Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk