2D интервальное дерево с использованием одномерных - PullRequest
Новая
       39

2D интервальное дерево с использованием одномерных

1 голос
/ 08 января 2012

Я использую класс класса дерева интервалов C # отсюда http://intervaltree.codeplex.com/SourceControl/list/changesets -> правая сторона -> загрузка.

Мне нужно получить интервалы из коллекции, которые перекрывают заданные.Это кажется простым с .Get(left, right).Однако мне нужны 2D-интервалы, по-видимому, это не так сложно, начиная с 1-мерных.

Я слышал что-то о том, что это делается с помощью вложенности. 

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

Однако, опять же, это не кажетсяиметь смысл.Appart из всего остального, движущиеся интервалы, кажется дорогим, и разработка того, где их добавить, кажется сложной. 

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

Я не уверен, что я сделал это, хотя как он будет работать Get(left, right, upper, lower).Предположительно экземпляр сохраненного_типа существовал бы и принадлежал обоим наборам, однако возникли бы проблемы, если бы наборы перегруппировывались при изменении вещей?

Однако это сделано, .Get(...) возвращает List<stored_type>.В списке интервалов будет гораздо меньше, чем в списке интервалов, но в этом List будет еще много элементов, которые нужно будет быстро обработать, но независимо от этого им не нужен заказ.Могу ли я преобразовать List в другую коллекцию, такую ​​как LinkedList или HashSet, чтобы проходить быстрее, чем просто обходить его?

edit:

Так что, возможно, что-то вроде следующего. 

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);
    }
}

За исключением того, что нет to_HashSet (), поэтому мне приходится использовать двойной цикл, чтобы выяснить, где пересекаются два набора.Кроме того, x и y каждого элемента жестко запрограммированы.

Мне бы очень хотелось получить обратную связь.Прежде, чем я использовал HashSet и foreach, чтобы пройти через него, сравнивая каждый элемент для перекрытия желаемых границ.

1 Ответ

2 голосов
/ 09 января 2012

Кажется, вам нужна не реализация дерева интервалов, а структуры данных KD-дерева.KD-деревья позволяют O (log N) время поиска для низких размеров, если я правильно помню.

Быстрый Google вернул много результатов, например: http://www.codeproject.com/KB/architecture/KDTree.aspx Вы можете пойти и проверить его, чтобы увидеть, соответствует ли он вашим потребностям, или найти другую реализацию, если нет.

...