<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML xmlns="http://www.w3.org/TR/REC-html40" xmlns:o =
"urn:schemas-microsoft-com:office:office" xmlns:w =
"urn:schemas-microsoft-com:office:word"><HEAD><TITLE>Message</TITLE>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2800.1276" name=GENERATOR>
<STYLE>@page Section1 {size: 612.0pt 792.0pt; margin: 72.0pt 90.0pt 72.0pt 90.0pt; }
P.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"
}
LI.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"
}
DIV.MsoNormal {
FONT-SIZE: 12pt; MARGIN: 0cm 0cm 0pt; FONT-FAMILY: "Times New Roman"
}
A:link {
COLOR: blue; TEXT-DECORATION: underline
}
SPAN.MsoHyperlink {
COLOR: blue; TEXT-DECORATION: underline
}
A:visited {
COLOR: purple; TEXT-DECORATION: underline
}
SPAN.MsoHyperlinkFollowed {
COLOR: purple; TEXT-DECORATION: underline
}
SPAN.EmailStyle17 {
COLOR: windowtext; FONT-FAMILY: Arial; mso-style-type: personal-compose
}
DIV.Section1 {
page: Section1
}
</STYLE>
</HEAD>
<BODY lang=EN-US vLink=purple link=blue>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><SPAN class=906174415-03052005>>
</SPAN>I’m asking for advice here: What is the most robust (numerically
stable) way to use GEOS? What are its limitations?</SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"></SPAN> </P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>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: </SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>- testing the relative orientation of 3
points</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>- computing the intersection point of two segments (the
case you've raised)</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>- computing the intersected arrangement of a set of
linestrings (the noded problem)</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005></SPAN></o:p></SPAN> </P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>There's probably some others - feel free to provide
others.</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005></SPAN></o:p></SPAN> </P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>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).</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005></SPAN></o:p></SPAN> </P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005>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.</SPAN></o:p></SPAN></P>
<P class=MsoNormal><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005></SPAN></o:p></SPAN><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p><SPAN
class=906174415-03052005></SPAN></o:p></SPAN><FONT face=Arial color=#0000ff
size=2><SPAN class=906174415-03052005></SPAN></FONT> </P>
<P class=MsoNormal><FONT face=Arial color=#0000ff size=2><SPAN
class=906174415-03052005>Martin</SPAN></FONT></P>
<DIV align=center><FONT face=Arial size=2><STRONG>Martin Davis, Senior Technical
Architect</STRONG><BR><STRONG><FONT color=#0000ff>Vivid Solutions
Inc.
<I>www.vividsolutions.com</I></FONT></STRONG><BR></FONT><EM><FONT face=Arial
size=2>Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5<BR>Phone: (250)
385 6040 - Local 308 Fax: (250) 385 6046</FONT></EM></DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV></DIV>
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left><FONT
face=Tahoma size=2>-----Original Message-----<BR><B>From:</B>
geos-devel-bounces@geos.refractions.net
[mailto:geos-devel-bounces@geos.refractions.net] <B>On Behalf Of </B>Kevin
Wiebe<BR><B>Sent:</B> May 3, 2005 7:00 AM<BR><B>To:</B>
geos-devel@geos.refractions.net<BR><B>Subject:</B> [geos-devel] How robust is
GEOS?<BR><BR></FONT></DIV>
<DIV class=Section1>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">I’m asking for advice here:
What is the most robust (numerically stable) way to use GEOS? What are
its limitations?<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">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.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Here is a concrete example from
real customer data:<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">I have created two simple 2-point
LINEs and used the GEOS call to get the spot where they
intersect:<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">point =
lineA.intersection(lineB);<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">lineA = from
(2089426.5233462777,1180182.3877339689) to
(2085646.6891757075,1195618.7333999649)<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">lineB = from
(1889281.8148903656,1997547.0560044837) to
(2259977.3672235999,483675.17050843034)<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">the intersection point I get back
is this:<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">point =
(2097408.2633752143,1144595.8008114607)<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">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.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">JTS returns the same
result.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Depending on your explanations for
this I may have some technical advice.<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">Thanks for your
comments,<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial">-Kevin-<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'">----------------------------------------------------------------<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'"> Kevin
Wiebe Safe Software
Inc.
kevin@safe.com<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'">
Senior Surrey, BC,
CANADA phone: (604)
501-9985<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'">
Developer
http://www.safe.com fax: (604)
501-9965<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'">----------------------------------------------------------------<o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'"><o:p> </o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face="Courier New" size=2><SPAN
style="FONT-SIZE: 10pt; FONT-FAMILY: 'Courier New'"> <o:p></o:p></SPAN></FONT></P>
<P class=MsoNormal><FONT face=Arial size=2><SPAN lang=EN-CA
style="FONT-SIZE: 10pt; FONT-FAMILY: Arial"><o:p> </o:p></SPAN></FONT></P></DIV></BLOCKQUOTE></BODY></HTML>