найти контур смежных полигонов

Я ищу способ найти контур двух соседних многоугольников.найти контур смежных полигонов

Полигоны определяются списком точек, упорядоченных по вхождению в многоугольник. В моем случае использования нет перекрывающихся полигонов, между полигонами нет промежутков, и нет полигонов с «отверстиями».

Я хочу рассчитать схему двух полигонов без каких-либо «отверстий». Эти pictures показывают ожидаемые результаты.

enter image description here

Я знаю, что есть много библиотек для отсечения многоугольников, но для большинства из них производительность не очень хорошо, потому что они работают для любого вида многоугольника (с отверстиями, перекрывающихся многоугольников и т.д.) , В моем варианте использования алгоритм должен работать в режиме реального времени для большого количества полигонов (> 20 000). Как я могу наиболее эффективно рассчитать схему?

источник

2014-09-29 heinzwilli

Попробуйте это ... http://stackoverflow.com/questions/83593/is-there -an-efficient-algorithm-to-generate-a-2d-вогнутый корпус –

Будет полезно: 1) избегать дублирования вершин; 2) установить обратное соотношение «эта вершина принадлежит этому/их контурову».Оттуда вы можете найти контуры, которые разделяют вершину и могут быть объединены, а обработка сократится до логического объединения двух списков вершин. –

Ив Дауст: После вашего совета я могу определить, какие вершины принадлежат обоим полигонам. Но как продолжать? Случай один на картинке довольно прост. Мне просто нужно вставить вершины из многоугольника 2 между двумя вершинами из многоугольника 1, которые принадлежат обоим полигонам, в правильном порядке. Случай 2 с рисунка сложнее. Если я удаляю контуры между полигонами, остается «отверстие». Как я могу определить, какие контуры принадлежат «дыре»? – heinzwilli

Учитывая

не перекрывающихся полигонов, нет никаких зазоров между полигонами и нет многоугольники с «дырами»

следующий алгоритм должен сделать трюк.

Удалить дубликаты отрезков.
Вычислить естественное комбинаторное вложение того, что осталось в качестве doubly connected edge list. Каждый сегмент порождает два узла (половина ребер, обратные друг к другу, причем одна конечная точка сегмента представляет собой головку (соответственно хвост), а другая - хвост (соответственно головка)), а каждая половина краевых связей к следующей половине края с той же головой в направлении против часовой стрелки.
Извлечь лица. A face в комбинаторном вложении - это минимальное, непустое множество половинных ребер, для которого для каждой половины ребра e обратная сторона следующего полуребра от e находится в множестве. Множество граней - это разбиение полуребер. См. Диаграмму ASCII ниже.
```
U----V----W 
| | | 
| | | 
Z----Y----X 
```
Бесконечное лицо {U->Z, Z->Y, Y->X, X->W, W->V, V->U}. Следующая половина края от W->V составляет U->V. Реверс следующего крайнего края от W->V составляет V->U. Остальные грани {U->V, V->Y, Y->Z, Z->U} и {V->W, W->X, X->Y, Y->V}.
Сохранять только бесконечные грани путем суммирования подписанных углов против часовой стрелки и проверки знака. Конечное лицо, как {U->V, V->Y, Y->Z, Z->U} имеет отрицательную сумму
```
/_UVY - 180 + /_VYZ - 180 + /_YZU - 180 + /_ZUV - 180 
    = 4 * (90 - 180) = -360. 
```
Бесконечное лицо имеет положительную сумму
```
/_UZY - 180 + /_ZYX - 180 + /_YXW - 180 + /_XWV - 180 + /_WVU - 180 + /_VUZ - 180 
    = 4 * (270 - 180) + 2 * (180 - 180) = 360. 
```

источник

2014-10-04 04:34:36

ответ

Смежные вопросы