<!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.2900.2802" name=GENERATOR></HEAD>
<BODY>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff size=2>The
way Quadtree actually works is that it returns a candidate set of items whose
Envelopes *may* intersect the query envelope. The candidate set is
normally much smaller than the entire set of objects in the index. You
need to check for actual intersection in a subsequent step.</FONT></SPAN></DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff size=2>The
reason this was done is to move the envelope intersection check outside of the
index, to allow the caller to decide whether or not it needs to perform
it. (For instance, the caller may simply be calling a further function on
the returned items which does the envelope check anyway - in which case this
avoids a redundant check).</FONT></SPAN></DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff size=2>Note
that STRtree is usually faster than QuadTree.</FONT></SPAN></DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=299493117-20022006></SPAN><SPAN class=299493117-20022006><FONT
face=Arial color=#0000ff size=2>You have the right approach for GEOS.
There may be other indexes which make point-in-envelope queries faster, but they
aren't in GEOS.</FONT></SPAN></DIV>
<DIV><SPAN class=299493117-20022006><FONT face=Arial color=#0000ff
size=2></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>George
Ionescu<BR><B>Sent:</B> February 19, 2006 12:56 AM<BR><B>To:</B>
geos-devel@geos.refractions.net<BR><B>Subject:</B> [geos-devel] QuadTree
indexing<BR><BR></FONT></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>Hello all geos
developers,</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>I'm quite new with
geos so please be gentle.</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>I'm trying to use
geos library to perform spatial queries.</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>1. I have a large
number of line segments (around 100.000) and I'm trying to do hit-testing
(e.g. does the point x,y falls on one of the lines with a given
tollerance?). </FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>For this, I
thought of creating an Envelope for each line segment, adding them to a
QuadTree index and then construct another Envelope (x-tollerance,
x+tollerance, y-tollerance, y+tollerance) and query the index to find all
overlapping polygons. From there, I'll compute the distance from my point
to each of the lines and take the shortest one. To be short, I have
something like this:</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>typedef
std::vector<void*> VoidEmptyVec;</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>geos::Quadtree
tree;</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN><SPAN
class=234571708-19022006><FONT face=Arial size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>geos::Envelope*
env = new geos::Envelope(10, 30, 10, 30);</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>tree.insert(env,
env);</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>
<DIV><SPAN class=234571708-19022006><FONT face=Arial size=2>geos::Envelope*
envQuery = new geos::Envelope(0, 4, 0, 4);</FONT></SPAN></DIV>
<DIV><SPAN class=234571708-19022006>VoidEmptyVec* queryResults =
tree.query(envQuery);</SPAN></DIV>
<DIV><SPAN class=234571708-19022006>if (!queryResults->empty())
{</SPAN></DIV>
<DIV><SPAN class=234571708-19022006>geos::Envelope* envResult =
(geos::Envelope*)*queryResults->begin();</SPAN></DIV>
<DIV><SPAN class=234571708-19022006>}</SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006>To my surprise, the tree finds the first
Envelope (10, 30, 10, 30) as overlapping the query Envelope (0, 4, 0, 4)
!</SPAN></DIV>
<DIV><SPAN class=234571708-19022006>Is there something I'm missing here? The
comment from geos::Quadtree::query states </SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN
class=234571708-19022006>vector<void*>*<BR>Quadtree::query(const
Envelope *searchEnv)<BR>{<BR> /*<BR> * the items that are matched
are the items in quads which<BR> * overlap the search envelope<BR>
*/</SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006>So shouldn't the query method find the
envelopes which overlap? This is definitively not true in my
example.</SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006>2. If it's me who doesn't understand how
things work, given a set of N envelopes, what is the index I should use
to find the envelopes which overlap a given envelope E?</SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006>3. Are there indexes which could be used
to find the envelopes which contain a given point P?</SPAN></DIV>
<DIV><SPAN class=234571708-19022006></SPAN> </DIV>
<DIV><SPAN class=234571708-19022006>Thanking for your answers,</SPAN></DIV>
<DIV><SPAN
class=234571708-19022006>George.</SPAN></DIV></FONT></SPAN></DIV></BLOCKQUOTE></BODY></HTML>