Comment calculer des points de polygone à partir d'une simple ligne pour une largeur spécifique?

Question

Je développe actuellement une application qui crée des polygones à partir de lignes et je rencontre un petit problème:

J'ai un ensemble de points, représentant une ligne. Je voudrais créer un polygone qui affiche la ligne avec une largeur spécifique (par exemple pour une rue). J'ai plusieurs idées pour calculer les points du polygone extérieur, mais je pense qu'ils sont trop compliqués ...

Ma meilleure idée était celle illustrée ci-dessous: Chaque point de la ligne doit être projeté à au moins deux points: Les deux les points doivent être à 90 ° du segment de droite suivant et avoir une distance égale à la moitié de la largeur de polygone préférée.

Cela fonctionne bien, comme vous pouvez le voir à la fin et les points de départ du polygone photo. Maintenant, la partie compliquée: Avec cette méthode, dans un coin, chaque point obtient quatre points. Mais ces points ne sont pas corrects pour le polygone externe, car ils sont dans la forme. Les lignes ont intersecté et créé un polygone laid.

Comment trouver les bons points pour un tel polygone? Je pense que ma méthode est beaucoup trop compliquée pour résoudre ce problème.

Quelqu'un peut-il m'aider avec ce problème (propably très commun)?

Info: J'ai marqué cela avec openstreetmap parce que le rendu comme Mapnik a aussi ce problème.

Answer 1

Ce que vous cherchez est un algorithme de décalage de polygone (ou de ligne). Ce n'est pas nécessairement un problème facile à résoudre, d'ailleurs: An algorithm for inflating/deflating (offsetting, buffering) polygons.

Au cours des dernières semaines, j'ai travaillé sur un algorithme de décalage de ligne pour Maperitive. Dans mon cas, je ne avais besoin pour compenser la ligne, donc je ne cherchais pas une solution pour créer un polygone tampon autour, mais je suppose que l'algorithme pourrait être étendu à l'avenir:

flux de base (environ , mais le diable est dans les détails):

1. pour chaque point de polyligne trouver un point qui a une l distance du point d'origine et se trouve sur une ligne qui est perpendiculaire à la ligne originale et passe par l'original point.
2. Dessinez maintenant une ligne de décalage à travers ce nouveau point. La ligne doit être parallèle à la ligne d'origine.
3. Pour les angles de coin, vous devez étendre les deux lignes de décalage voisines et trouver le point d'intersection, qui sera le prochain point de la ligne de décalage.

Quelques choses à observer:

• Notez la limite d'onglet appliquée sur les angles concaves à droite de l'image.
• Avant de calculer la ligne de décalage, vous devez simplifier la polyligne d'origine pour exclure les segments qui sont trop petits pour contenir le décalage (les résultats peuvent être vus au centre gauche de l'image).
• J'ai seulement implémenté la prise en charge des jointures d'onglet, mais un bon algorithme devrait aussi être capable de rendre des jointures rondes (en utilisant des arcs).