<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<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></BODY></HTML>