¿Cómo puedo crear una polilínea paralelo sin intersecciones auto?

Question

El algoritmo simple de crear una polilínea paralela a una polilínea existente es simple: se puede calcular la normal de cada vértice (como la media de las normales del segmento) y desplazar los vértices utilizando la normal con cualquier cantidad que usted quiere

Sin embargo, hay un problema gráfica cuando intento de utilizar este algoritmo en una polilínea curva, esto es, una sucesión de puntos que forman un arco. Cuando creo el paralelo a la polilínea de arco, todo está bien hasta que aumento la suficiente distancia que proyecta vértices a través de sus normales crean una polilínea donde avanzando desde un vértice a otro en realidad se mueve en la dirección inversa, creando un auto-intersección.

¿Cómo puedo eliminar dichos vértices de la polilínea en paralelo de manera eficiente? He aunque de comparar la dirección de los segmentos: si los segmentos generados no son paralelas, que significa que he llegado a un punto eran las propias intersecta polilínea paralelas. Sin embargo, esto no funciona muy bien para pequeños segmentos (una polilínea curvada generará segmentos incluso más pequeños) o polilíneas que originalmente tienen vértices degenerados (un vértice igual a la siguiente).

Answer 1

A polilínea paralelo se conoce en los círculos gráficos como polilínea offset. Se parece a un método para generar polilíneas de offset sin artefactos de geometría degenerados son para uso algoritmos rectas esqueleto .

También he encontrado un interesante artículo sobre el tema llamado Un desplazamiento algoritmo para las curvas de polilínea .