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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2007-05-01 07:53:53

----- Mensaje original -----
De: Chris Fairles <chris.fairles_at_[hidden]>
Fecha: Lunes, Abril 30, 2007 9:44 pm
Asunto: [Boost-users] [multi_index] 2D/3D range seaching
Para: boost-users_at_[hidden]

> 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<point,int,x>,
>  member<point,int,y>,
>  member<point,int,z>
> >{};
> 
> struct coords{};
> 
> typedef multi_index_container<
>  point,
>  indexed_by<
>    ordered_non_unique<tag<coords>, coords_key>
> >
> > 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<point,int,x>,
    member<point,int,y>
  >{};

  struct coords_yx_key : composite_key<
    point,
    member<point,int,y>,
    member<point,int,x>
  >{};

  struct coords_xy{};
  struct coords_yx{};

  typedef multi_index_container<
    point,
    indexed_by<
      ordered_non_unique<tag<coords_xy>, coords_key_xy>,
      ordered_non_unique<tag<coords_yx>, coords_key_yx>
   >
  > point_set;

  template<typename F
  void for_each_in_rectangle(point x1,point y1,point x2,point y2,Fun f)
  {
    point_set::iterator it=p.lower_bound(make_tuple(x1));
    while(it!=p.end()&&it->x<x2){
      point_set::index_iterator<coords_key_yx>::type ityx1=
        p.get<coords_key_yx>().lower_bound(it->x,y1);
      point_set::index_iterator<coords_key_yx>::type ityx2=
        p.get<coords_key_yx>().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