[geos-devel] Geometry::relate checkNotGeometryCollection -unnecessary?

[Martin Davis]

There is a reason that check is in the code - it wasn't just added in frivously.  But it's a subtle issue. 

The short answer is that there are GC examples which cause the current JTS/GEOS code to break.  For instannce, try relating:

GEOMETRYCOLLECTION (POLYGON ((0 0, 120 0, 120 100, 0 100, 0 0)), 
  POLYGON ((0 180, 120 180, 60 99, 0 180)))

LINESTRING (60 140, 60 60) 

The problem is that there's some assumptions fairly deep in the code that polygons do not overlap.  The simply way around this is to union all the objects in the collection and then compute the relationship.  This is potentially a lot more expensive, but at least will work.  But there are further more subtle issues.

The first is that the OGC SFS does not define the semantics of relationships with GeometryCollection.  In particular, it doesn't say how to handle the case where the GC contains two polygons that overlap.  Is the portion of the polygon boundary that is inside the other polygon on the boundary of the GC or not?   According to the obvious interpretation (and currently implemented) of getBoundary(), it is.  But the "union" semantics for relate would say a point intersecting the "contained" boundary is in the interior of the GC.  

A knarlier problem is that using the algorithms currently in JTS/GEOS, it isn't possible to make the relate algorithm fully robust if GCs are allowed.  The problem is where a polygon vertex lies very close to an edge of another polygon.  JTS can robustly determine if the vertex is inside or outside or on the other polygon.  But it can't tell if a line which passes through the interior of both polygons and the vertex is wholely contained in the polygons (if they do touch) or is partially in the exterior of the polygons (if they don't touch).

One approach would be just to ignore these issues, and compute *some* answer even if it's technically wrong.  I didn't really like this approach, since it could conceivably cause unexpected inconsistencies to surface in some uses of the library.  So I've been procrastinating on addressing this issue, waiting until perhaps a better approach became apparent.  But I'm open to being convinced - or even bribed  8^)

Martin Davis, Senior Technical Architect
Vivid Solutions Inc.      www.vividsolutions.com
Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046


> -----Original Message-----
> From: Owen Gibbins [mailto:Owen.Gibbins at safe.com] 
> Sent: November 17, 2004 3:46 PM
> To: geos-devel at geos.refractions.net
> Subject: [geos-devel] Geometry::relate 
> checkNotGeometryCollection -unnecessary?
> 
> 
> Hi all,
> 
> I am working with making spatial comparisons between 
> geometries using GEOS, and ran into trouble when either or 
> both of the geometries were GeometryCollections.  I tracked 
> this down to the first two lines in Geometry::relate(const Geometry*):
> 
>  checkNotGeometryCollection(this);  checkNotGeometryCollection(other);
> 
> Can anyone tell me if this check is really necessary? I 
> commented out the two lines, and voilà! All my issues were 
> resolved.  The intersection matrix resulting from a 
> comparison between a GeometryCollection with another 
> GeometryCollection, or between a GeometryCollection and a 
> non-collection Geometry, makes sense in every test case I 
> have run so far.
> 
> If there is no good reason not to get rid of this check, 
> maybe someone would be so kind as to make this change.  I'm 
> having trouble getting CVS set up for the GEOS repository, 
> and I don't anticipate tinkering around much more with the 
> code anyway.
> 
> Thank you!
> 
> Owen Gibbins
> 
> --------------------------------------------------------------
> Owen Gibbins                             owen.gibbins at safe.com
> Developer, Safe Software Inc.            (604)501-9985 ext.210
> --------------------------------------------------------------
> _______________________________________________
> geos-devel mailing list
> geos-devel at geos.refractions.net 
> http://geos.refractions.net/mailman/listinfo/geos-devel
>