алгоритм разделения топологических слоев - PullRequest
Новая
       3

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

0 голосов
/ 01 февраля 2012

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

1 Ответ

1 голос
/ 02 февраля 2012

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

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

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

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и один для г. 

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), чтобы проверить каждыйпара фигур.

...