<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Message</TITLE>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2800.1276" name=GENERATOR></HEAD>
<BODY>
<DIV><FONT face=Arial size=2><SPAN class=429572219-17092004>I keep hearing that
people find that using the PostGIS distance function is faster than using the
GEOS intersects() function. Does anyone know why this is? My
understanding of the PostGIS distance function is that it's a simple scan of all
linesegments, which is O(n^2). The GEOS code should be able to do better
than this. Of course, likely there's some overhead in the conversion to GEOS -
perhaps that's the source of the problem (for small to medium geometries,
anyway).</SPAN></FONT></DIV>
<DIV><FONT face=Arial size=2><SPAN
class=429572219-17092004></SPAN></FONT> </DIV>
<DIV><FONT face=Arial size=2><SPAN class=429572219-17092004>Is this still the
case for REALLY big geometries? If it really is just an copying overhead
thing, I would expect the difference to decrease as the input size gets bigger
(copying is O(n), which will get swamped by O(n^2) at some
point).</SPAN></FONT></DIV>
<DIV><FONT face=Arial size=2><SPAN
class=429572219-17092004></SPAN></FONT> </DIV>
<DIV><FONT face=Arial size=2><SPAN class=429572219-17092004>I'm just asking
because I'm curious if there's anything that can be done to speed up GEOS (both
for PostGIS and in general).</SPAN></FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><SPAN class=429572219-17092004><FONT face=Arial size=2>Also, if distance is
used heavily I wonder whether it's worth spending some time optimizing the
computation using indexing techniques?</FONT></SPAN></DIV>
<DIV><SPAN class=429572219-17092004><FONT face=Arial
size=2></FONT></SPAN> </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>
<DIV> </DIV></BODY></HTML>