Внешний многоугольник из набора краев

Question

Предположим, что у меня есть набор из двух сегментов линии, все из которых связаны. Мне нужен алгоритм, который находит самые отдаленные сегменты в наборе. То есть минимальное подмножество, которое ограничивает одну и ту же область.

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

Редактировать: Наверху находится начальный набор сегментов. Ниже приведен один и тот же контур с удаленными внутренними сегментами. (Игнорируйте маленькие серые кресты, они просто отметят точки пересечения.)

Answer 1

Как бы вы сделали это с помощью карандаша ...?

1. Найти левую вершину (минимум x). Если их больше одного, выберите самый низкий из них (минимум y). Нет вершины ниже текущей, поэтому возьмите направление «вниз» в качестве ссылки.
2. Найти все ребра, идущие от текущей вершины и рассчитать их направления (подшипники). Найти тот, который делает наименьший положительный угол (против часовой стрелки) от опорного направления. Это будет сегмент контура.
3. Выберите другой конец в качестве новой «текущей» вершины и установите направление от этой вершины до последнего в качестве нового эталонного направления.
4. Перейдите к шагу 2, пока не дойдете до начальной вершины.
5. Удалите все невидимые сегменты.
6. Удалите все осиротевшие вершины (если они появились на шаге 5).

Answer 2

Ниже приводится подход, начинающийся с convex hull, затем прокладывает себе путь внутрь. Интуиция заключается в том, что вы начинаете с краев на корпусе, затем заполняете пробелы, находя ближайшую точку «вдоль» промежутка, следуя кратчайшему пути в своем наборе кромок.

1. Вычислить выпуклый корпус ваших точек.
2. Пересеките корпус, установленный вашим набором кромок. Это оставит вас с рядом потенциально отключенных путей.
3. Любая точка, которая не имеет двух ребер (то есть, leaf в терминах графа), соединена с ее ближайшим листом, найдя кратчайший путь в исходном наборе ребер.
4. Любые галстуки могут быть разбиты дорожкой, которая делает наименьшую площадь закрытой корпусом.

Answer 3

Для трехгранного невыпуклого многоугольника вы можете указать направление обхода вершин (по часовой стрелке от CCW). Сделайте все треугольники одинаково ориентированными WRT обхода его вершин. Разложите все треугольники на направленные ребра. Каждое ребро для каждого треугольника является кортежем из двух вершин (a, b). Для каждого соседнего треугольника у вас есть два противоположных края (a, b) и (b, a). Вы можете просто исключить такие пары ребер из дальнейшего рассмотрения. Наконец, вы получите набор исключительно внешних краев.

Нет никакой потери общности, если ваш многоугольник состоит из несимплициальных частей (но все же вы можете указать направление обхода вершин).

Триангуляция многоугольника, построенного на основе исходных сегментов, является очевидным шагом: растягивание вершин на параболоиде и триангуляции $ d + 1 $, а затем исключение треугольников, содержащих по крайней мере одно ребро, которое не соответствует ни одному сегменту источника.

Другой возможный подход слегка изменен Gift wrapping algorithm.