RE: [boost] Re: new component, extent_set<>

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.

Reid

> -----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: http://www.boost.org  Send unsubscribe requests to:
<mailto:boost-unsubscribe_at_[hidden]>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/