[OSM-dev] Multipolygon processing (was: osm2spatialite!)

Sarah Hoffmann lonvia at denofr.de
Fri Feb 18 13:55:11 GMT 2011


Hi,

On Fri, Feb 18, 2011 at 08:22:54AM +0100, Frederik Ramm wrote:
> Hi,
>
> On 02/18/11 04:35, Daniel Sabo wrote:
>>> Makes sense. Do you do anything about touching inner rings?
>>
>> No, and I haven't thought of a good way to handle it. If you have an         algorithm that works well I'd be interested it it :).
>
> I use the GEOS library and I test all pairs of inner rings for  
> intersections. Then if I find a pair with an intersection, I check if  
> that intersection is a line (rather than just a point). If it is a line,  
> then I compute the "SymDifference" between the two and throw the result  
> of that into the polygonizer which hopefully will be able to make one  
> ring from it. You can look at my algorithm here

I have tried a slightly different approach to the multipolygon problem
which goes like this: first, find all possible linear rings by first
joining the ways at the obvious points and then repairing the remaining
gaps. Second, compute the outer hull of all rings, which gives valid
polygons for all rings, i.e it resolves any self-intersections. Finally, 
compute a MultiPolygon by taking the SymDifference of all these polygons.

The SymDifference conveniently sorts out outer and inner rings, and can
handle nested inner rings, multiple outer rings and touching rings. 
Only rings that intersect each other might have to be treated in a 
special way.

It turns out that the tricky part is the computation of the outer hull.
GEOS' buffer() function should be able to do that but it is also produces
wrong results when encountering self-intersections, so there seems to be no
way around writing a hand-crafted sweep algorithm.

> All this is probably only halfway there. I'd be very interested in ideas  
> how to fix broken multipolygons. There is some code there (line 117ff  
> tries to repair self-intersections and 343ff tries to fill gaps in  
> rings) but still OSM users come up with ever more invalid polygons ;)

How about a gallery of spectacularly misshaped multipolygons?

Sarah



More information about the dev mailing list