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

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-10-07 19:36:09

--------------------------------------------------
From: "Mathias Gaunard" <mathias.gaunard_at_[hidden]>
Sent: Tuesday, October 07, 2008 5:52 PM
To: <boost_at_[hidden]>
Subject: [boost] Geometry and spatial indexes, my opinion

> Hi,
>
> Wanting to code a simple 3D virtual world, I looked into the recent 
> spatial indexes SOC work, which depends on the proposed geometry library.
>
> I have to admit I was fairly disappointed.
> So I'm going to put some critics, some quite harsh maybe, along with some 
> ramblings about what I would have liked to have.
> Note that I am no geometry or space indexing expert, so what I say may be 
> perfectly silly.
>
> For starters, I think those libraries should be dimension agnostic and 
> generic. Geometry not only has a strong 2D bias, but the documentation 
> also says geometry::box only works with point_xy (and point_ll).
> Since it is used everywhere in spatial index, that means it's unusable on 
> 3D.
>

Hi Mathias,

I just wanted to say something here about dimensional agnosticism. I don't 
think this is necessarily the way to go. There are a couple of reasons that 
I say this. The more trivial point is that higher than 3D geometry isn't 
likely to be supported and isn't of much practical use anyway. The second 
point is on the basis of coordinate frameworks. While I agree that any 
library shouldn't necessarily be limited to 2D, I don't think that you 
should lose the notions of what type of coordinate frame you are working in. 
So while you may be able to have 0, 1, or 2 to describe agnostically the 
dimension in the framework you want, the descriptions of what those 
dimensions are is lost. For example, you may have an algorithm which is 
designed to work in Cartesian coordinates in 2D (or 3D). You may have 
another algorithm which requires points in Polar (Spherical) coordinates. 
Another might want cylindrical coordinates to be optimal. Then there are 
algorithms which require translation of points into parametric coordinates 
to perform some logic optimally. If you have points which are agnostic to 
dimension, how can you distinguish 0,1,2 from x,y,z or r, theta, phi? The 
constraints imposed by these concepts are rather that when given a point of 
some dimensionality you need to be able to determine the type of coordinate 
frame that the point is describing. I've been working on a generative 
geometry library which includes support for these distinctions via 
conceptually enforced interfaces and traits.

> The geometry documentation doesn't clearly state what a geometry::box is. 
> Is it (assuming 2D) any rectangle or only axis-aligned rectangles?
> In case it is just any rectangle, it mind be interesting to introduce a 
> new type for axis-aligned ones, which can always be defined from two 
> points whatever the dimension (well, at least it seems enough for 3D, I'm 
> not good at projecting in other dimensions to see if that'd work).
> I suppose the spatial index interface expects axis-aligned boxes, so it's 
> fairly important to clarify what we're talking about.
>
> Apart from that, there is also lots of point_xy-dependent code in spatial 
> indexes. Also the quadtree implementation isn't dimension agnostic in 
> particular (it should have 2^n children nodes, and not 4).
> I don't really get why it uses shared_ptr everywhere either (is it 
> supposed to support COW or something?)
>
> I don't really get what boost::spatial_index::spatial_index is for. It 
> does nothing but forward everything to the last template parameter.
>
> Instead of writing
> boost::spatial_index::spatial_index<
>     point_type, value_type,
>     boost::spatial_index::rtree<point_type, value_type>
> > index(args...);
>
> I might as well write
> boost::spatial_index::rtree<point_type, value_type> index(args...);
>
> Also, I think the spatial indexes do not provide enough operations. The 
> only things they allow is putting point => value pairs, retrieving the 
> value associated to a point in O(log n) time (I assume, complexity is not 
> documented), and finding all values within a certain box (in O(log n) 
> too?).
> Many things one typically wants to do with spatial indexes are not 
> possible:
> - Iterate all (points, value) pairs in the index
> - Find the element closest (or k-closest) to some point in space or other 
> element.
> - Find all elements within a certain range of some point in space or other 
> element
> - Find the elements that intersect with a given object (ray tracing, for 
> example, searches for an element that intersects with a ray and that is 
> the closest to its source)
> - Consider only a part of the indexed space (e.g. an area delimited by a 
> range/sphere or box)
> - Being able to index arbitrary objects and not just points
> - Traverse the spatial index as a tree
>
> I believe there is no need to clutter the interface with a lot of 
> functions, most algorithms can be implemented generically as free 
> functions.
> Giving a read-only tree interface to all spatial indexes ought to be 
> enough to implement all algorithms. A spatial index, after all (correct me 
> if I'm wrong), is nothing else but a tree that partitions space, where 
> every node defines a partition of space that includes all of its children 
> (which might overlap or not). Subtrees should be full-fledged spatial 
> indexes (so that I can perform a search in a subtree), albeit read-only.
> Apart from that they should allow insertion and removal of object => value 
> pairs.
>
> Quadtrees and r-trees should be fairly easy to work with: they both 
> partition space into axis-aligned boxes (which are even cubes in 
> quadtrees).
>
> As for allowing all kinds of objects to be stored instead of just points, 
> that should be possible by using generic distance and intersection 
> functions.
> The real difference is that the same object could eventually be in 
> multiple places in the tree, because it spans over multiple space 
> partitions. Whenever you put an object in the tree or split a partition, 
> however, it would be necessary to calculate in which partitions to put the 
> object, whereas with points you only have to find the one partition.
>
> Of course, some cases can be specialized and optimized, like axis-aligned 
> boxes in a R-tree, which can directly be used as partitions and thus never 
> span across multiple ones.
> I find it weird having a different interface for R-trees and Quadtrees. 
> Indeed, one can only put points in a quadtree while in a r-tree you can 
> put boxes as well. A generic approach allowing to put any object with 
> boxes specialized seems like a better approach to me.
>
> About geometry, I think there should be more basic objects.
> While it is true polygons and multipolygons (polyhedrons) are enough to 
> represent everything in 3D space, having rays, segments, triangles, quads, 
> circles, spheres, squares, rectangles, cubes, cuboids (boxes), planes, 
> half-planes and more, with ability to compute all intersections and 
> distances, would be the most practical thing for 3D development.
> I do not know how to organize this in a really dimension-agnostic manner, 
> however.

This certainly makes sense, though I think starting with points, segments 
and polylines/polygons give sufficient primitives to do most basic geometry 
operations. These could of course be specialized into classes as you have 
described.

>
> In a nutshell, I think the spatial indexes design and how geometry can 
> help it ought to be discussed.
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>