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

Question

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

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

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

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

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

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

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

Answer 1

Вы можете посмотреть на R-Trees

Java-код

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

Answer 2

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

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