Параллельная кривая как алгоритм для графиков

Question

Есть ли хорошо известный алгоритм для вычисления "параллельного графа"? где под параллельным графиком я подразумеваю то же самое, что и параллельная кривая, неопределенно называемая «кривой смещения», но с графиком вместо кривой. В лучшем случае это позволило бы переменное расстояние для каждого сегмента (соединения).

Учитывая следующую картину, где известны координаты узлов, связанных с красными сегментами, а также желаемое расстояние (толщина)

график смещения http://3.bp.blogspot.com/_MFJaWUFRFCk/TAEFKmfdGyI/AAAAAAAACXA/vTOBQLX4T0s/s320/screenshot2.png

как я могу рассчитать точки черных контуров полигонов?

Answer 1

Ознакомьтесь со стратегией Straight Seleton . Есть пример реализации, здесь . Сложность алгоритма задокументирована здесь .

Кроме того, здесь описаны некоторые другие методы, Обзор стратегий смещения полигонов .

В GameDev также есть тема .

Редактировать: CGAL также имеет реализацию этого, начиная с версии 3.3, см. API . Автор славно представил тестовый файл . (Не реализация.) Однако вы можете проверить источник.