[geos-devel] QuadTree indexing

[George Ionescu]

Hello all geos developers,
I'm quite new with geos so please be gentle.
 
I'm trying to use geos library to perform spatial queries.
 
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?). 
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:
 
typedef std::vector<void*> VoidEmptyVec;
geos::Quadtree tree;
 
geos::Envelope* env = new geos::Envelope(10, 30, 10, 30);
tree.insert(env, env);
geos::Envelope* envQuery = new geos::Envelope(0, 4, 0, 4);
VoidEmptyVec* queryResults = tree.query(envQuery);
if (!queryResults->empty()) {
geos::Envelope* envResult = (geos::Envelope*)*queryResults->begin();
}
 
To my surprise, the tree finds the first Envelope (10, 30, 10, 30) as
overlapping the query Envelope (0, 4, 0, 4) !
Is there something I'm missing here? The comment from geos::Quadtree::query
states 
 
vector<void*>*
Quadtree::query(const Envelope *searchEnv)
{
 /*
  * the items that are matched are the items in quads which
  * overlap the search envelope
  */
 
So shouldn't the query method find the envelopes which overlap? This is
definitively not true in my example.
 
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?
 
3. Are there indexes which could be used to find the envelopes which contain
a given point P?
 
Thanking for your answers,
George.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/geos-devel/attachments/20060219/41107798/attachment.html