Алгоритм разделения топологических слоев

Question

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

Answer 1

Первое, что приходит на ум, это алгоритм развертки и сокращения (также известный как сортировка и развертка).

По сути, вы сначала узнаете "границы" каждой фигуры вдоль каждой оси. Для оси x это будут самые левые и самые правые точки на фигуре. Для оси у, самый верхний и самый нижний.

Допустим, у вас есть связанная структура, которая выглядит примерно так:

struct Bound
{
    float value;      // The value of the bound, ie, the x or y coordinate.
    bool  isLower;    // True for a lower bound (leftmost point or bottommost point).
    int   shapeIndex; // The index (into your array of shapes) of the shape this bound is on.
};

Создайте два массива этих границ, один для оси x и один для y.

Bound xBounds* = new Bound[2 * numberOfShapes];
Bound yBounds* = new Bound[2 * numberOfShapes];

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

int closeAxes* = new int[numberOfShapes * numberOfShapes];

for (int i = 0; i < numberOfShapes * numberOfShapes; i++)
    CloseAxes[i] = 0;

struct Pair
{
    int shapeIndexA;
    int shapeIndexB;
};

Pair candidatePairs* = new Pair[numberOfShapes * numberOfShape];
int numberOfPairs = 0;

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

Затем сделайте следующее (и повторите для оси Y):

for (int i = 0; i + 1 < 2 * numberOfShapes; i++)
{
    if (xBounds[i].isLower && xBounds[i + 1].isLower)
    {
        unsigned int L = xBounds[i].shapeIndex;
        unsigned int R = xBounds[i + 1].shapeIndex;

        closeAxes[L + R * numberOfShapes]++;
        closeAxes[R + L * numberOfShapes]++;

        if (closeAxes[L + R * numberOfShapes] == 2 ||
            closeAxes[R + L * numberOfShapes] == 2)
        {
            candidatePairs[numberOfPairs].shapeIndexA = L;
            candidatePairs[numberOfPairs].shapeIndexB = R;
            numberOfPairs++;
        }
    }
}

Все пары кандидатов меньше, чем дельта на каждой оси. Теперь просто проверьте каждую пару кандидатов, чтобы убедиться, что они на самом деле меньше дельты друг от друга. Я не буду вдаваться в подробности, как именно это сделать в данный момент, потому что, ну, я на самом деле не думал об этом, но, надеюсь, мой ответ, по крайней мере, поможет вам начать. Я полагаю, что вы могли бы просто проверить каждую пару отрезков линии и найти кратчайшее расстояние x или y, но я уверен, что есть более эффективный способ сделать шаг "узкой фазы".

Очевидно, что фактическая реализация этого алгоритма может быть намного более сложной. Моей целью было сделать объяснение ясным и кратким, а не элегантным. В зависимости от макета ваших фигур и алгоритма сортировки, который вы используете, один прогон этого примерно между O(n) и O(n log n) с точки зрения эффективности, в отличие от O(n^2), чтобы проверить каждый пара фигур.