Re: [multi_index] 2D/3D range seaching
Chris Fairles <chris.fairles <at> gmail.com>
2007-05-01 12:13:14 GMT
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> tid.es> wrote:
> ----- Mensaje original -----
> De: Chris Fairles <chris.fairles <at> gmail.com>
> Fecha: Lunes, Abril 30, 2007 9:44 pm
> Asunto: [Boost-users] [multi_index] 2D/3D range seaching
> Para: boost-users <at> 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<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> lists.boost.org
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
RSS Feed