Hi! Did you ever think about merging areas mapped to the same garmin type when they touch? I'm thinking about an algorithm that for each zoom level checks, if two areas touch, and when yes merge them when they have the same garmin type. The motivation: At the moment, areas that are mapped with lots of details can completely go lost in low zoom levels. The detailed areas are removed because they are below the minimum polygon size. At these low zoom levels, it can happen that after rounding of the coordinates the areas touch. I think the user would prefer to see the merged area in the low zoom level, when in the higher zoom level the area is almost completely covered with one type. The algorithm shall probably be only used for landuse types. For other types (building=* for example), it would lead to undesired behaviour (mark in polygons stylefile?). Cheers, Daniel -- GMX DSL Doppel-Flat ab 19,99 Euro/mtl.! Jetzt mit gratis Handy-Flat! http://portal.gmx.net/de/go/dsl
Hi!
Did you ever think about merging areas mapped to the same garmin type when they touch? I'm thinking about an algorithm that for each zoom level checks, if two areas touch, and when yes merge them when they have the same garmin type.
The motivation: At the moment, areas that are mapped with lots of details can completely go lost in low zoom levels. The detailed areas are removed because they are below the minimum polygon size. At these low zoom levels, it can happen that after rounding of the coordinates the areas touch. I think the user would prefer to see the merged area in the low zoom level, when in the higher zoom level the area is almost completely covered with one type.
The algorithm shall probably be only used for landuse types. For other types (building=* for example), it would lead to undesired behaviour (mark in polygons stylefile?).
Cheers, Daniel
That's definitely worth thinking about it. I expect that it will be hard to find a solution with a good performance but maybe it will be easier than I expect. Some things that come to my mind when thinking about it: * If you merge two touching areas you might create holes in it. In this case you have to recut the merged area in two halfs because polygons with holes are not supported by the garmin format (no native garmin multipolygon available). * The current multipolygon processing might change its behaviour so that it precompiles the mps (decide which polygon is inside the other and decide which tags are used). The cut process might be relocated to each level creation so that too small inner polygons need not be cut out for higher levels. * Why do you want to use the merge for landuse types only? Why not for buildings? Do you have a short draft how you want to detect that two areas are touching? WanMil
Hi!
* Why do you want to use the merge for landuse types only? Why not for buildings?
I think about towns with many separate stand-alone buildings. When the are all merged, the whole town is a single building. For rows of flats it's OK.
Do you have a short draft how you want to detect that two areas are touching?
When two nodes follwing each other from one polygon are inside the other. Or on the outline of it. Cheers, Daniel -- NEU: FreePhone - kostenlos mobil telefonieren und surfen! Jetzt informieren: http://www.gmx.net/de/go/freephone
Do you have a short draft how you want to detect that two areas are touching? When two nodes follwing each other from one polygon are inside the other. Or on the outline of it.
Yeah, and you will have to test some 100 thousands of nodes, if they lie inside one of a 10 thousands polygons. This will be as a number of thumb 10 ^ 9 tests (or add some more zeroes) of tests if the is node in polygon area, which is not a cheap test by itself. You will need at least some tricks with quadtrees or bounding box checks to achieve reasonable runtimes. In general I really like the idea of merging polygon areas. I have mentioned it already in this mailing list. But up to now I haven't found any practicable solution. The algorithm should merge two polygons even if there is some space between it. Think of a map of small woods or lakes, which should be combined to a bigger one and simplified, while zooming out of the map. They are *not* overlapping or touching in most of the cases. I don't want discourage you, if you think, you have some working solution, please let us know. Regards, Johann
Do you have a short draft how you want to detect that two areas are touching? When two nodes follwing each other from one polygon are inside the other. Or on the outline of it.
Yeah, and you will have to test some 100 thousands of nodes, if they lie inside one of a 10 thousands polygons. This will be as a number of thumb 10 ^ 9 tests (or add some more zeroes) of tests if the is node in polygon area, which is not a cheap test by itself.
You will need at least some tricks with quadtrees or bounding box checks to achieve reasonable runtimes.
Yes, the complexity is very high and it will be a hard task to achieve that in a reasonable time. I plan to add an R*-tree to get a better performance in the locator branch. Maybe this might be reused. If someone (Daniel?) likes to implement the R*-tree please lift your fingers. I am not very keen on doing this and it would help a lot!
In general I really like the idea of merging polygon areas. I have mentioned it already in this mailing list. But up to now I haven't found any practicable solution. The algorithm should merge two polygons even if there is some space between it. Think of a map of small woods or lakes, which should be combined to a bigger one and simplified, while zooming out of the map. They are *not* overlapping or touching in most of the cases.
I would start with a more simple approach: Different levels have different coordinate accuracies. I think mkgmap must recalculate the coordinates of all polygons based on the current level (is that correct?!?). One might search for identical coordinate pairs and these coordinate pairs must only be searched within polygons with identical garmin ids. That sounds feasable. It's not the perfect approach but it might realizable as a first step. Daniel, are you still encouraged to give it a try? WanMil
I don't want discourage you, if you think, you have some working solution, please let us know.
Regards, Johann
I plan to add an R*-tree to get a better performance in the locator branch. Maybe this might be reused. If someone (Daniel?) likes to implement the R*-tree please lift your fingers. I am not very keen on doing this and it would help a lot!
Have you looked around, if there is some implementation already available? At a quick search I have found some interesting projects: http://www.rtreeportal.org/code.html seems to have a small use ready R*-tree project. Not sure about the license. http://www2.research.att.com/~marioh/spatialindex/ looks more overloaded with unneeded features. http://en.giswiki.net/wiki/JSI_%28Java_Spatial_Index%29_RTree_Library is an open source project.
I plan to add an R*-tree to get a better performance in the locator branch. Maybe this might be reused. If someone (Daniel?) likes to implement the R*-tree please lift your fingers. I am not very keen on doing this and it would help a lot!
Have you looked around, if there is some implementation already available? At a quick search I have found some interesting projects:
http://www.rtreeportal.org/code.html seems to have a small use ready R*-tree project. Not sure about the license.
http://www2.research.att.com/~marioh/spatialindex/ looks more overloaded with unneeded features.
http://en.giswiki.net/wiki/JSI_%28Java_Spatial_Index%29_RTree_Library is an open source project.
Hi Johann, thanks for your query. If found the first two projects myself. The source code is quite old stylish and lot of work seems to be necessary to use the two projects. But the third one looks like a perfect match! 1. The project is alive 2. The R-Tree is completely kept in memory 3. It's open source and the licence should be ok for us After a first short try I got some exceptions with the R-Tree but I think these are little problems that can be fixed. Thanks for hint!! WanMil
participants (3)
-
Johann Gail -
spam-me＠gmx-ist-cool.de -
WanMil