Subject: Re: [boost] Interval Trees & ICL
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-12-17 16:31:27
2010/12/17 Bruce Adams <tortoise_74_at_[hidden]>:
> ----- Original Message ----
>> From: Joachim Faulhaber <afojgo_at_[hidden]>
>> To: boost_at_[hidden]
>> Sent: Fri, December 17, 2010 12:32:48 AM
>> Subject: Re: [boost] Interval Trees & ICL
>> 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
>> > 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),
>> > 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.
>> > 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.
After I have spent some more time studying your proposal, I still
think it is a very smart method and a good alternative to the
"classical" interval tree implementation suggested by Dave.
The restriction imposed by bit-interleaving on the applicable element
types is justified if the data structure gains efficiency. Using meta
programming we can choose the best implementation dependent on the
element type. More unpleasant is the fact that an important part of
the method, the efficient search of the z-ordered values within the
quarter-plane defined by the query interval seems to be protected by a
software patent as Bruce pointed out. But may be you have a different
implementation that circumvents this obstacle.
> That is an interesting idea. However, I see the method (or at least some
> of it) are covered by a patent. Presumably that could affect its adoption into
> I'm broadly against software patents
-- 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