Générer de nouveaux polygones à partir d'un polygone coupé (2D)

Question

Je suis coincé avec ce petit problème et mon algorithme pour le résoudre ne tient pas dans tous les cas. Est-ce que quelqu'un a une idée de comment résoudre cela?

Voici un polygone exemple:

example http://img148.imageshack.us/img148/8804/poly.png

Description formelle

Nous avons une liste de points dans CW ordre définissant le polygone. Nous pouvons également demander si un point est un point de coupe avec is_cut(p), où p est un point donné. Maintenant, nous voulons calculer de nouveaux polygones causés par cette "coupe".

L'algorithme doit faire:

Entrée: {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

Sortie: {a, c1, c2}, {b, c4, c3, f, c2, c1}, {d, c6, c5}, {e, c3, c4, c, c5, c6}

Voici mon algorithme actuel:

follow your points, CW 
if the point is a cut point 
-> go back trough the list looking for cut points 
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it 
--- else keep searching 
else 
-> continue until you hit your starting point. 
that's a poly 
do this for every non-cut-point 

Cet algorithme ne tient pas si vous commencez à c ou f.

Answer 1

D'abord, vous devez calculer quels segments de la ligne de coupe appartiennent aux internes de votre polygone d'origine. C'est un problème classique et sa solution est simple. Étant donné que vos points c1, c2, c3 ... c6 sont disposés le long de la ligne dans exactement cet ordre, les segments c1-c2, c3-c4 etc appartiendront toujours aux polygones internes (*).

Maintenant, nous pouvons construire un algorithme récursif simple pour couper des polygones. Étant donné votre grand tableau d'entrée, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, commencez à partir de n'importe quel point de polygone, par exemple, b; ajoutez-le au tableau result. Traverse le tableau d'entrée vers l'avant. Si vous rencontrez

• noeud polygone d'habitude, pousser à un tableau result.
• ck nœud, où k est impair, recherchez c(k+1) et continuez à traverser à partir de sa position.
• noeud ck, où k est encore, chercher c(k-1), sauter à sa position et continuer néanmoins traverser vers l'avant.

Pour deux derniers cas, ajoutez ces noeuds dans l'ordre que vous rencontrez à result tableau.Ajouter ck noeud pour définir cut, et ajouter un autre noeud (c(k+1) ou c(k-1), selon ce que vous avez) dans un ensemble global done.

Si vous devez aller au-delà du dernier élément, passez au premier élément du tableau d'entrée.

Tôt ou tard, vous rencontrerez le nœud initial que vous avez traversé. Maintenant, dans le tableau result, vous avez un polygone que vous avez coupé. Souviens toi. Répétez la procédure récursivement, à partir de la position de chaque nœud appartenant à cut et n'appartenant pas à l'ensemble global done.

Voilà la solution que je vois. Mais c'est la géomancie computationnelle, donc cela peut devenir un peu plus complexe qu'il n'y paraît.

---

Pour notre exemple, commencer à partir b:

1. done={}, partir b. Après la première passe, vous obtiendrez result=[b,c4,c3,f,c2,c1], cut={c4,c2}, done={c3,c1}; Recurse à c4 et c2 nœuds.
2. done={c3;c1}, à partir de c4 (récursivité à partir de 1). Après ce passage, vous aurez result=[c4,c,c5,c6,e,c3,c4], cut={c5,c3}, done+={c6,c4}; Recurse à c5.
3. done={c3;c1;c4;c6}, à partir de c2 (récursivité à partir de 1). Après ce passage, vous aurez result=[c2,a,c1], cut={c1}, done+={c2}; Ne pas recurse à c1, car il est en done ensemble;
4. done={c3;c1;c4;c6;c2}, à partir de c5 (récursivité à partir de 2). Après ce passage, vous aurez result=[c5,d,c6], cut={c5}, done+={c6}; Ne pas recurse à c5, car il est en done ensemble;

Voila - vous obtenez 4 polygones dont vous avez besoin.

---

(*) Notez qu'il exige une plus grande représentation "mathématique" de la ligne. Par exemple, si l'un des sommets de polygone est sur la ligne, le sommet doit être doublé, c'est-à-diresi c point était un peu plus proche du côté droit et sur la ligne rouge, la ligne aurait [c1, c2, c3, c, c, c6] points, et le tableau de polygones serait [a, c1, b, c, c, c, d, c6, e, c3, f, c2].

Parfois (pas dans cet exemple), cela peut conduire à couper des polygones "vides", tels que [a, a, a]. Si vous n'en avez pas besoin, vous pouvez les éliminer à un stade avancé. Quoi qu'il en soit, c'est une géométrie computationnelle avec un nombre immense de cas de frontière. Je ne peux pas tous les inclure dans une seule réponse ...

Answer 2

Vous pouvez appliquer l'écrêtage Weiler Atherton (ce que suggère Pavel), mais il y a une mise en garde énorme. En raison d'erreurs en virgule flottante, l'algorithme d'écrêtage W/A est extrêmement difficile à faire fonctionner correctement - Dans des cas tels que la ligne de découpage passant par un sommet, ou précisément le long d'un bord du polygone, l'algorithme peut devenir confus à propos de quel "chemin" autour du périmètre du polygone il devrait suivre et il produit alors des résultats incorrects.

Answer 3

1 trouver côté chaque point est

choisir un pont qui est pas coupé (un par exemple) et définissez qu'il est sur le côté gauche (il ne Metter pas actaly)

lorsque vous aller sur les points sur la coupe, le côté du point que vous atteignez le changement. Donc vous trouvez des points gauche/droit.

Le problème est que vous devriez également considérer que l'ordre des points devrait être de manière prédictive. (dans le sens des aiguilles d'une montre par exemple)

2 commencer à chaque section médiane de cx et aller une fois dans le sens des aiguilles d'une montre et dans le sens inverse des aiguilles d'une montre.

Pour chaque polygone, vous n'atteignez la section médiane que dans une seule direction.

Si vous "débordez" c cela signifie que vous atteignez le polynôme externe. Vous pouvez résoudre ce problème si vous définissez c0 et cmax qui se trouve sur polgon et vous avez que

input = {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2} 

Answer 4

Le plus simple à mettre en œuvre est Sutherland-Hodgman. Le seul problème avec cela est qu'il laisse peu de zéros de zone zéro reliant les polys d'un côté de la ligne. Dans votre exemple, cela vous donne quelque chose comme:

{a c2 c3 e c6 c5 c c4 c1} et {b c1 c2 f c3 c6 d c5 c4}

Si vous pouviez vivre avec cela ou comprendre comment les diviser en morceaux que vous voulez, alors vous constaterez que le code qui a fait la coupure réelle serait à peu près aussi simple que possible.

La mise en œuvre nécessite simplement deux piles et un seul passage à travers les sommets de votre polygone. À chaque sommet, vous vérifiez si vous avez franchi la ligne depuis le sommet précédent. Si c'est le cas, calculez le point de croisement et poussez-le sur l'une des piles. Ensuite, poussez le nouveau sommet sur l'une des piles. Vraiment facile.