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

Question

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

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

Я слышал что-то об этом, сделанном с вложением.

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, чтобы проходить быстрее, чем просто проходить?

редактировать:

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

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, чтобы пройти через него, сравнивая каждый элемент для перекрытия желаемых границ.

Answer 1

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

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