Алгоритм накачивания / выкачивания (смещения, буферизации) полигонов

Question

Как бы я «надул» многоугольник? То есть я хочу сделать что-то похожее на это:

Требование заключается в том, что ребра / точки нового (надутого) многоугольника находятся на одном и том же постоянном расстоянии от старого (исходного) многоугольника (на примере изображения это не так, поскольку тогда придется использовать дуги для завышенных вершин). , но давайте об этом пока забудем;)).

Математический термин для того, что я ищу, на самом деле смещение внутреннего / внешнего многоугольника . +1 к балтинту за указание на это. Альтернативное наименование - полигональная буферизация .

Результаты моего поиска:

Вот несколько ссылок:

• Обзор стратегий офсета полигонов
• Смещение многоугольника, ПРОБЛЕМА
• Буферизация данных полигона

Answer 1

Я использую простую геометрию: векторы и / или тригонометрию

1. В каждом углу найдите средний вектор и средний угол. Средний вектор - среднее арифметическое двух единичных векторов, определяемых ребрами угла. Средний угол - это половина угла, определенного краями.

2. Если вам нужно расширить (или сжать) свой многоугольник на величину d от каждого ребра; Вы должны выйти (в) на величину d / sin (midAngle), чтобы получить новую угловую точку.

3. Повторите это для всех углов

*** Будьте осторожны в вашем направлении. Сделайте CounterClockWise Test, используя три точки, определяющие угол; выяснить, какой выход, или в.

Answer 2

Существует несколько библиотек, которые можно использовать (также можно использовать для наборов данных 3D).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

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

Последний имеет наименьшие зависимости, является автономным и может читать в файлах .obj.

С наилучшими пожеланиями, Stephan