Какова хорошая структура данных для определения области, содержащей точку?

Я ищу структуру данных, которая поддерживает поиск, какая из «n» областей содержит точку «p». Я смотрел на Quadtree и R-деревья, но не думаю, что они подходят именно тому, что я ищу.

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

Наивный алгоритм, который я сейчас использую, состоит в том, чтобы просто проверить точку «p» по каждому измерению каждой прямоугольной области.

for(region in regionList):
    if(p.x > region.x1 && p.x < region.x2 && p.y > region.y1 && py < region.y2 && p.z > region.z1 && p.z < region.z2)
        return region
end

Это выполняется за время O (n), где n - количество регионов. Я хотел бы, чтобы поиск брал O (log n), как точка Quadtree для поиска 2d точек.


region data-structures point binary-tree quadtree
person Rovert Renchirk    schedule 05.02.2013    source источник
comment
Это выглядит многообещающе. cs.umd.edu/~hjs/multidimensional-book-flyer. pdf   -  person    schedule 06.02.2013
comment
Так как области не могут перекрываться, точка может быть в лучшем случае только в одной. Это заставляет ... вернуть, какая область наиболее сильно ограничивает точку. логическая невозможность. 1, и только 1 может ограничить точку.   -  person    schedule 07.02.2013
comment
Это приложение может очень хорошо использовать новые расширения SIMD с 16 128-битными регистрами для приложений 3D-графики.   -  person    schedule 09.02.2013

Ответы (2)


arrow_upward
0
arrow_downward

Я бы предложил QuadTree, который хранит регионы как дерево MX-CIF. По сути, это QuadTree, основанное на двух измерениях (x, y). Как только вы найдете подходящий узел, который содержит точку в терминах (x, y), вы можете проверить, содержит ли он точку во всех трех (x, y, z) измерениях.

Я сделал нечто подобное на Яве.

Вы также можете изучить Octree, которое представляет собой трехмерное QuadTree.

person Justin    schedule 05.02.2013
comment
Просто чтобы убедиться, что я правильно вас понимаю. Вы предлагаете мне проверить, находится ли точка в области xy, используя Quadtree, а затем просто независимо проверить, находится ли точка также в границах z этой области? Что произойдет, если у меня будет два региона, один над другим? Что вернет Quadtree? - person Rovert Renchirk; 06.02.2013
comment
Точка не может существовать в нескольких регионах, верно? Разве это не было частью постановки вашей проблемы? - person Justin; 06.02.2013
comment
Верно, но поскольку дерево MX-CIF проверяет, находится ли точка в пределах 2-го региона. Если у меня есть трехмерные области, то точка может находиться в проекциях двух трехмерных областей, но не в обеих этих областях. Если вы не имели в виду, что я адаптирую дерево MX-CIF к 3 измерениям, и в этом случае это должно сработать. - person Rovert Renchirk; 06.02.2013
comment
Точка может находиться в одном пространстве XY двух неперекрывающихся граничных прямоугольников, только если они занимают разное пространство Z. Над другим подразумевается другое пространство Y, а не Z-пространство. Я думаю, вы имеете в виду позади другого - в этом случае у них будет то же пространство XY, но другое пространство Z, поэтому предложение Джастина работает нормально. - person ; 07.02.2013
comment
В любом случае только один прямоугольник, если таковой имеется, может содержать точку, поэтому на вопрос о том, какой именно прямоугольник ограничивает точку наиболее сильно, нельзя ответить с помощью предложенной вами конструкции. Возможно, вам нужно более внимательно изучить определение вашей проблемы. - person ; 07.02.2013
comment
@RocketRoy Единственным недостатком такой структуры является то, что она в конечном итоге сломается, если все ваши регионы будут иметь одинаковые значения (x, y), но разные значения (z). Итак, по сути, это будет список, который является O (n), но если вы знаете, что этого, скорее всего, не произойдет, этого должно быть достаточно. - person Justin; 07.02.2013
comment
@Justin, согласен. Если вы прочитаете мои удаленные комментарии, вы вспомните, что я использовал деревья с указателями Right, Left и Next_Dim. Когда я искал в дереве измерение X, я перешел к корню Y, а после разрешения Y - к корню Z. Серьезно сложный фрагмент кода для написания, если вы хотите, чтобы он был самодостаточным. балансировка, но разрешит любое количество измерений - 28 в моем случае. Также возможно, чтобы отдельные деревья использовали одни и те же верхние узлы, поэтому они занимают ту же память, что и узлы, при условии, что у вас есть ограничение на глубину / размеры. - person ; 09.02.2013
comment
@ Джастин, разве это не похоже на проблему населения сети? Отсутствие перекрытия требует прямоугольников одинаковой формы, иначе в ограниченном пространстве появятся большие промежутки. - person ; 09.02.2013
comment
Проблема, которую я бы нашел более убедительной, была бы: когда и где два объекта прошли ближе всего друг к другу ?. Для велосипедиста, использующего GPS-навигатор Garmin, и для пилота-любителя это было бы классное приложение, использующее в качестве входных данных следы Garmin. Это также добавило бы явно доминирующее первичное 4-е измерение - ВРЕМЯ. Таким образом, мое бесконечномерное решение предоставило бы такое решение, которого я не видел ни у кого. - person ; 09.02.2013

arrow_upward
0
arrow_downward

Ознакомьтесь с деревьями сегментов и Деревья KD.

person J. Katzwinkel    schedule 05.02.2013