Subject: Re: [boost] Interval Trees & ICL
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-12-16 19:32:48
2010/12/16 Phil Endecott <spam_from_boost_dev_at_[hidden]>:
> My idea is to
> consider an interval (low,high) as a point in a 2D plain. Then, a query to
> find all of the intervals overlapping (a,b) is the same as the query to find
> all the points in the quarter-plane where low<b and high>a.
> Any 2D data structure could be used to store these (e.g. quadtrees etc), but
> the aim here is to adapt a 1D data structure. I have used the Z-curve
> method  to do this efficiently for some years now and it works well. The
> idea is that you bitwise-interleave the two values and use this as the key.
> You can then iterate over all points in a rectangle by iterating over all
> points in the 1D range between the interleaved bottom left and top right
> corner values.
I find your idea quite nifty and fascinating. The transformation from
intervals to 2D plane to z-curve ordering is quite powerful and opens
up new frames of thinking on the problem. I guess I need a little more
thinking time and intend to post another answer tomorrow.
-- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk