Geometry Boost List: [ggl] is_simple is_valid

Subject: [ggl] is_simple is_valid
From: Mateusz Loskot (mateusz)
Date: 2009-10-05 17:35:01

Barend Gehrels wrote:
> Mateusz Loskot wrote:
>> Barend Gehrels wrote:
>>>
>>> I'm looking at self-intersections to implement the function is_simple
>>> (based on blocks we already have). But I'm what confused about the name.
>>>
>>> According to OGC:  IsSimple  (): Integer Returns 1 (TRUE) if this
>>> geometric object has no anomalous geometric points, such as self
>>> intersection or self tangency. The description of each instantiable
>>> geometric class will include the specific conditions that cause an
>>> instance of that class to be classified  as not simple.
>>>
>>> JTS says: Valid polygonal geometries are simple by definition, so
>>> isSimple trivially returns true.
>>> (http://www.vividsolutions.com/JTS/javadoc/com/vividsolutions/jts/geom/Geometry.html#isSimple())
>>
>> Yes, but the result is not well defined for invalid geometries, so
>> isSimple may result true for non-simple && invalid geometry.
>>
>> Here is two points exaplnation provided by Martin - JTS guru
>> (http://postgis.refractions.net/pipermail/postgis-users/2004-April/004507.html):
>
> Thanks for the link. Martin explains: /"It states that Polygons are
> always simple geometries (sec. 2.1.10)."/ and indeed I now find the
> statement /polygons are simple geometric objects/. Seems to me
> contratictory, but OK.

I can't see any contradiction in the two statements.

> However, is_valid is NOT an OGC method as far as I can see in the older
> and newer specs.

I asked PostGIS folks for clarification
(http://postgis.refractions.net/pipermail/postgis-devel/2009-October/006915.html)

"ST_IsValid is *not* an OGC defined function"

And, thanks to the beauty of Open Source Software development model,
it's got improved in the manual :-)

http://trac.osgeo.org/postgis/changeset/4597

>>> The PostGIS implementation give TRUE back to all self-intersecting
>>> polygons that I try.
>>>     
>>
>> Can you give WKT of simple example of such polygon?
>   
> select IsSimple(GeomFromText('POLYGON((1 2,1 1,2 1,2 2.25,3 2.25,3 0,0
> 0,0 3,3 3,2.75 2,1 2))')) -> true

My analysis that AFAIK conforms PostGIS and other implemenations of OGC:

1. There is no guarantee to return correct results for invalid
   geometries.

2. This polygon is invalid because it's self-intersecting,

3. The implication based on 1 and 2 is that the reported "true" result
   shall be considered as "undefined result".

Undefined is...undefined, what means it may make sense or not. Just as
undefined behaviour in C++ :)

> select IsSimple(GeomFromText('LINESTRING(1 2,1 1,2 1,2 2.25,3 2.25,3 0,0
> 0,0 3,3 3,2.75 2,1 2)')) -> false

1. Simple linestring if it does not pass through the same point twice

2. The implication based on 1 is that the reported "true" result
   is correct.

> select IsValid(GeomFromText('POLYGON((1 2,1 1,2 1,2 2.25,3 2.25,3 0,0
> 0,0 3,3 3,2.75 2,1 2))')) -> false

> select IsValid(GeomFromText('LINESTRING(1 2,1 1,2 1,2 2.25,3 2.25,3 0,0
> 0,0 3,3 3,2.75 2,1 2)')) -> true

The OGC Validity chapter in PostGIS manual says:

"Typically, it doesn't make sense to check for validity on linear
features since it will always return TRUE."

> This behaviour sounds completely illogical to me:
> *- a self-intersecting linestring is valid but not simple

Because of the extra note above about checking validity of linear
geometries.

> - a self-intersecting polygon is simple but not valid
> *
> Anyway, this is probably not the right platform to discuss that.

Why not? It's a proper geometry problem, IMHO.

> The OGC spec indeed states that a simple linestring may not self-intersect...

Actually, it must not self-intersect.

> But the message here is: do we want that GGL follows this behaviour?
> 
> We could make only one function: is_valid, which returns as above, so
> always true for linestrings (because there is no harm if they
> self-intersect)

And this is what PostGIS does (means, this is what most GIS-specific
geometry users expect).

> and false for self-intersecting polygons.

Yes.

> Or maybe better, but less conformant: intersects(geometry) -> true for
> both linestring and polygon. This is an OGC method but specified for two
> geometries (intersects(a,b)) but we of course might make an overload for
> one, meaning self-intersecting, and one for a container of geometries,
> meaning that at least one pair of the container intersects.
> Actually this is much better because is_valid has also other purposes
> (e.g. nonclosed polygons)

Sure, good idea.

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org