Spatially Equal (IV)

Today we continue our "Spatially Equal" research started in February. In the meantime I've updated sources of Boost.Geometry to support for the situations described in the blogs I and II of these series.

Our new question is: is a polygon equal to its reverse? In other words: a triangle going from (0,0) to (0,4) and then via (4,0) back to (0,0) is orientated clockwise. Is this triangle considered as spatially equal to a triangle having the same coordinates but orientated counter clockwise?

However, there is a subtility here. In set theory there is the concept of the Complement. Wiki states that "The complement of set A refers to things not in A". The complement of set A can be written as A^c. The complement of a triangle in Spatial Set theory is containing all space outside that triangle. A triangle can be represented as 3 points, and its complement can be represented as three points in opposite direction! So assume that a clockwise oriented triangle contains all points inside, then a counter clockwise orientated triangle contains all points outside that triangle, so all points in the universe excepted the space in that triangle.

So are two triangles with different orientaties spatially equal? On the contrary, if you follow Spatial Set theory, they should not be equal. Are their borders equal? The answer depends on the definition of border, if a line is equal to a line in opposite direction, then yes, else no.

OGC's Simple Feature specification is built upon Spatial Set theory. However its specification does not state the orientation of polygons, and it also does not state if two polygons only differing in orientation are equal...

SQL Server and PostGIS both answer yes on this question: a polygon is equal to its reverse. Used SQL query (SQL Server 2008):

select geometry::STGeomFromText('POLYGON((0 0,0 4,4 0,0 0))',0)
.STEquals(geometry::STGeomFromText('POLYGON((0 0,4 0,0 4,0 0))',0));

Spatially Equal (III)

The previous two blogs handled Spatially Equal.

What does Spatially Equal mean? OGC says: Given two (topologically closed) geometric objects “a” and “b”: a.Equals(b) ⇔ a ⊆ b AND b ⊆ a

This means: a is a subset of b and b is subset of a. This can only be true if a and b are equal. OGC continues with the so-called Dimensionally Extended 9 Intersection Matrix (DE9IM). We skip the formal definition here, the essention OGC is describing for Spatially Equal is:

• there is overlap in their interiors
• there is overlap in their boundaries
• there is no overlap of boundary of a and interior of b and vice versa
• there is no overlap of boundary of a with the exterior of b and vice versa

All these conditions together can only be true if a and b are equal.

A point? A point does not have a real interior (though that can be discussed - what is the interior...), and does not have a boundary. But two points can certainly be equal... So the DE9IM specified by OGC (in summary: "TFFFTFFFT") is not correct for points. Checking this using PostGIS indeed shows that points do have another DE9IM ("0FFFFFF2"), not matching in place 5 (all other places not F, false match with T, true).

PostGIS defines Spatially Equal as: Returns true if the given geometries represent the same geometry. Directionality is ignored. So this last part is important, a clockwise polygon is equal to a counter clockwise polygon, according to PostGIS. It continues: This function will return false if either geometry is invalid even if they are binary equal.. It is a bit unclear if this is relevant for ST_Equals or for the also described ST_OrderingEquals, because we have seen before that PostGIS returns true for invalid but Spatially Equal polygons.

So let's try to make a new definition:

Spatially Equals is:

Alternative 1) two geometries cover the same area. This is an easy one. Too easy.

Alternative 2) both interiors contain the same pointset, and both boundaries contain the same pointset. Not bad.

Alternative 3) same as 2, but to adding: the order of which points are stored in boundaries of a geometry is not relevant

However, I doubt that this addition of 3) is wise. Are two polygons with mutually reversed borders spatially equal? We come back to that in a next blog.

So our current definition is: both interiors contain the same pointset, and both boundaries (if any) contain the same pointset. In this definition a point contains of an interior with a pointset of one element: the point... It might be refined later on.

Spatially Equal (II)

Yesterday I wrote a blog page about a geometry having two representations, one of them using an interior ring. A similar situation is going on with the polygon above: it has two representations, one as one self-touching polygon, and another one as a multi-polygon consisting of two polygons. Because of the similar situation, I would expect that databases would behave in a similar way onto this...

So two possible Well-Known Texts of the polygon above are:

• POLYGON((0 0,0 1,2 3,3 0,4 2,5 0,0 0))
• MULTIPOLYGON(((0 0,0 1,2 3,3 0,0 0)),((3 0,4 2,5 0,3 0)))

Let's again inspect how this behaves in different spatial databases. SQL Server reported earlier that both representations of a touching interior ring were both valid. Now it is different:

• one ring: no, it is not valid; the area function gives an exception: SqlGeometry.ThrowIfInvalid()
• two rings: yes, it is valid; the area is 7.5
• the STEquals method cannot be called for these two representations, it raises the same exception

PostGreSQL / PostGIS says:

• one ring: no, it is not valid; it has area 7.5
• two rings: yes, it is valid; it has area 7.5
• the ST_Equals function returns t (true)

So, for SQL Server, STEquals throws because the polygon is invalid. Apparently this is always (or at least often) the case for SQL Server, and it makes sense: you cannot call functions on invalid input. And because of this we now know that even for a (internally quite simple) area algorithm, it also checks validity... That must have a performance loss...

So PostGreSQL behaves exactly the same as in the case of the interior ring. ST_Equals returns true. It can call it on invalid input, OK for me. So these polygons are considered spatially equal, perfect. Note, I'm not saying which succeeds and which fails... The definitions of OGC polygons and (maybe) ISO polygons are not always clear, as also can be read in the paper of van Oosterom et al mentioned in my previous blog.

If a polygon is a connected set of points, bounded by one or more rings (I mean, they can be filled with one "flood fill" action in drawing software), then SQL Server perfectly conforms to that definition... Because the first case, with the semi-interior ring, the polygon interior is a connected set of points. In the second case, two touching rings, there are actually two interiors! So these cases are not symmetrical.

We will see more of this in an upcoming blog about the rules.

I now also checked MySQL. MySQL does not have the IsValid function. But it has Area and Equals (without the ST prefix). The area is correctly reported as 7.5 for both representations. And the equals function returns true. Because it was not reported before: in the case of the touching interior ring, area was 6 (correct), equals returns 1 (true), perfect.

In the coming days we will see more in this blog on Spatially Equal: how OGC defines it, some other situations, and, in the end, how Boost.Geometry behaves... (because it currently reports them all as not equal...)

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))'));