Re: [boost] Interval Trees & ICL

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 [3] 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.

Hi Phil,

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.

Best regards,
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de