[mkgmap-dev] Multipolygons and basic question on polygons with holes

Tue Jan 5 21:10:55 GMT 2010

Am 02.01.2010 15:18, schrieb Christian Gawron:
> Am 02.01.2010 00:19, schrieb Steve Ratcliffe:
>> [...]
>> Some observations
>>
>> 1. The sea polygon is probably cut up into small enough pieces first,
>> before the "cuts" to the hole are made.
>> 2. Because we do things the other way round, we make the cut a slight
>> wedge shape, as you cannot send polygons that have touching segments
>> to the polygon splitting code.  This is what makes things look bad.
>> 3. If you split a sea polygon with a line that goes "through" (around)
>> a hole then you don't need to add a cut.
>> 4. Its probably easier to do it by hand, but that might just reflect
>> my lack of knowledge of GIS algorithms in this area...
>>
> I think it should not be too hard to create an algorithm that decomposes
> a polygon with holes into polygons without holes. I googled for "polygon
> decomposition" and found a paper describing an algorithm to decompose a
> polygon with holes into convex polygons, but this seems to be more than
> we need (and too complex computationally). Right now I have some time so
> I will have a look at it.
>
> Best wishes
> Christian
 >

Christian,

I think it's a good idea to change the strategy from the old "polygon 
with holes" to "simple polygons". The old strategy does not work with 
the PolygonSplitter and seems to be too complex.

I have some requirements to the new strategy:
* It should handle most of possible cases. Otherwise we will always have 
complaints about not supported multipolygons.
* It should take not too much performance. The current findCpa method is 
a performance killer for polygons with lots of points.
* It should work with the current PolygonSplitter. This is achieved by 
creating simple polygons.

At the moment I am using your idea of simple polygons and try a new 
implementation using the java.awt.Area class that is also used in the 
PolygonSplitter. I hope this will achieve the requirements.

WanMil