<!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>
<DIV><SPAN class=260281616-03052005><FONT face=Arial color=#0000ff size=2>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.</FONT></SPAN></DIV>
<DIV> </DIV>
<DIV> </DIV>
<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>Martin
Davis<BR><B>Sent:</B> May 3, 2005 8:52 AM<BR><B>To:</B> GEOS Development
List<BR><B>Cc:</B> Kevin Wiebe<BR><B>Subject:</B> RE: [geos-devel] How robust
is GEOS?<BR><BR></FONT></DIV>
<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></BLOCKQUOTE></BODY></HTML>