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