[geos-devel] How robust is GEOS?

[Martin Davis]

By the way, I'll also point out that I architected JTS so that the
algorithms which are potentially problematic are all modularized.  If
there are better algorithms for performing any of the operations below,
it should be easy to just plug them in to the code.
 
 
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 Martin
Davis
	Sent: May 3, 2005 8:52 AM
	To: GEOS Development List
	Cc: Kevin Wiebe
	Subject: RE: [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?

	 

	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/811c751d/attachment.html