Проверьте, находится ли точка в каком-либо прямоугольнике
У меня есть большая коллекция прямоугольников одинакового размера. Я генерирую случайные точки, которые не должны попадать в эти прямоугольники, поэтому я хочу проверить, находится ли сгенерированная точка в одном из прямоугольников, и если это так, сгенерировать новую точку.
Использование R-деревьев, кажется, работает, но они действительно предназначены для прямоугольников, а не точек. Я мог бы использовать модифицированную версию алгоритма R-дерева, которая также работает с точками, но я бы не стал изобретать велосипед, если уже есть какое-то лучшее решение. Я не очень знаком со структурами данных, так что, возможно, уже существует какая-то структура, которая подходит для моей проблемы?
Таким образом, в основном я спрашиваю, знает ли кто-нибудь о хорошем алгоритме, который работает в Python, который можно использовать для проверки, лежит ли точка в каком-либо прямоугольнике в данном наборе прямоугольников.
редактировать: это в 2D и прямоугольники не повернуты.
5 ответов
Этот поток Reddit решает вашу проблему:
У меня есть набор прямоугольников, и мне нужно определить, содержится ли точка в каком-либо из них. Какие есть хорошие структуры данных для этого, с быстрым поиском, который важен?
Если ваша вселенная целочисленная или уровень точности хорошо известен и не слишком высок, вы можете воспользоваться предложением Абельссона из потока, используя поиск O(1) с использованием раскраски:
Как обычно, вы можете обменять пространство на время... вот поиск O(1) с очень низкой константой. init: Создайте растровое изображение, достаточно большое, чтобы охватить все прямоугольники с достаточной точностью, инициализируйте его черным. Цвет всех пикселей, содержащих любой прямоугольник, белый. O(1) поиск: точка (x,y) белая? Если так, прямоугольник был поражен.
Я рекомендую вам перейти на этот пост и полностью прочитать ответ ModernRonin, который является наиболее приемлемым. Я вставил это здесь:
Во-первых, микро проблема. У вас есть произвольно повернутый прямоугольник и точка. Точка внутри прямоугольника?
Есть много способов сделать это. Но лучше всего, я думаю, использовать 2-мерное векторное произведение. Сначала убедитесь, что точки прямоугольника хранятся по часовой стрелке. Затем сделайте векторное произведение с 1) вектором, образованным двумя точками стороны и 2) вектором от первой точки стороны до контрольной точки. Проверьте знак результата - положительный находится внутри (справа от) стороны, отрицательный - снаружи. Если это внутри всех четырех сторон, это внутри прямоугольника. Или, что то же самое, если он находится вне какой-либо из сторон, он находится за пределами прямоугольника. Больше объяснений здесь.
Этот метод будет принимать 3 вычитания на вектор *, умноженные на 2 вектора на сторону, плюс одно перекрестное произведение на сторону, которое равно трем умножениям и двум сложениям. 11 флопов на сторону, 44 флопа на прямоугольник.
Если вам не нравится перекрестное произведение, то вы можете сделать что-то вроде: выяснить, вписанные и ограниченные круги для каждого прямоугольника, проверить, находится ли точка внутри вписанного. Если так, то это тоже в прямоугольнике. Если нет, проверьте, находится ли он за пределами описанного прямоугольника. Если так, то это тоже за пределами прямоугольника. Если он попадает между двумя кругами, значит, вы чертовски трудны.
Нахождение точки внутри окружности в 2d требует двух вычитаний и двух квадратов (= умножение), а затем вы сравниваете расстояние в квадрате, чтобы избежать необходимости делать квадратный корень. Это 4 флопа, два круга - 8 флопов, но иногда вы все равно не узнаете. Также это предполагает, что вы не платите процессорное время, чтобы вычислить описанные или вписанные круги, что может быть или не быть правдой в зависимости от того, сколько предварительных вычислений вы готовы сделать для вашего набора прямоугольников.
В любом случае, возможно, не стоит проверять точку на каждом прямоугольнике, особенно если у вас их сто миллионов.
Что подводит нас к проблеме макроса. Как избежать проверки точки на каждый прямоугольник в наборе? В 2D это, вероятно, проблема четырех деревьев. В 3d то, что сказал generic_handle - октри. Наверху, я бы, вероятно, реализовал это как дерево B +. Заманчиво использовать d = 5, чтобы каждый узел мог иметь до 4 дочерних элементов, так как это очень хорошо отображается на абстракцию четырехъядерного дерева. Но если набор прямоугольников слишком велик, чтобы поместиться в основную память (в наши дни это маловероятно), то, вероятно, стоит использовать узлы одинакового размера с дисковыми блоками.
Остерегайтесь раздражающих вырожденных случаев, таких как некоторый набор данных, который имеет десять тысяч почти идентичных прямоугольников с центрами в одной и той же точной точке.:П
Почему эта проблема важна? Это полезно в компьютерной графике, чтобы проверить, пересекает ли луч многоугольник. То есть, тот выстрел из снайперской винтовки, который ты только что сделал, поразил человека, в которого стреляли? Он также используется в картографическом программном обеспечении в реальном времени, например, в единицах GPS. GPS сообщает вам координаты, в которых вы находитесь, но программное обеспечение карты должно найти, где находится эта точка в огромном количестве картографических данных, и делать это несколько раз в секунду.
Опять же, заслуга ModernRonin...
Для прямоугольников, которые выровнены с осями, вам нужно только две точки (четыре числа), чтобы идентифицировать прямоугольник - условно, левый нижний и правый верхний углы. Чтобы определить, перекрывает ли данная точка (Xтест, Yтест) прямоугольник (XBL, YBL, XTR, YTR), протестировав оба:
- Xtest > = XBL && Xtest <= X TR
- Ytest > = YBL && Ytest <= Y TR
Очевидно, что для проверки достаточно большого набора точек это может занять довольно много времени. Вопрос в том, как оптимизировать тестирование.
Ясно, что одной из оптимизаций является установление минимальных и максимальных значений X и Y для прямоугольника, окружающего все прямоугольники (ограничивающий прямоугольник): быстрый тест на этом показывает, есть ли необходимость смотреть дальше.
- Xtest > = Xmin && Xtest <= X max
- Ytest > = Ymin && Ytest <= Y max
В зависимости от того, сколько общей площади поверхности покрыто прямоугольниками, вы можете найти непересекающиеся подзоны, которые содержат прямоугольники, и тогда вы можете избежать поиска в тех подзонах, которые не могут содержать прямоугольник, перекрывающий точку, снова сохранение сравнений во время поиска за счет предварительного вычисления подходящих структур данных. Если набор прямоугольников достаточно разреженный, перекрытия может не быть, и в этом случае это вырождается в поиск методом грубой силы. Точно так же, если набор прямоугольников настолько плотен, что в ограничивающей рамке нет поддиапазонов, которые можно разделить, не разбивая прямоугольники.
Однако вы также можете произвольно разбить ограничивающую область, скажем, на четверти (по половине в каждом направлении). Затем вы будете использовать список блоков, который будет включать больше блоков, чем в исходном наборе (два или четыре блока для каждого блока, который перекрывает одну из произвольных границ). Преимущество этого состоит в том, что вы можете исключить три из четырех четвертей из поиска, уменьшив объем поиска, который нужно выполнить в целом - за счет вспомогательного хранилища.
Итак, как всегда, есть пространственно-временные компромиссы. И предварительные вычисления против компромиссов поиска. Если вам не повезло, предварительные вычисления ничего не достигают (например, есть только два блока, и они не перекрываются ни на одной из осей). С другой стороны, это может принести значительную выгоду во время поиска.
Почему бы не попробовать это. Это кажется довольно легким как для вычислений, так и для памяти.
Рассмотрим проекции всех прямоугольников на базовую линию вашего пространства. Обозначим этот набор интервалов строки как
{[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.
Теперь предположим, что ваша точка (x, y), начинайте поиск слева от этого набора, пока не достигнете линейного интервала, который содержит точку x.
Если ничего не происходит, ваша точка (x, y) находится за пределами всех прямоугольников.
Если некоторые из них скажут [Rlk, Rrk], ..., [Rlh, Rrh], (k <= h), просто проверьте, находится ли y в пределах по вертикали любого из этих прямоугольников.
Готово.
Удачи.
Джон Донер
Ваш подход R-дерева - лучший из известных мне подходов (этот подход я бы выбрал для дерева квадрантов, деревьев B+ или BSP, поскольку R-деревья удобны для построения в вашем случае). Предостережение: я не эксперт, хотя я помню кое-что из своего курса по алгоритмике в университете.
Я предлагаю вам взглянуть на деревья BSP (и на возможные ветки дерева или октавы, ссылки также доступны на этой странице). Они используются для рекурсивного разделения всего пространства и позволяют быстро проверить точку, прямоугольники которой вам нужно проверить.
Как минимум, у вас есть только один огромный раздел, и вам нужно проверить все прямоугольники, максимум ваши разделы становятся настолько маленькими, что они уменьшаются до размеров отдельных прямоугольников. Конечно, чем более детализирован раздел, тем дольше вам нужно идти по дереву, чтобы найти прямоугольники, которые вы хотите проверить.
Тем не менее, вы можете свободно решить, сколько прямоугольников подходит для проверки на точку, а затем создать соответствующую структуру.
Обратите внимание на перекрывающиеся прямоугольники, хотя. Так как дерево BSP должно быть предварительно вычислено в любом случае, вы можете также удалить перекрытия в течение этого времени, чтобы получить чистые разделы.