Un algorithme pour gonfler/dégonfler les polygones (compensation, mise en mémoire tampon)

Question

Mise à JOUR: les mathématiques terme pour ce que je cherche est en fait vers l'intérieur/vers l'extérieur du polygone offseting. +1 pour balint pour le rappeler. L'alternative de nommage est un polygone de mise en mémoire tampon.

Mise à JOUR 2 (02.11.2011): découvrez la nouvelle accepté de répondre à Clipper de la bibliothèque par Angus Johnson.

Avant de commencer à développer ma propre solution à partir de zéro, personne ne sait de toute bonne source pour un algorithme qui peut gonfler un polygone, quelque chose de semblable à ceci:

La condition est que la nouvelle (gonflé) du polygone à côtés, les points sont à la même distance constante par rapport à l'ancien (original) du polygone (sur l'exemple de pic. ils ne le sont pas, car alors il faudrait utiliser des arcs pour gonfler les sommets, mais oublions pour l'instant ;) ).

Les résultats de ma recherche:

Voici quelques liens:

• Une Enquête de Polygone Offseting Stratégies
• Polygone de décalage, de PROBLÈME
• Mise En Mémoire Tampon Des Données De Polygones

Answer 1

Je comprends que cette question a été posée avec une réponse et accepté il y a quelques temps. Néanmoins, je pensais que je pourrais mentionner brièvement ma propre polygone de découpage et de compensation de la bibliothèque - Clipper - dans le cas où d'autres sont encore à la recherche d'une solution à ce problème.

Alors que Clipper est principalement conçu pour les polygones les opérations de découpage, il ne polygone de compensation. La bibliothèque est freeware open source écrit en Delphi, C++ et C#. Il a une très encombré Stimuler la licence lui permettant d'être utilisé dans les deux freeware applications commerciales et ce, sans frais.

Clipper polygone de compensation fonction permet le choix de trois décalage styles - rond, carré et onglet.

Answer 2

Le polygone que vous cherchez est appelé vers l'intérieur/vers l'extérieur décalage polygone dans le calcul de la géométrie et il est étroitement lié à la droite du squelette (voir http://en.wikipedia.org/wiki/Straight_skeleton)

Ce sont plusieurs décalage des polygones complexes polygone:

Et c'est le droit de squelette pour un autre polygone:

Comme indiqué dans d'autres commentaires, en tant que bien, en fonction de combien vous prévoyez de "gonfler/dégonfler votre polygone, vous pouvez vous retrouver avec de connexion différentes pour la sortie.

De calcul de point de vue: une fois que vous avez le droit de squelette, on devrait être en mesure de construire le décalage des polygones relativement facilement. L'open source et (gratuit pour les non-commerciale) CGAL la bibliothèque dispose d'un package de mise en œuvre de ces structures. Voir cet exemple de code pour calculer l'offset de polygones à l'aide de CGAL.

Le package manuel devrait vous donner un bon point de départ sur la façon de construire ces structures, même si vous n'allez pas utiliser CGAL, et contient les références des documents avec la mathématique définitions et propriétés:

CGAL manuel: Droit en 2D Squelette et Polygone de Compensation

Answer 3

Me semble que ce que vous voulez, c'est:

• En commençant dans un coin, le visage anti-horaire, le long d'une arête adjacente.
• Remplacer la pointe de la technologie avec une nouvelle arête parallèle placé à distance d de la "gauche" de l'ancien.
• Répétez l'opération pour tous les bords.
• Trouver les intersections de la nouvelle bords pour obtenir les nouveaux sommets.
• Détecter si vous avez traversé polynôme et de décider quoi faire à ce sujet. Sans doute ajouter un nouveau sommet au passage du point et de se débarrasser de certains anciens. Je ne suis pas sûr qu'il y a une meilleure façon de détecter ce que juste pour comparer chaque paire de non-arêtes adjacentes à voir si leur intersection se trouve entre les deux paires de sommets.

Le polygone résultant se trouve à la distance requise de l'ancien polygone "assez loin" des sommets. Près d'un sommet, l'ensemble des points à distance d de l'ancien polygone est, comme vous le dites, pas un polygone, de sorte que l'obligation qu'a déclaré ne peuvent pas être remplies.

Je ne sais pas si cet algorithme a un nom, un exemple de code sur le web, ou un diabolique de l'optimisation, mais je pense qu'il décrit ce que vous voulez.

Answer 4

Voici une solution alternative, voir si vous l'aimez mieux.

1. Faire une triangulation, il n'ont pas à être delaunay-toute la triangulation le ferait.

2. Gonflez chaque triangle -- cela devrait être trivial. si vous stockez le triangle dans le sens anti-horaire de l'ordre, il suffit de déplacer les lignes à droite et ne intersection.

3. Fusionner utilisant une version modifiée de Weiler-Atherton l'écrêtage de l'algorithme

Answer 5

Chaque ligne doit diviser le plan de "l'intérieur" et "plan"; vous pouvez la trouver à l'aide de l'habituel intérieure-produit méthode.

Déplacer toutes les lignes vers l'extérieur par une certaine distance.

Envisager toutes les paires de voisin lignes (lignes, pas de segment de ligne), trouver l'intersection. Ces sont le nouveau sommet.

Nettoyage le nouveau sommet en supprimant toutes les pièces traversées. -- nous avons quelques cas ici

(a) Cas 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

si vous dépensez par l'un des, vous obtenu ceci:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 et 4 chevauchement.. si vous voyez cela, vous supprimez ce point et tous les points entre les deux.

(b) cas 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

si vous dépensez par deux, vous avez ceci:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

pour résoudre ce problème, pour chaque segment de ligne, vous devez vérifier si elle chevauchement avec les derniers segments.

(c) cas 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

dépenser de 1. c'est un cas plus général pour le cas 1.

(d) cas 4

même que case3, mais dépenser par deux.

En fait, si vous pouvez gérer l'affaire 4. Tous les autres cas sont juste au cas particulier de celui-ci avec une ligne ou un sommet qui se chevauchent.

Pour 4, vous de garder une pile de vertex.. vous pousser lorsque vous trouver des lignes qui se chevauchent avec la dernière ligne, de la pop lorsque vous obtenez la dernière ligne. -- juste comme ce que vous faites dans convexe-hull.