Быстрый алгоритм для нахождения всех точек внутри прямоугольника

Question

Учитывая набор различных точек в двумерном пространстве и прямоугольник (координаты всех четырех точек, сторон, параллельных оси xy), как я могу быстро найти, какие точки находятся внутри прямоугольника?

Меня не интересует основное решение, проходящее через все точки и видя, какой из них находится внутри прямоугольника. Я ищу алгоритм, который даст мне быстрое время запроса на каждый прямоугольник.

Мне все равно, сколько времени я провожу на этапе предварительной обработки. Меня волнует то, что после обработки данных я получаю полезную структуру, которая дает мне быстрое время запроса на каждый прямоугольник.

Я знаю, например, я могу подсчитать, сколько точек у меня внутри прямоугольника в O (logN). Это работает, потому что я делаю много тяжелой обработки в начале, а затем каждый раз обрабатываю обработанные данные с помощью нового прямоугольника и получаю новый счет в logN time. Я ищу аналогичный алгоритм для нахождения фактических точек, а не только их счет.

Answer 1

Классическим ответом является kD-дерево (в данном случае 2D-дерево).

Для простой альтернативы, если ваши точки распределены достаточно равномерно, вы можете попробовать с помощью сетки.

Выберите размер ячейки для квадратной сетки (если проблема является анизотропной, используйте прямоугольную сетку).Назначьте каждую точку ячейке сетки, которая содержит ее, сохраненную в связанном списке. Когда вы выполняете запрос, найдите все ячейки, которые перекрываются прямоугольником и просматривают их, чтобы пересечь их списки. Для частично покрытых ячеек вам нужно будет выполнить тест «точка-в-прямоугольнике».

Выбор размера важен: слишком большой может привести к тому, что слишком много точек, нуждающихся в проверке, в любом случае; слишком маленький может привести к слишком большому количеству пустых ячеек.

Answer 2

Если вы отсортируете точки по оси X, то вы сможете выполнить двоичный поиск, чтобы найти самую левую (наименьшее значение X), которая находится в прямоугольнике.

Сделайте еще один бинарный поиск, чтобы найти самую правую (самую большую величину X) точку в прямоугольнике.

Все точки в отсортированном списке между этими двумя точками будут находиться в пределах левого края прямоугольника, даже если вы не проверили большинство из них!

Повторите этот процесс по вертикальной оси/оси Y.

---

Два бинарных поиска по оси X должны быть равны O (logN).
То же самое с двумя бинарными поисками по оси Y.
O (4 LogN) == O (журнал N)

Там еще будет какая-то слияния шага в конце концов, что я не сразу уверен.

Answer 3

Думаю, что вы должны хранить свои очки в quadtree. Я не разработал детали, но он должен позволять в основном делать что-то похожее на двоичный поиск, который напрямую дает точки, находящиеся внутри прямоугольника.

Если ваши точки сгруппированы, т. Е. Существуют кластеры, которые содержат много точек в небольшой области и других областях, которые не содержат или очень мало точек, R-tree может быть еще лучше.

Сложность выполнения должна быть O (logN) Я думаю.

Answer 4

Вы можете группировать точки в секторах. Если сектор полностью находится в или из заданного прямоугольника, то все точки внутри него также находятся или выходят. Если сектор частично включен, вам нужно искать O (n) для точек в этом секторе, чтобы проверить, находятся ли они в прямоугольнике. Ищите k-d tree поиск.

Answer 5

Вы ищете kd-tree range search или запрос диапазона.

• Квадраты (или октавы или 16 деревьев ...) лучше, когда есть изменяющийся набор точек, но вы ожидаете, что распределение будет равномерным. Никаких дальнейших шагов балансировки не требуется, поскольку структура дерева фиксирована.
• kd-деревья лучше работают на фиксированном множестве точек, даже с неравномерным распределением. Когда набор точек изменяется, трудно (но не невозможно) выполнить шаги самобалансировки.
• Деревья AABB (или жирные деревья AABB) обеспечивают быстрый способ тестирования перекрывающихся фигур, а не только точек. Иногда AABB-деревья нуждаются в балансировке. Когда постоянно движущиеся объекты включены, общим способом является использование «жирных AABB-s», поэтому вам не нужно обновлять дерево в каждом кадре.
• Сортировка только одной осью и использование двоичного поиска (что-то вроде предложенного abelenky, но я думаю, что нет смысла делать второй бинарный поиск) - это простое и элегантное решение, но будет медленным, когда, например, вы сортируете по X, и все точки находятся на прямой, параллельной Y. Вы должны выполнить линейную фильтрацию по точкам, которые сопоставляются бинарным поиском по X. Сложность времени - это худший случай O(n), но этот худший случай случается довольно часто.

Все эти алгоритмы запускают запросы в среднем O(log n + k), где k - количество совпадающих точек.

Gridding, как и предложил Yves, может выполнять поиск по диапазону в O(k) времени, но только тогда, когда размер прямоугольника запроса ограничен. Это то, что они часто делают в particle simulations. Gridding может использоваться, даже если набор входных данных не ограничен - просто сделайте фиксированное количество ведер на основе хеша координат сетки. Но если прямоугольник запроса может иметь произвольный размер, то сетка - это не-go.

Answer 6

Наряду с другими ответами вы также можете изучить коды Мортона (сортировка кривой z-порядка).

В вашем случае, то есть статические данные, вы можете даже представить все данные точки в виде массива.

https://en.wikipedia.org/wiki/Z-order_curve

Эта статья также имеет довольно сложный график различных «методы мульти-доступа х мерные» - http://www.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf