Boost logo

Boost :

From: Reid Sweatman (reid_of_diamonds_at_[hidden])
Date: 2002-01-01 03:13:14

Thanks for the book ref. These structures come up a lot in 3D
collision-detection algorithms. I always rolled my own, but would be glad
to see them in Boost.


> -----Original Message-----
> From: Beman Dawes [mailto:bdawes_at_[hidden]]
> Sent: Monday, December 31, 2001 2:48 PM
> To: boost_at_[hidden]; boost_at_[hidden]
> Subject: Re: [boost] Re: new component, extent_set<>
> At 10:07 AM 12/31/2001, David Abrahams wrote:
> >A data structure I've needed (and used) from time to time which
> I presume
> >is
> >different from everything described so far in this thread is an
> "interval
> >tree". An interval tree is an RB-tree of intervals sorted on the start
> >position of each interval, where each node contains an
> additional record
> of
> >the maximum end position of all intervals in the subtree rooted at that
> >node. The intervals are allowed to overlap. It is possible to
> efficiently
> >enumerate all intervals in the tree that overlap any given interval, for
> >example.
> That sounds like a one-dimensional case of the general
> n-dimensional R-tree
> (or R*tree or R+tree refinements) used for spatial search. Although I've
> never used anything other than a B-tree, I'm pretty sure you can
> implement
> an R-/*/+tree on top of any kind of binary or multi-way underlying tree
> structure.
> By the way, an ordering other than on start position can have
> dramatically
> better performance (at least for multi-dimensional cases).
> See the book Spatial Databases by Rigaux, Scholl, and Voisard, beginning
> around page 238. ISBN 1-55860-588-6.
> --Beman
> Info: Send unsubscribe requests to:

Your use of Yahoo! Groups is subject to

Boost list run by bdawes at, gregod at, cpdaniel at, john at