Wednesday, February 17, 2010

Spatially Equal (II)


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...)