Geometry Boost List: [ggl] union/intersection of multi-polygons

Subject: [ggl] union/intersection of multi-polygons
From: Barend Gehrels (Barend.Gehrels)
Date: 2010-02-07 17:12:44

Hi,

On the Boost list we got a report of failures of union of multi polygons.

In one case it indeed failed (solved now).

In another case, failure/passing is questionable. One of the input 
multi-polygons have intersections itself, so there are three or four 
triangles, partly overlapping each other, forming one multi-polygon. If 
that one is overlayed with another (multi)polygon, is it expected that 
those internal intersections are solved as well?

OGC says no. A valid (multi)geometry may not be self-overlapping. It can 
be self-tangent in some cases, but may not overlap itself.

So PostGIS says no. This query:
select astext(st_intersection(
geomfromtext('MULTIPOLYGON(((200 200,200 -200,-200 -200,-200 200,200 
200),(100 0,50 86.6025,-50 86.6025,-100 0,-50 -86.6025,50 -86.6025,100 
0)),((30 10,40 27.3205,50 10,30 10)))'),
geomfromtext('MULTIPOLYGON(((0 0,10 17.3205,20 0,0 0)),((-10 -10,0 
7.32051,10 -10,-10 -10)),((0 -15,10 2.32051,20 -15,0 -15)),((-50 
-40,-110 0,-100 30,-50 -40)))')));

Says:
NOTICE:  TopologyException: side location conflict 2.11325 3.66025
ERROR:  GEOS Intersection() threw an error!

And SQL Server 2008 also says no, with this query:
select geometry::STGeomFromText('MULTIPOLYGON(((200 200,200 -200,-200 
-200,-200 200,200 200),(100 0,50 86.6025,-50 86.6025,-100 0,-50 
-86.6025,50 -86.6025,100 0)),((30 10,40 27.3205,50 10,30 10)))',0).
STIntersection(geometry::STGeomFromText('MULTIPOLYGON(((0 0,10 
17.3205,20 0,0 0)),((-10 -10,0 7.32051,10 -10,-10 -10)),((0 -15,10 
2.32051,20 -15,0 -15)),((-50 -40,-110 0,-100 30,-50 -40)))',0))
;

It says:
Msg 6522, Level 16, State 1, Line 1
A .NET Framework error occurred during execution of user-defined routine 
or aggregate "geometry":
System.ArgumentException: 24144: This operation cannot be completed 
because the instance is not valid. Use MakeValid to convert the instance 
to a valid instance. Note that MakeValid may cause the points of a 
geometry instance to shift slightly.
System.ArgumentException:
   at Microsoft.SqlServer.Types.SqlGeometry.ThrowIfInvalid()
   at Microsoft.SqlServer.Types.SqlGeometry.STIntersection(SqlGeometry 
other)
.

Our library does not says these things, but (currently) just ignores 
those intersections and give a proper union, including the overlaps. Or, 
actually, that is the case here but as soon as the overlapping 
geometries all intersect with the other polygon, the result might be 
different.

What do we expect? Apparently some of our users expect the union to 
resolve internal intersections. However, always checking that would 
decrease performance, and in many cases, geometries are known to be 
non-intersecting.

There is another algorithm under development which would remove 
self-intersections. This is "dissolve", mentioned earlier this week. 
Coincidentally the postgis/geos is discussing this this week in 
parallel, clean_geometry / unary union / buffer(0).

So users can call:
multi_polygon a, b;
// fill a and b
multi_polygon ad, bd;
dissolve(a, ad);
dissolve(b, bd);
multi_polygon result;
union_(ad, bd, result);

Another option is giving the union an (optional) boolean flag to denote 
that self-intersections must be solved as well. It then (optionally) 
calls the dissolve internally, or, better, intersect them all at the 
same time.

/
/
Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20100207/baa0557e/attachment.html