2D interval tree using 1D ones

Question

I'm using the C# interval tree collection class class from here http://intervaltree.codeplex.com/SourceControl/list/changesets -> right hand side -> download.

I need to get intervals from the collection that overlap given ones. This seems easy with .Get(left, right). However I need 2D intervals, apparently this is not to hard starting with 1D ones.

I heard somthing about it being done with nesting.

IntervalTree<IntervalTree<stored_type, float>, float> intervals;

However then again this dosn't seem to make sence. Appart from anything else moving intervals seems expensive and working out where to add them seems complicated.

IntervalTree<stored_type, float> intervals_x;
IntervalTree<stored_type, float> intervals_y;

I'm not sure if I did this though how it would perform Get(left, right, upper, lower). Presumably an instance of stored_type would exist and belong to both sets, however would there be issues if the sets rearanged themselves as things changed?

However it's done the .Get(...) returns a List<stored_type>. There will be far less than is in the intervals list but still a great deal of items in this List that will need processing quickly, but independently, they don't need an order. Could I convert the List into another collection such as a LinkedList or a HashSet to traverse more quickly than just traversing it?

edit:

So perhaps something like the following.

class interval_tree_2D
{
    private IntervalTree<stored_type, float> x =
        new IntervalTree<stored_type, float>();
    private IntervalTree<stored_type, float> y =
        new IntervalTree<stored_type, float>();

    public void add(stored_type n,
        float left, float right, float lower, float upper)
    {
        intervals_x.AddInterval(left, right, n);
        intervals_y.AddInterval(upper, lower, n);
    }

    public HashSet<stored_type> get(
        float left, float right, float lower, float upper)
    {
        var i1 = x.Get(left, right);
        var i2 = y.Get(lower, upper);
        var i3 = i1.to_HashSet();
        var i4 = i2.to_HashSet();
        return i3.union(i4);
    }
}

Except that there is no to_HashSet() so I'm having to use a double loop to find out where the two sets intersect. Also the x and y of each element is hard coded.

I'd really like some feedback. Before I was using a HashSet and a foreach to step through it, comparing each element for overlapping the desired bounds.

Answer 1

It seems, you need not an implementation of not a Interval Tree but an KD-Tree data structure. KD-Trees enable O(log N) search time for low dimensions, if I remember correctly.

A quick google returned many results, for example: http://www.codeproject.com/KB/architecture/KDTree.aspx You can go and check it to see if it fits your needs, or find another implementation if not.