[mkgmap-dev] shapes with holes

Sat Jan 19 13:02:09 GMT 2013

> Hi WanMil,
>
> WanMil wrote
>> 1. RoundCoordsFilter creates an invalid polygon with hole
>> 2. PolygonSplitterFilter might split the polygon because it is too
>
>> large. It converts the polygon to a java.awt.geom.Area object, splits it
>> into two halves and converts it back in the method
>> PolygonSplitterBase.areaToShapes(..) method. This method does not check
>> the orientation of the returned polygons and therefore converts the hole
>> to same type the polygon has - in other words the hole is removed.
>
> I thought about this again and I think it might be the solution for the
> mp-cut
> problem:
> We don't have to cut out inner polygons, instead we can connect each inner
> polygon with the outer one. We have to find two points:
> p1, a point on the outer way that is close to a point of the inner polygon,
> which
> is then called p2.
> Now, we have to split the outer way at p1, draw a line to p2, add the points
> of
> the inner polygon, and draw a way back from p2 to p1.
> It works (QLandkarte shows the polygon with a hole), but only when
> none of the filters destroys the added ways between p1 and p2.
>
> I don't know yet how multiple nested polygons look like, but I think it is a
> promising approach.
>
> Gerd

Hi Gerd,

that was the original approach how MPs were handeled in mkgmap but I 
changed it because of many problems.

1. You talked about the filter problem. Any use of the java Area object 
must be replaced. That might be possible but I expect a performance problem.
2. Finding a connection between inner and outer is not so easy as it 
sounds. You also have to check that the connection of inner and outer 
does not intersect any other inner/outer polygon. Also it must be 
checked that it does not intersect the same polygon.

Look at the following mp (drawn partially):
       i       i                7
       1iiiiiii2                o
                                o
8ooooooooooooooooooooooo3      o
                         o      o
ooooooo6   5oooooooooooo4      o
o      ooooo                   o
o                              o
oooooooooooooooooooooooooooooooo

o = outer polygon; i = inner polygon
7 is connected with 8 somwhere above my drawing

Using the closest approach you would cut between point 6 and 1. But this 
intersects the outer polygon so it's not a good idea...
So you have to add some costly checks which point is directly 
connectable. There is an algorithm (I don't remember the name) that 
calculates which points are directly visible from a given point. If you 
want to implement it would work. Just search Wikipedia and the polygon 
algorithms. You will find it. I guss it's not very nice to the 
performance...

So if you can realize it it probably will be a good approach. The 
algorithms are a bit more complex than it seems on a first sight.

WanMil