Re: [Boost-users] [multi_index] 2D/3D range seaching

Thanks for the input. I currently use kd-trees to do such range searches. Its fairly efficient, I think 2D worst case range search is around O(sqrt(N)) assuming its perfectly balanced... its slightly worse for a random tree. Maybe theres interest in a k-D set container implemented with such a structure (although theres probably more efficient methods, kd-trees are fairly simple). Chris On 5/1/07, "JOAQUIN LOPEZ MU?Z" wrote:

----- Mensaje original ----- De: Chris Fairles Fecha: Lunes, Abril 30, 2007 9:44 pm Asunto: [Boost-users] [multi_index] 2D/3D range seaching Para: boost-users@lists.boost.org

...

At first glance, it looked like the multi_index lib (perhaps combined with the range lib) might provide a convenient way to search for ranges of two+ indicies. For example, points. You have a grid of random points and you want a pair of iterators that contain all points within the cube (x1,y1,z1) and (x2,y2,z2) .

I made a multi_index container with a composite key containing all three coords contained within a point class.

struct point { int x, y ,z; };

struct coords_key : composite_key< point, member, member, member

...

{};

struct coords{};

typedef multi_index_container< point, indexed_by< ordered_non_unique

...

point_set;

int main() { point_set p;

p.insert(point(1,2,2)); p.insert(point(2,3,1)); p.insert(point(1,2,3)); p.insert(point(10,3,2));

point_set::iterator it = p.lower_bound(make_tuple(1,1,1)); point_set::iterator it2 = p.upper_bound(make_tuple(3,3,3)); return 0; }

it would be great if [it, it2] contained the first four points, but this is not the case. If I run this code, it == it2 == the first point.

Am i barking up the wrong tree? Or is this doable.

Hello Chris,

I'm afraid you can't tweak a multi_index_container or any other STL-compatible container so that their associated ranges are actually prisms in 2- or 3-D: basically, ranges and prisms do not behave the same. For instance, given three iterators it1,it2,it3, the following hold of ranges:

[it1,it3) is the disjoint union of [it1,it2) and [it2,it3),

which is not true of prisms (in 2 or more dimensions), as you can easily visualize.

So, you have to resort to more elaborate data structures or algorithms in order to do what you want. A crude way to get the points in the rectangle [x1,y1,x2,y2) with B.MI could be coded as follows (done in 2D for simplicity of exposition):

struct point { int x, y; };

struct coords_xy_key : composite_key< point, member, member

...

{};

struct coords_yx_key : composite_key< point, member, member

...

{};

struct coords_xy{}; struct coords_yx{};

typedef multi_index_container< point, indexed_by< ordered_non_unique, coords_key_xy>, ordered_non_unique, coords_key_yx>

...

point_set;

templatex::type ityx1= p.get().lower_bound(it->x,y1); point_set::index_iterator::type ityx2= p.get().upper_bound(it->x,y2); // [ityx1,ityx2) is the vertical segment of the rectangle // with x-coordinate== it->x.

while(ityx1!=ityx2)f(*ityx1++);

// next non-empty x-coordinate it=p.upper_bound(make_tuple(it->x)); } }

This has not been compiled and will surely contain some sintax erros, but you get the idea. Of course, this is not terribly efficient, and if you want maximum performance you should probably go to dedicated spatial indexing data structures like quadtress and octrees.

HTH,

Joaquín M López Muñoz Telefónica, Investigación y Desarrollo _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users