[geos-devel] QuadTree indexing

[Martin Davis]

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.
 
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).
 
Note that STRtree is usually faster than QuadTree.
 
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.
 
 
 
Martin Davis, Senior Technical Architect
Vivid Solutions Inc.      www.vividsolutions.com
Suite #1A-2328 Government Street Victoria, B.C. V8T 5G5
Phone: (250) 385 6040 - Local 308 Fax: (250) 385 6046

	-----Original Message-----
	From: geos-devel-bounces at geos.refractions.net
[mailto:geos-devel-bounces at geos.refractions.net] On Behalf Of George
Ionescu
	Sent: February 19, 2006 12:56 AM
	To: geos-devel at geos.refractions.net
	Subject: [geos-devel] QuadTree indexing
	
	
	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/20060220/77cae64d/attachment.html