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

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

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

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

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

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

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