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

From: Chris Fairles (chris.fairles_at_[hidden])
Date: 2007-05-01 08:13:14

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" <joaquin_at_[hidden]> wrote:
> ----- 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>