[geos-devel] How robust is GEOS?

[Martin Davis]

> I'm asking for advice here:  What is the most robust (numerically
stable) way to use GEOS?  What are its limitations?

 

That's a bit hard to give a short answer to.  (In fact, the shortest
answer is probably in the code itself.)  Basically, JTS/GEOS is as
robust as I know how to make it.  There are a few obvious places where
robustness is an issue: 

- testing the relative orientation of 3 points

- computing the intersection point of two segments (the case you've
raised)

- computing the intersected arrangement of a set of linestrings (the
noded problem)

 

There's probably some others - feel free to provide others.

 

For each of these areas I have tried to obtain or develop a fully robust
or at least a high quality algorithm.  In the case of point orientation,
this reduces to evalutating the sign of a determinant, and there is some
good code provided by a group in France for doing this robustly.  For
noding, I have added snap rounding in the next version of JTS (although
I have not yet incorporated this into the geometry algorithms, since
there are some further issues to work out).

 

For the case of line segment intersection, I was aware that the code was
not robust and that there were some egregious failure cases.  But you've
found a real shocker!  If you have any ideas about how to make this more
robust, that would be great.  Feel free to post or call me to discuss.

 

Martin

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: geos-devel-bounces at geos.refractions.net
[mailto:geos-devel-bounces at geos.refractions.net] On Behalf Of Kevin
Wiebe
	Sent: May 3, 2005 7:00 AM
	To: geos-devel at geos.refractions.net
	Subject: [geos-devel] How robust is GEOS?
	
	

	I'm asking for advice here:  What is the most robust
(numerically stable) way to use GEOS?  What are its limitations?

	 

	For our purposes we need to use code that is both as fast and
accurate as possible.  As you probably know, when using a complex
algorithm sometimes even small inaccuracies in geometric computations
can compound into drastically incorrect results.

	 

	Here is a concrete example from real customer data:

	I have created two simple 2-point LINEs and used the GEOS call
to get the spot where they intersect:

	point = lineA.intersection(lineB);

	 

	lineA = from (2089426.5233462777,1180182.3877339689) to
(2085646.6891757075,1195618.7333999649)

	lineB = from (1889281.8148903656,1997547.0560044837) to
(2259977.3672235999,483675.17050843034)

	 

	the intersection point I get back is this:

	point = (2097408.2633752143,1144595.8008114607)

	 

	This point is a significant distance away from any part of
lineA.  If one were to place this intersection point between the start
and end points of lineA, the resulting line would look ridiculous.

	 

	JTS returns the same result.

	 

	Depending on your explanations for this I may have some
technical advice.

	 

	Thanks for your comments,

	-Kevin-

	 

	----------------------------------------------------------------

	 Kevin Wiebe     Safe Software Inc.              kevin at safe.com

	      Senior     Surrey, BC, CANADA       phone: (604) 501-9985

	   Developer     http://www.safe.com        fax: (604) 501-9965

	----------------------------------------------------------------

	 

	 

	 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20050503/f507872d/attachment.html