Re: [boost] [Itl] Review

Subject: Re: [boost] [Itl] Review
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-02-23 18:06:27

Phil Endecott wrote:
> I was hoping to find that this library was an implementation of an
> interval tree.  But it is not: it is built on top of normal
> standard-library containers.  The implementation used can find the
> intervals that overlap a point in O(M + log N) time, but to do so it
> needs worst-case O(N^2) space and I think it needs O(N^2 log N) time
> to 
> build that structure.

Oddly enough I had exactly that data structure (extended to 2D for rectangle query) in an old version of my library prior to boost submission.  I took it out because I didn't want to go through the work of making its interface sufficiently generic to meet boost standards.  Included in the work I didn't want to do was factoring out the 1D portion and exposing in interval based interface for it.  I don't use the interval tree for my sweepline data structure because a std::map actually works better for sweepline when you store the end points of intervals as the key as opposed to the intervals themselves.  We had a failed boost summer of code project that didn't produce a good 2D version of the same data structure and the Boost.Geometry library has promised to include this same data structure, but by working with the summer of code author, apparently.

I would be happy to work with Joachim to add interval set operations and interval tree, plus the extension to 2D for rectangle query as an extension of my library.  Since my library already provides an interval concept it is, perhaps, a better foundation for this extension than Boost.Geometry.  I use extension here in a different sense of the word than Boost.GIL and Boost.Geometry extensions.  Interval set operations would not be second class features, but rather a part of the core library.  Many of the utility functions on intervals are already implemented for my interval concept.  I also understand both the interval tree data structures and the algorithms required for optimally computing interval set operations.  I have some extensive experience with the optimal interval set operation algorithm in the internal implementation of my sweepline algorithms for polygon set operations.  I can help with design of interfaces, provide some code for the interval tree and 2D extension and guidance on which algorithms are needed for interval set operations and where to provide abstractions to simplify their implementation.  Rather than as a large block of work this extension can be implemented piecemeal over time and would not require full review by boost but only my own review in the same manner that I can add features to the library myself as its maintainer without the need for full review for each one.  

I am on good terms with Joachim and I think we could work productively together.  I hope he will not take it amiss that I make this offer on the list and not privately.  There are a few sticky issues related to interval sets with a domain type that wouldn't normally be a legal coordinate type for my library.  Please remember that integer coordinate type is a requirement of my general polygon set operations algorithm, not of the library in general or the way its interfaces are defined.  I believe that these issues with domain types that don't map well to my coordinate concept can be overcome. (Lack of std::numeric_limits<std::string>::max() { return std::string(char(127)); } and so forth.)  Obviously a polygon set operation can never work with a coordinate of type string (actually Manhattan polygon set operations could, but not 45-degree or general), but that doesn't mean we can't use string as a coordinate type when instantiating 1D data structures and algorithms or even 2D data structures and algorithms that don't require arithmetic.  I think that would improve my library and make it more generic.  It sounds like an interesting challenge at least.

Regards,
Luke