Comment puis-je créer une polyligne parallèle sans intersections auto?

Question

L'algorithme simple pour créer une polyligne parallèle à une polyligne existante est simple: vous pouvez calculer la normale de chaque sommet (comme la moyenne des Normales du segment) et déplacer les sommets en utilisant la normale avec ce montant que vous voulez

Cependant, il y a un problème graphique lorsque je tente d'utiliser cet algorithme sur une polyligne courbe, c'est une succession de points qui forment un arc. Lorsque je crée le parallèle à la polyligne à l'arc, tout va bien jusqu'à ce que j'augmente suffisamment de distance projetée sommets à travers leurs Normales créer une polyligne où avancer d'un sommet à un autre en fait se déplace dans le sens inverse en créant une auto-intersection.

Comment puis-je supprimer ces sommets de la polyligne parallèle efficace? J'ai bien de comparer la direction des segments: si les segments générés ne sont pas parallèles, cela signifie que je suis arrivé à un point étaient les intersecte polylignes parallèles lui-même. Cependant, cela ne fonctionne pas très bien pour les petits segments (une polyligne courbe va générer des segments encore plus petits) ou polylignes qui à l'origine ont des sommets dégénérés (un sommet égal à la suivante).

Answer 1

Un parallèle polyligne est connu dans les milieux graphiques comme polyligne offset. Ressemble à un procédé pour générer des polylignes de décalage sans artefacts géométriques sont dégénérées à utiliser droite algorithmes squelette.

Je l'ai aussi trouvé un article intéressant sur le sujet appelé Un décalage algorithme pour les courbes de polylignes .