Определить внешнюю границу ограничивающих полигонов C ++

Question

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

У меня это представлено в C ++ как следующее:

#include <vector>

using namespace std;

class Shape {

    public:
        Shape(vector<vector<float> > c) {
            coordinates = c;
        }

        vector<vector<float> > coordinates; // in format {{x1,y1},{x2,y2}}
};

class Shape_Group {
    public:
        Shape_Group(vector<Shape> s) {
            shapes = s;
        }

        vector<Shape> shapes;
        Shape generate_border();
};

Shape Shape_Group::generate_border() {
    /* 
        define algorithm here
    */
}

int main() {
    // define rectangle shapes
    Shape s1({{0,0}, {0,1}, {1,1}, {1,0}});
    Shape s2({{0,0}, {0,1}, {1,-1}, {-1,0}});

    Shape_Group group({s1, s2}); 
    Shape border = group.generate_border(); // should return a shape with the exterior border
    // border should be filed with {{1,0}, {1,1}, {1,-1}, {-1,0}};
}

Моя первоначальная идея для генерации этой внешней формы заключалась в следующем:

loop through each line segment for each shape in the Shape_Group object
    loop through every other segment in the Shape_Group object
        if both line segments are colinear and overlap, remove them

whatever's left over should be the exterior border

Однако при больших входных данных это очень медленный алгоритм. Что еще я могу сделать?

Answer 1

Геометрия O(n^2) заход на посадку:

1. создание списка всех ребер

2. удаление всех внутренних ребер

   использование проверка попадания для обнаружения внутренних / внешних ребер.

3. заново соедините все оставшиеся ребра в новый многоугольник

   просто соедините ребра, имеющие одну и ту же конечную точку.

Если вы хотите что-то более простое, тогда O(n) графический подход:

1. визуализация вашей фигуры
2. заливка фона указанным c цветом
3. удалить все ребра, а не соседний цвет фона

это несколько связано:

• Визуализация заполненных сложных многоугольников с большим количеством вершин с помощью OpenGL

он также сочетает в себе векторную графику и пиксельный доступ ...

Есть и другие подходы к этой проблеме, например, такие как:

• Поиск отверстий в наборе 2d точек?