Tuesday, February 16, 2010

Spatially Equal (I)


Spatially Equal (I)




This green polygon above can be represented in two different ways:
  • as one sequence of points, so one ring, which is self-touching in point (1,2)
  • as an exterior ring ring, and an interior ring, both rings touch in point (1,2)
Using WKT the representations are as following (sorry the picture above was a little shifted afterwards and will be recreated):
  • POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))
  • POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))
The first representation is the sequence of points, the second representation is an exterior ring (the first sequence of points) and an interior ring (the second sequence, starting at the opening brace).

The first question is: is this polygon valid? OGC says: No two Rings in the boundary cross and the Rings in the boundary of a Polygon may intersect at a Point but only as a tangent. So what does this say? At least it seems to say that the exterior ring may touch the interior ring. There is no crossing here, so if a ring may self-touch is not written explicitly. SQL Server 2008 says:
  • one ring: yes, it is valid; it has area 6
  • two rings: yes, it is valid; it has area 6
PostGreSQL / PostGIS says:
  • one ring: no, it is not valid; it has area 6
  • two rings: yes, it is valid; it has area 6
I didn't check Oracle.

The second question is: are both representations spatially equal? Spatially equal means: they cover exactly the same area, they contain exactly the same points. So the expected answer is: yes. Yes, both representations are considered as spatially equal by both SQL Server and PostGIS. Boost.Geometry currently considers these representations as not equal, just because there is no match in their rings. So I have to update our library... See also this paper, containing much more information about valid and invalid polygons, and questions: http://www.gdmc.nl/publications/2004/Invalid_Valid_Clean_Polygons.pdf


Used SQL Server 2008 Queries:
select geometry::STGeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))',0).STIsValid();
select geometry::STGeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))',0).STIsValid();
select geometry::STGeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))',0).STArea();
select geometry::STGeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))',0).STArea();
select geometry::STGeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))',0)
.STEquals(geometry::STGeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))',0));

Used PostGreSQL/PostGIS queries:
select ST_IsValid(ST_GeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))'));
select ST_IsValid(ST_GeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))'));
select ST_Area(ST_GeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))'));
select ST_Area(ST_GeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))'));
select ST_Equals(ST_GeomFromText('POLYGON((2 2,3 3,4 3,4 0,1 0,1 1,2 2),(2 1,3 1,3 2,2 2,2 1))')
,ST_GeomFromText('POLYGON((1 1,2 2,2 1,3 1,3 2,2 2,3 3,4 3,4 0,1 0,1 1))'));