Как я могу создать параллельную полилинию без самопересечения?

Question

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

Тем не менее, есть графическая проблема, когда я пытаюсь использовать этот алгоритм на изогнутой полилинии, это, это, является последовательность точек, которые образуют дугу. Когда я создаю параллельную полилинию дуги, все нормально, пока не увеличиваю достаточно расстояния, чтобы прогнозируемые вершины через их нормали, создают полилинию, где продвигаются от одной вершины к другому, на самом деле перемещаются в обратном направлении, создавая самопересеку.

Как я могу эффективно удалить такие вершины с параллельной полилинии? У меня есть хотя из сравнения направления сегментов: если генерируемые сегменты не параллельны, это означает, что я достиг того, была параллельная полилина пересекается сама. Однако это не очень хорошо работает для небольших сегментов (изогнутая полилина будет генерировать даже меньшие сегменты) или полилиния, которые первоначально имеют вырожденные вершины (одна вершина, равная следующему).

Answer 1

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

Я также нашел интересную бумагу на тему под названием Алгоритм смещения для кривых полилинии.