Эффективный алгоритм удаления петель из полилиний

Question

У меня есть ломаная линия, заданная в виде упорядоченного набора (X, Y) координат, которая может пересекать себя, образуя один или несколько циклов. Из этого я хочу извлечь многоугольник с удаленными петлями, который будет включать точки пересечения, где линия пересекает себя. В настоящее время у меня есть грубый алгоритм грубой силы, который работает следующим образом:

int RemoveLoops(CoordType Points[],int NoPoints)
{
    int n = 0;  // Start of first line segment
    int m = 2;  // Offset to n of second line segment
    int p = NoPoints;
    while (n + m + 1 < p)
    {
        CoordType Ip; // Intersection point
        if (Intersect(Points[n],Points[n+1],Points[n+m],Points[n+m+1],Ip))) 
        {
            Points[n+1] = Ip;
            int d = m - 1;  // Number of points to delete
            for (int i = n + m + 1; i < p; i++)
                Points[i - d] = Points[i];
            p -= d;
            m = 2;
            continue;   // Restart from intersection point 
        }
        m ++;
        if (n + m + 1 >= p) // Reached end of line, change starting segment
        {
            m = 2;  // Reset offset
            n++;    // Increment starting segment
        }
    }
    return(p);  // Return the number of points in the new poly line
}

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

Есть идеи относительно хорошего алгоритма для вышеперечисленного, O (n log n) или лучше?

Answer 1

Обычные предположения, которые приводят к ускорению или более приятному алгоритму, - это когда полигональная цепочка является простой или выпуклой. Вначале ваша цепочка - ни то, ни другое.

Возможно, существует инкрементная структура данных, которая может выполнить O (log n + s) строк - простые тесты пересечения полигональных цепей, но я подозреваю, что даже если она существует, она более сложна и, вероятно, медленнее, чем просто пересечение сегментов.

Answer 2

Попробуйте использовать алгоритм строчной линии . Интуитивно, лучше думать об алгоритме графически. Вы размещаете точки в плоскости и «наводите» их слева направо. Во время подметания вы поддерживаете инвариант состояния линий, которые вы уже обнаружили. Если есть пересечение между двумя линиями, это должно произойти между двумя линиями, которые мы уже «открыли». Технически, вам не нужно «подметать» самолет: вы можете проверять инвариант каждый раз, когда натыкаетесь на точку. Таким образом, вы можете упорядочить точки по их x координате и проходить их по очереди.

Узким местом алгоритма является сортировка, которую можно выполнить в O(nlogn). Я почти уверен, что вы не можете сделать лучше, чем nlog n, потому что проблемы такого типа обычно сводятся к сортировке. Вы, вероятно, можете свести эту проблему к нахождению выпуклой оболочки набора точек, что также невозможно менее чем за n log n.