[mkgmap-dev] Merge areas

Tue Apr 26 22:05:14 BST 2011

>
>>> 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