скажем, у меня есть огромный набор неперекрывающихся прямоугольников с целыми координатами, которые фиксируются раз и навсегда
У меня есть еще один прямоугольник A с целыми координатами, координаты которых движутся (но вы можете предположить, что его размер постоянный)
Каков наиболее эффективный способ определения того, какие прямоугольники пересекаются (или внутри)? Я не могу просто пропустить свой набор, поскольку он слишком большой. Благодаря
edit: прямоугольники все параллельны оси
Лично я решил бы это с помощью KD-Tree или BIH-Tree. Они представляют собой адаптивные структуры пространственных данных, которые имеют время поиска журнала (n). У меня есть реализация обоих для моего Ray Tracer, и они кричат.
- ОБНОВЛЕНИЕ -
Сохраните все ваши фиксированные прямоугольники в KD-Tree. Когда вы проверяете пересечения, выполните итерацию через KD-Tree следующим образом:
function FindRects(KDNode node, Rect searchRect, List<Rect> intersectionRects)
// searchRect is the rectangle you want to test intersections with
// node is the current node. This is a recursive function, so the first call
// is the root node
// intersectionRects contains the list of rectangles intersected
int axis = node.Axis;
// Only child nodes actually have rects in them
if (node is child)
{
// Test for intersections with each rectangle the node owns
for each (Rect nRect in node.Rects)
{
if (nRect.Intersects(searchRect))
intersectionRects.Add(nRect);
}
}
else
{
// If the searchRect boundary extends into the left bi-section of the node
// we need to search the left sub-tree for intersections
if (searchRect[axis].Min // Min would be the Rect.Left if axis == 0,
// Rect.Top if axis == 1
< node.Plane) // The absolute coordinate of the split plane
{
FindRects(node.LeftChild, searchRect, intersectionRects);
}
// If the searchRect boundary extends into the right bi-section of the node
// we need to search the right sub-tree for intersections
if (searchRect[axis].Max // Max would be the Rect.Right if axis == 0
// Rect.Bottom if axis == 1
> node.Plane) // The absolute coordinate of the split plane
{
FindRects(node.RightChild, searchRect, intersectionRects);
}
}
Эта функция должна работать после преобразования из псевдокода, но алгоритм правильный. Это алгоритм поиска журнала (n) и, возможно, самая медленная его реализация (преобразование из рекурсивного в стек).
- UPDATE - добавлен простой алгоритм построения KD-дерева
Простейшая форма дерева KD, содержащего формы области/объема, такова:
Rect bounds = ...; // Calculate the bounding area of all shapes you want to
// store in the tree
int plane = 0; // Start by splitting on the x axis
BuildTree(_root, plane, bounds, insertRects);
function BuildTree(KDNode node, int plane, Rect nodeBds, List<Rect> insertRects)
if (insertRects.size() < THRESHOLD /* Stop splitting when there are less than some
number of rects. Experiment with this, but 3
is usually a decent number */)
{
AddRectsToNode(node, insertRects);
node.IsLeaf = true;
return;
}
float splitPos = nodeBds[plane].Min + (nodeBds[plane].Max - nodeBds[plane].Min) / 2;
// Once you have a split plane calculated, you want to split the insertRects list
// into a list of rectangles that have area left of the split plane, and a list of
// rects that have area to the right of the split plane.
// If a rect overlaps the split plane, add it to both lists
List<Rect> leftRects, rightRects;
FillLists(insertRects, splitPos, plane, leftRects, rightRects);
Rect leftBds, rightBds; // Split the nodeBds rect into 2 rects along the split plane
KDNode leftChild, rightChild; // Initialize these
// Build out the left sub-tree
BuildTree(leftChild, (plane + 1) % NUM_DIMS, // 2 for a 2d tree
leftBds, leftRects);
// Build out the right sub-tree
BuildTree(rightChild, (plane + 1) % NUM_DIMS,
rightBds, rightRects);
node.LeftChild = leftChild;
node.RightChild = rightChild;
Здесь есть куча очевидных оптимизаций, но время сборки обычно не так важно, как время поиска. Говоря это, дерево построения скважин - это то, что делает поиск быстрым. Посмотрите SAH-KD-Tree, если вы хотите узнать, как построить быстрое kd-дерево.
Готов поспорить, вы можете использовать какой-то вывод quadtree для этого. Взгляните на этот пример.
Вы можете создать два вектора индексов прямоугольника (поскольку две диагональные точки однозначно определяют ваш прямоугольник) и сортировать их по одной из координат. Затем вы выполняете поиск перекрытий с использованием этих двух массивов индексов, которые будут логарифмическими, а не линейными.
Вы можете сделать случайный "ходячий" алгоритм... в основном создать список соседей для всех ваших прямоугольников с фиксированной позицией. Затем произвольно выберите один из прямоугольников фиксированной позиции и проверьте, где находится целевой прямоугольник по сравнению с текущим прямоугольником фиксированной позиции. Если он не находится внутри прямоугольника, который вы случайно выбрали в качестве начальной точки, то он будет в одном из восьми направлений, которые соответствуют данному соседу вашего текущего прямоугольника фиксированной позиции (т.е. Для любого заданного прямоугольника будет прямоугольник в N, NE, E, SE, S, SW, W, NW). Выберите соседний прямоугольник в ближайшем заданном направлении к целевому прямоугольнику и повторите проверку. Это, по сути, рандомизированный алгоритм инкрементного построения, и его производительность, как правило, очень хороша для геометрических задач (обычно логарифмическая для отдельной итерации и O (n log n) для повторных итераций).
Создайте матрицу, содержащую элементы "квадранта", где каждый квадрант представляет собой пространство N * M в вашей системе, причем N и M являются шириной и высотой самых широких и самых высоких прямоугольников соответственно. Каждый прямоугольник будет помещен в квадрантный элемент на основе его верхнего левого угла (таким образом, каждый прямоугольник будет находиться ровно в один квадрант). Для прямоугольника A проверьте наличие столкновений между прямоугольниками в собственном квадранте и 8 соседних квадрантах.
Это алгоритм, который я нахожу, рассматривая, как рекомендуется, как простая оптимизация для тестов на грубую силу при обнаружении конфликтов для разработки игр. Он работает лучше всего, когда вы в основном имеете дело с маленькими объектами, хотя, если у вас есть несколько больших объектов, вы можете избежать разрушения его эффективности, выполнив их обнаружение по отдельности и не помещая их в квадрант, тем самым уменьшая размер квадранта.
Поскольку они не перекрываются, я бы предложил подход, аналогичный (но не равный) для Джейсона Мура (B). Сортируйте массив по x верхнего левого угла. И отсортируйте копию по верхнему левому углу. (разумеется, вы просто разделите указатели на них, чтобы сохранить память).
Теперь вы создаете два набора Sliding_Window_X и Sliding_Window_Y.
Вы выполняете поиск по бинарному поиску после x-координаты (вверху слева) для вашего окна A в отсортированном по x массиве и y-координате. Вы помещаете свои результаты в файл sliding_Window_Set. Теперь вы добавляете все следующие прямоугольники в упорядоченном массиве, которые имеют более низкую координату x (y) (на этот раз ниже справа), чем ваш нижний правый угол A.
В результате вы в Sliding_Window задаете окна, которые перекрываются с вашим A в одной координате. Наложение A является пересечением Sliding_Window_X и _Y.
Наборы Sliding_Window могут быть легко представлены всего двумя номерами (начальный и конечный индекс сортировочного массива, отвечающего за обработку).
Как вы говорите, вы перемещаете A, теперь очень легко пересчитать перекрытие. В зависимости от направления теперь вы можете добавлять/удалять элементы в набор Sliding_Window. То есть вы берете только следующий элемент из отсортированного массива на передней/конце набора и, возможно, удаляете его в конце.
Topcoder предоставляет способ определить, находится ли точка внутри прямоугольника. В нем говорится, что мы имеем точку x1, y1 и прямоугольник. Мы должны выбрать случайную точку, очень удаленную от текущей локальности ссылки в прямоугольной системе координат, например, x2, y2.
Теперь мы должны сделать отрезок линии с точками x1, y1 и x2, y2. Если этот отрезок пересекает нечетное число сторон данного прямоугольника (в нашем случае это будет 1, этот метод может быть распространен и на общие многоугольники), то точка x1, y1 лежит внутри прямоугольника и если она пересекает четное число сторон он лежит вне прямоугольника.
Учитывая два прямоугольника, нам нужно повторить этот процесс для каждой вершины 1 треугольника, возможно, во втором треугольнике. Таким образом, мы сможем определить, перекрываются ли два прямоугольника, даже если они не выровнены по оси x или y.
Интервальные деревья: предназначены ли BST с принятием значения "lo" в качестве ключа в интервале. Так, например, если мы хотим вставить (23, 46) в дерево, мы вставим его с помощью "23" в BST.
Кроме того, с деревьями интервалов в каждом node мы сохраняем максимальную конечную точку (значение hi) поддерева, корневого в этом node.
Этот порядок вставки позволяет нам искать все пересечения "R" в R (logN). [Мы ищем первое пересечение в logN время и все R в RlogN время] Пожалуйста, обратитесь к документации интервальных деревьев для того, как вставляются, выполняются поиск и детали сложности.
Теперь для этой проблемы мы используем алгоритм, известный как алгоритм развертки. Представьте себе, что мы имеем вертикальную линию (параллельную оси y), которая подметает 2D-пространство и в этом процессе пересекается с прямоугольниками.
1) Расположите прямоугольники в порядке возрастания x-cordinates (левый крайний) либо через приоритетную очередь, либо путем сортировки. Сложность NlogN, если N прямоугольников.
2) Поскольку эта линия проносится слева направо, следуют случаи пересечения:
Если линия пересекает левую сторону прямоугольника, который никогда не виден, добавьте y координаты стороны прямоугольника в дерево интервалов. [say (x1, y1) и (x1, y2) являются левыми координатами края интервала добавления прямоугольника (y1, y2) в дерево интервалов] --- > (NlogN)
Сделайте поиск диапазона в дереве интервалов. [say (x1, y1) и (x1, y2) являются левыми координатами края прямоугольника, занимают интервал (y1, y2) и выполняют запрос пересечения интервалов на дереве, чтобы найти все пересечения] --- > RlogN (на практике)
Если линия пересекает правую часть прямоугольника, удалите ее из дерева интервалов, поскольку прямоугольник теперь полностью обработан. ---- > NlogN
Общая сложность: NlogN + RlogN
Пусть ваш набор прямоугольников будет (Xi1, Yi1, Xi2, Yi2), где я изменяется от 0 до N.
Прямоугольник A и B не могут пересекаться, если Ax1 > Bx2 || Ay1 < By2 || Bx1 > Ax2 || By1 < Ay2.
Создать дерево, которое оптимизировано для диапазона/интервала (для exa: дерево сегментов или дерево интервалов) См. http://w3.jouy.inra.fr/unites/miaj/public/vigneron/cs4235/l5cs4235.pdf
Используйте это дерево, чтобы найти набор треугольников, в то время как ваш треугольник меняет координаты.
Вычисляя площадь каждого прямоугольника и проверяя длину L, высота H и площадь прямоугольников превышают или не имеют длину и высоту и площадь прямоугольника A
Метод (A)
Вы можете использовать дерево интервалов или дерево сегментов, Если деревья были созданы так, чтобы они были сбалансированы, это дало бы вам время O (log n). Я предполагаю, что этот тип предварительной обработки является практичным, потому что это произойдет только один раз (похоже, что вы больше заботитесь о времени выполнения, как только прямоугольник начинает двигаться, чем вы с первоначальной предварительной обработкой в первый раз). Объем пространства будет O (n) или O (n log n) в зависимости от вашего выбора выше.
Метод (B)
Учитывая, что ваш большой набор прямоугольников имеет фиксированный размер и никогда не меняет их координаты и что они не перекрываются, вы можете попробовать несколько иной стиль алгоритма/эвристики, чем предлагать другие здесь (предполагая, что вы можете жить с единовременная предварительная плата за предварительную обработку).
Алгоритм предварительной обработки [O (n log n) или O (n ^ 2) runtime {выполняется только один раз}, O (n) пробел]
Вычислить функцию распределения и кумулятивную функцию распределения горизонтальных координат. (Время выполнения O (1) до O (n ^ 2) в зависимости от используемого метода и того, какое распределение ваших данных имеет)
a) Если горизонтальные координаты ваших прямоугольников следуют некоторым естественным процессам, вы можете, вероятно, оценить их функцию распределения, используя известное распределение (например: normal, exponential, uniform и т.д.).
b) Если горизонтальные координаты ваших прямоугольников не соответствуют известному распределению, вы можете вычислить пользовательское/оцененное распределение, создав histogram.
Вычислить функцию распределения и кумулятивную функцию распределения вертикальных координат.
a) Если вертикальные координаты ваших прямоугольников следуют каким-то естественным процессам, вы можете, вероятно, оценить их функцию распределения, используя известное распределение (например: normal, exponential, uniform и т.д.).
b) Если вертикальные координаты ваших прямоугольников не соответствуют известному распределению, вы можете вычислить пользовательское/оцененное распределение, создав histogram.
Алгоритм поиска пересечения в реальном времени [в любом месте от O (1) до O (log n) до O (n) (примечание: если O (n), то константа перед n будет очень малой} время выполнения в зависимости от того, насколько хорошо функции распределения соответствуют набору данных]
Возьмем горизонтальную координату вашего движущегося прямоугольника и подключите его к функции совокупной плотности для горизонтальных координат многих прямоугольников. Это даст вероятность (значение от 0 до 1). Умножьте это значение раз n (где n - количество многих прямоугольников, которые у вас есть). Это значение будет индексом массива для проверки в отсортированном списке прямоугольников. Если прямоугольник этого индекса массива пересекается, тогда вы закончите и можете перейти к следующему шагу. В противном случае вам придется сканировать окружающих соседей, чтобы определить, пересекаются ли соседи с движущимся прямоугольником. Вы можете атаковать эту часть проблемы несколькими способами:
a) выполнить линейное сканирование, пока не найдет пересекающийся прямоугольник или не найдет прямоугольник с другой стороны движущегося прямоугольника
b) вычислить доверительный интервал , используя функции плотности вероятности, которые вы рассчитали, чтобы дать вам наилучшее предположение о потенциальных границах (т.е. интервал, где пересечение должно лежать). Затем выполните двойной поиск на этом небольшом интервале. Если двоичный поиск не выполняется, вернитесь к линейному поиску в части (a).
Сделайте то же самое, что и на шаге 1, но сделайте это для вертикальных частей, а не для горизонтальных частей.
Если шаг 1 дал пересечение, а шаг 2 дал пересечение, а пересекающийся прямоугольник на шаге 1 был тем же прямоугольником, что и на шаге 2, то прямоугольник должен пересекаться с движущимся прямоугольником. В противном случае нет пересечения.
Используйте дерево R +, которое, скорее всего, точно определяет конкретную структуру дерева, которую вы ищете. R + деревья явно не допускают перекрытия во внутренней (нелистовой) структуре в обмен на скорость. Пока объект не существует в нескольких листах одновременно, наложения не перекрываются. В вашей реализации, а не на перекрытии поддержки, всякий раз, когда объект нужно добавить к нескольким листам, просто верните true.
Вот подробное описание структуры данных, в том числе о том, как управлять прямоугольниками: R + -tree: динамический индекс для многомерных объектов