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

Question

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

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

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

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

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

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

Редактировать: Хорошо, я немного играл с R-дереями, и это именно то, что я искал. Infact Я в настоящее время использую реализацию RTREE http://stackulator.com/rtree/ Как предложено Endy_c. Он действительно хорошо работает и полностью полностью добивает мои требования. Спасибо, много для вашей поддержки, ребята!

Answer 1

Вы могли бы посмотреть на R-деревья

Java код

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

Answer 2

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

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