Получить набор прямоугольников, содержащих указанную точку

Я не могу понять, как реализовать это на практике, поэтому я решил спросить вас, ребята.

У меня есть список прямоугольников — на самом деле это только квадраты, но мне, возможно, придется перейти к прямоугольникам позже, так что давайте придерживаться их и оставить его немного более общим — в 2-мерном пространстве. Каждый прямоугольник определяется двумя точками, прямоугольники могут перекрываться, и меня не слишком волнует время установки, потому что прямоугольники в основном статичны и есть некоторое пространство для предварительного расчета любых элементов настройки (таких как построение деревьев, сортировка, предварительный расчет дополнительных векторов, что угодно и т.д.). О, я разрабатываю JavaScript, если это имеет какое-либо значение.

На мой фактический вопрос: учитывая точку, как мне получить набор всех прямоугольников, включающих эту точку?

Линейные подходы работают недостаточно хорошо. Поэтому я ищу что-то, что работает лучше, чем O (n). Я читал кое-что, например, об иерархиях ограничивающих объемов и подобных вещах, но что бы я ни пробовал, тот факт, что прямоугольники могут перекрываться (и я действительно хочу получить их все, если точка находится внутри нескольких прямоугольников), кажется, всегда мешает мне .

Есть предложения? Я пропустил что-то очевидное? Применимы ли BVH даже к возможным перекрывающимся границам? Если да, то как построить такое, возможно, перекрывающееся дерево? Если нет, что еще я мог бы использовать? Меня не волнует, внутренние границы, внешние или неопределенные.

Если бы кто-то мог придумать что-нибудь полезное, например ссылку или разглагольствования о том, насколько я глуп, чтобы использовать BVH, а не Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem, я был бы очень признателен!

Редактировать: Хорошо, я немного поигрался с R-Trees, и это именно то, что я искал. Фактически, в настоящее время я использую реализацию RTree http://stackulator.com/rtree/, предложенную endy_c. Он работает очень хорошо и полностью удовлетворяет мои требования. Большое спасибо за вашу поддержку, ребята!


search algorithm geometry point-in-polygon
person Daniel Baulig    schedule 31.10.2010    source источник
comment
Я предполагаю, что ваши прямоугольники выровнены с декартовыми осями?   -  person peter.murray.rust    schedule 31.10.2010
comment
Да, извините, забыл упомянуть об этом. Настройка в основном очень проста, за исключением того, что прямоугольники могут перекрываться. Это действительно тривиально линейно, но как только вы (или я, на самом деле) пытаетесь уменьшить сложность (какая ирония), это выходит из-под контроля, и я не могу с этим справиться.   -  person Daniel Baulig    schedule 31.10.2010
comment
мы можем использовать постоянное дерево сегментов, чтобы оптимизировать его до O (log n) на запрос.   -  person Siqi Ouyang    schedule 30.06.2016

Ответы (2)


arrow_upward
7
arrow_downward

Вы можете посмотреть на R-деревья

код Java

есть и вики, но можно разместить только одну ссылку ;-)

person Doggett    schedule 31.10.2010

arrow_upward
2
arrow_downward

Вы можете разделить пространство на сетку и для каждой ячейки сетки иметь список прямоугольников (или идентификаторов прямоугольников), которые хотя бы частично существуют в этой сетке. Поиск прямоугольников только в соответствующей ячейке сетки. Сложность должна быть O(sqrt(n)).

Другой подход состоит в том, чтобы поддерживать четыре отсортированных массива значений x1, y1, x2, y2 и выполнять двоичный поиск вашей точки в этих 4 массивах. Результатом каждого поиска является набор кандидатов-прямоугольников, а конечным результатом является пересечение этих 4 наборов. В зависимости от того, как реализовано пересечение множеств, это должно быть эффективнее, чем O (n).

person Dialecticus    schedule 31.10.2010
comment
+1 Хорошие подходы - но нам все еще нужно знать, что такое n (точки или прямоугольники). - person Adam Matan; 31.10.2010
comment
Мне очень нравится ваш первый подход, каким бы простым он ни был. Я думал об использовании сетки, и на самом деле это в основном подход BVH (но выложенный линейно, а не иерархически), но, к моему стыду, никогда не думал о размещении прямоугольников в нескольких зонах. Я еще немного подумаю об этом. - person Daniel Baulig; 31.10.2010