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 _______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
