Re: [boost] Geometry and spatial indexes, my opinion

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2008-10-08 21:53:55

Federico J. Fernández wrote:

> - You are able to find all elements within a certain range, if you mean by
> range a box. Or you can use a box and then refine the result filtering out
> the elements that are not in your area.

I meant it in a more abstract way. Usually a range is defined by a 
circle (rather than a box), but it could also be an area defined 
arbitrarily, so why not make it work with any geometrical object, using 
geometry::intersect and geometry::within in place of your overlap function?
Maybe it would be more practical if geometry provided an overlap 
(not-completely-within) test function. Maybe having a search where you 
search for elements that are completely within an area is interesting 
too? In that case you might as well parameterize the criteria.

> - About "Being able to index arbitrary objects and not just points". You can
> insert the envelopes of arbitrary geometries and a pointer to the real
> object as the data. Maybe it's not the best interface to do this, but a lot
> of libraries (i.e. GEOS) use this approach.

Which I can only do with R-trees and not Quadtrees, if I understand 
correctly.
It will still lead to approximations when computing distances and the 
like though, the actual object may be more far away than its minimal 
axis-aligned bounding box and thus the nearest neighbor search might 
return wrong results.