Commit: r2277: Adjust TRE size of test
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 May 2012) Adjust TRE size of test Commit 2276 changed the size of the TRE file by using a different subdivision algorithm.
Gerd, the SimpleRouteTest checks if the file sizes of the img files are as expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself? Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi WanMil, sorry, I should have run the tests myself. We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a better solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier? Gerd WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are as expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi WanMil,
sorry, I should have run the tests myself.
I didn't do that either before committing...
We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a better solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier?
Yes but I think that requires the general rework of the subdivision algorithm I explained in one of my previous posts. In general you have to find an algorithm that assigns all elements to a subdivision so that the multiple limits of the subdivision are not exceeded. The current algorithm implements a top-down algorithm, i.e. create the largest possible subdivisions, add all elements to it and split them until all limits are ok. The problem arises if splitting does not help to find a solution and the limits are still exceeded. The bottom-up algorithm would add elements to subdivisions so that their limits are not exceeded. Theoretically this would results in a better fill level of the subdivisions and therefore less subdivisions. Maybe it is necessary to split elements so that they fit into a subdivision without exceeding its limits. I don't know if this algorithm is ever possible. Problems might be: - if subdivisions need to be hierarchical over different layers you need a kind of subdivision splitting when processing the next layer - the algorithm handling the multiple limits is complex. Maybe it's easier to start with adding only one type of elements to a subdivision (so having POI subdivisions, line subdivisions and shape subdivisions). This reduces the number of limits the algorithm has to handle simultanously. - when is it better to split a line because it does not fit to a subdivision or to create a new subdivision? Creating a new subdivision might result is lots of subdivisions with a few lines/shapes only. Hopefully you have some good ideas for that :-) Anyhow it is astonishing how good the current algorithm with the two bounds works. WanMil
Gerd
WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are as expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi WanMil, I think we are talking about different things reg. the bounding boxes. I meant the two bounding boxes within the OSM data. We read the data and may find a bounding box. If we do, we use it. The OSM file may contain a lot of points outside of this bounding box (I think this is the effect of the overlap parameter in splitter). The question for me is at what point this overlap is no longer needed, means, isn't it possible to clip everything that is outside of the bounding box which was saved in the OSM file? I think that would help to simplify the MapSplitter algorithm. Gerd
Date: Mon, 7 May 2012 19:56:24 +0200 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Commit: r2277: Adjust TRE size of test
Hi WanMil,
sorry, I should have run the tests myself.
I didn't do that either before committing...
We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a better solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier?
Yes but I think that requires the general rework of the subdivision algorithm I explained in one of my previous posts.
In general you have to find an algorithm that assigns all elements to a subdivision so that the multiple limits of the subdivision are not exceeded. The current algorithm implements a top-down algorithm, i.e. create the largest possible subdivisions, add all elements to it and split them until all limits are ok. The problem arises if splitting does not help to find a solution and the limits are still exceeded.
The bottom-up algorithm would add elements to subdivisions so that their limits are not exceeded. Theoretically this would results in a better fill level of the subdivisions and therefore less subdivisions. Maybe it is necessary to split elements so that they fit into a subdivision without exceeding its limits. I don't know if this algorithm is ever possible. Problems might be: - if subdivisions need to be hierarchical over different layers you need a kind of subdivision splitting when processing the next layer - the algorithm handling the multiple limits is complex. Maybe it's easier to start with adding only one type of elements to a subdivision (so having POI subdivisions, line subdivisions and shape subdivisions). This reduces the number of limits the algorithm has to handle simultanously. - when is it better to split a line because it does not fit to a subdivision or to create a new subdivision? Creating a new subdivision might result is lots of subdivisions with a few lines/shapes only.
Hopefully you have some good ideas for that :-) Anyhow it is astonishing how good the current algorithm with the two bounds works.
WanMil
Gerd
WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are as expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd, there are two reasons for the overlap: 1. lines and shapes need to be clipped and therefore they require that at least one more point outside the bbox is available 2. multipolygons can be handled the better the more complete they are contained in the tile The MapSplitter algorithm has nothing to do with this overlap. All items are already clipped to the bounding box when the MapSplitter comes into action (see StyledConverter.clipper). WanMil
Hi WanMil,
I think we are talking about different things reg. the bounding boxes. I meant the two bounding boxes within the OSM data. We read the data and may find a bounding box. If we do, we use it. The OSM file may contain a lot of points outside of this bounding box (I think this is the effect of the overlap parameter in splitter). The question for me is at what point this overlap is no longer needed, means, isn't it possible to clip everything that is outside of the bounding box which was saved in the OSM file? I think that would help to simplify the MapSplitter algorithm.
Gerd
Date: Mon, 7 May 2012 19:56:24 +0200 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Commit: r2277: Adjust TRE size of test
Hi WanMil,
sorry, I should have run the tests myself.
I didn't do that either before committing...
We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a
better
solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier?
Yes but I think that requires the general rework of the subdivision algorithm I explained in one of my previous posts.
In general you have to find an algorithm that assigns all elements to a subdivision so that the multiple limits of the subdivision are not exceeded. The current algorithm implements a top-down algorithm, i.e. create the largest possible subdivisions, add all elements to it and split them until all limits are ok. The problem arises if splitting does not help to find a solution and the limits are still exceeded.
The bottom-up algorithm would add elements to subdivisions so that their limits are not exceeded. Theoretically this would results in a better fill level of the subdivisions and therefore less subdivisions. Maybe it is necessary to split elements so that they fit into a subdivision without exceeding its limits. I don't know if this algorithm is ever possible. Problems might be: - if subdivisions need to be hierarchical over different layers you need a kind of subdivision splitting when processing the next layer - the algorithm handling the multiple limits is complex. Maybe it's easier to start with adding only one type of elements to a subdivision (so having POI subdivisions, line subdivisions and shape subdivisions). This reduces the number of limits the algorithm has to handle simultanously. - when is it better to split a line because it does not fit to a subdivision or to create a new subdivision? Creating a new subdivision might result is lots of subdivisions with a few lines/shapes only.
Hopefully you have some good ideas for that :-) Anyhow it is astonishing how good the current algorithm with the two bounds works.
WanMil
Gerd
WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are as expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100
(Sun, 06
May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi WanMil, sorry, forget my complains. I overlooked that SimpleRouteTest uses two input files for testing. I was confused by the data from the 2nd file. MapSplitter doesn't see any data outside of the bbox saved in the OSM file. So, we have two different bounding boxes in MapSplitter: 1) A real bounding box which grows with the data added to an area and 2) A logical bounding box which is devided in the split process and which is used to calculate the offsets. I have no clear idea for an optimized algorithm, I guess it could be somehow similar to the DensityMap in the tile splitter, but I doubt that it will be much faster. Probably more importantant is the problem that you have described in your picture. I think a solution for this must make sure that we don't add two (or more) large objects to one area, or we have to allow a logical bounding box with a width and height equal to 1 (instead of 10). I don't know if this limit of 10 is given by the img format or if it is just a reasonable value to stop the recursion? Gerd WanMil wrote
Hi Gerd,
there are two reasons for the overlap: 1. lines and shapes need to be clipped and therefore they require that at least one more point outside the bbox is available 2. multipolygons can be handled the better the more complete they are contained in the tile
The MapSplitter algorithm has nothing to do with this overlap. All items are already clipped to the bounding box when the MapSplitter comes into action (see StyledConverter.clipper).
WanMil
Hi WanMil,
I think we are talking about different things reg. the bounding boxes. I meant the two bounding boxes within the OSM data. We read the data and may find a bounding box. If we do, we use it. The OSM file may contain a lot of points outside of this bounding box (I think this is the effect of the overlap parameter in splitter). The question for me is at what point this overlap is no longer needed, means, isn't it possible to clip everything that is outside of the bounding box which was saved in the OSM file? I think that would help to simplify the MapSplitter algorithm.
Gerd
Date: Mon, 7 May 2012 19:56:24 +0200 From: wmgcnfg@ To: mkgmap-dev@.org Subject: Re: [mkgmap-dev] Commit: r2277: Adjust TRE size of test
Hi WanMil,
sorry, I should have run the tests myself.
I didn't do that either before committing...
We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a
better
solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier?
Yes but I think that requires the general rework of the subdivision algorithm I explained in one of my previous posts.
In general you have to find an algorithm that assigns all elements to a subdivision so that the multiple limits of the subdivision are not exceeded. The current algorithm implements a top-down algorithm, i.e. create the largest possible subdivisions, add all elements to it and split them until all limits are ok. The problem arises if splitting does not help to find a solution and the limits are still exceeded.
The bottom-up algorithm would add elements to subdivisions so that their limits are not exceeded. Theoretically this would results in a better fill level of the subdivisions and therefore less subdivisions. Maybe it is necessary to split elements so that they fit into a subdivision without exceeding its limits. I don't know if this algorithm is ever possible. Problems might be: - if subdivisions need to be hierarchical over different layers you need a kind of subdivision splitting when processing the next layer - the algorithm handling the multiple limits is complex. Maybe it's easier to start with adding only one type of elements to a subdivision (so having POI subdivisions, line subdivisions and shape subdivisions). This reduces the number of limits the algorithm has to handle simultanously. - when is it better to split a line because it does not fit to a subdivision or to create a new subdivision? Creating a new subdivision might result is lots of subdivisions with a few lines/shapes only.
Hopefully you have some good ideas for that :-) Anyhow it is astonishing how good the current algorithm with the two bounds works.
WanMil
Gerd
WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are
as
expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100
(Sun, 06
May 2012)
Adjust TRE size of test
Commit 2276 changed the size of the TRE file by using a different subdivision algorithm. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd,
Hi WanMil,
sorry, forget my complains. I overlooked that SimpleRouteTest uses two input files for testing. I was confused by the data from the 2nd file. MapSplitter doesn't see any data outside of the bbox saved in the OSM file.
So, we have two different bounding boxes in MapSplitter: 1) A real bounding box which grows with the data added to an area and 2) A logical bounding box which is devided in the split process and which is used to calculate the offsets.
I have no clear idea for an optimized algorithm, I guess it could be somehow similar to the DensityMap in the tile splitter, but I doubt that it will be much faster.
The main target should not be a faster but a better algorithm that handles all cases of input data.
Probably more importantant is the problem that you have described in your picture. I think a solution for this must make sure that we don't add two (or more) large objects to one area, or we have to allow a logical bounding box with a width and height equal to 1 (instead of 10). I don't know if this limit of 10 is given by the img format or if it is just a reasonable value to stop the recursion?
I think it's a vale to stop the recursion. WanMil
Gerd
WanMil wrote
Hi Gerd,
there are two reasons for the overlap: 1. lines and shapes need to be clipped and therefore they require that at least one more point outside the bbox is available 2. multipolygons can be handled the better the more complete they are contained in the tile
The MapSplitter algorithm has nothing to do with this overlap. All items are already clipped to the bounding box when the MapSplitter comes into action (see StyledConverter.clipper).
WanMil
Hi WanMil,
I think we are talking about different things reg. the bounding boxes. I meant the two bounding boxes within the OSM data. We read the data and may find a bounding box. If we do, we use it. The OSM file may contain a lot of points outside of this bounding box (I think this is the effect of the overlap parameter in splitter). The question for me is at what point this overlap is no longer needed, means, isn't it possible to clip everything that is outside of the bounding box which was saved in the OSM file? I think that would help to simplify the MapSplitter algorithm.
Gerd
Date: Mon, 7 May 2012 19:56:24 +0200 From: wmgcnfg@ To: mkgmap-dev@.org Subject: Re: [mkgmap-dev] Commit: r2277: Adjust TRE size of test
Hi WanMil,
sorry, I should have run the tests myself.
I didn't do that either before committing...
We see the different values because the patched version splits a few more times. I think the result is okay, but maybe there is a
better
solution. If I got this right, we deal with two different bounding boxes: the bounding box that is saved in the OSM data and the bounding box of all objects. I wonder if it is correct that the MapSplitter has to handle data that is outside of the OSM bounding box? These two different bboxes were the reason for some errors in the splitting process, and my patch only fixes the problem in MapSplitter / MapArea, but maybe it could be handled earlier?
Yes but I think that requires the general rework of the subdivision algorithm I explained in one of my previous posts.
In general you have to find an algorithm that assigns all elements to a subdivision so that the multiple limits of the subdivision are not exceeded. The current algorithm implements a top-down algorithm, i.e. create the largest possible subdivisions, add all elements to it and split them until all limits are ok. The problem arises if splitting does not help to find a solution and the limits are still exceeded.
The bottom-up algorithm would add elements to subdivisions so that their limits are not exceeded. Theoretically this would results in a better fill level of the subdivisions and therefore less subdivisions. Maybe it is necessary to split elements so that they fit into a subdivision without exceeding its limits. I don't know if this algorithm is ever possible. Problems might be: - if subdivisions need to be hierarchical over different layers you need a kind of subdivision splitting when processing the next layer - the algorithm handling the multiple limits is complex. Maybe it's easier to start with adding only one type of elements to a subdivision (so having POI subdivisions, line subdivisions and shape subdivisions). This reduces the number of limits the algorithm has to handle simultanously. - when is it better to split a line because it does not fit to a subdivision or to create a new subdivision? Creating a new subdivision might result is lots of subdivisions with a few lines/shapes only.
Hopefully you have some good ideas for that :-) Anyhow it is astonishing how good the current algorithm with the two bounds works.
WanMil
Gerd
WanMil wrote
Gerd,
the SimpleRouteTest checks if the file sizes of the img files are
as
expected. After commiting the subdivision change the TRE file size changed. I think thats ok, but can you please check that yourself?
Thanks! WanMil
> > Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06 > May 2012) > > Adjust TRE size of test > > Commit 2276 changed the size of the TRE file by using a different > subdivision algorithm. > _______________________________________________ > mkgmap-dev mailing list > mkgmap-dev@.org > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@.org http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
-- View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp568958... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (4)
-
Gerd Petermann -
GerdP
-
svn commit -
WanMil