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

Tout d'abord vous devez calculer quels segments de la ligne de coupe appartiennent à votre polygone interne de 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 cet ordre exactement, puis segments C1-C2 , -c4 c3 etc appartiendront toujours de polygones internes (*).

Maintenant, nous pouvons construire algorithme récursif simple pour les polygones de coupe. Compte tenu de votre grand tableau d'entrée, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, commencez à tout point de polygone, par exemple, b ; ajouter à un tableau Résultat . Traverse le tableau d'entrée vers l'avant. Si vous rencontrez

• pousser à un tableau noeud polygone habituelle , Résultat .
• ck noeud, où k est impair , rechercher les c (k + 1) et maintenir déplacement de sa position.
• ck noeud, où k est encore , rechercher les c (k-1) , sauter à sa position et garder traversant néanmoins en avant.

  Pour deux derniers cas, ajouter ces noeuds dans l'ordre que vous rencontrez à Résultat array. Ajouter ck noeud jeu cut , et ajouter un autre noeud ( c (k + 1) ou c (k-1) , selon ce que vous avez) dans un ensemble global fait .

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

  Tôt ou tard, vous rencontrerez le nœud initial que vous traversions à partir. Maintenant, dans le Résultat array vous avez un polygone que vous avez coupé. Souviens toi. Répétez la procédure récursive, à partir de la position de chaque noeud qui appartient à cut ensemble et ne pas appartenir à l'économie mondiale fait < / em> ensemble.

  C'est la solution que je vois. Mais il est geomentry de calcul, donc il peut tourner un peu plus complexe qu'il n'y paraît.

  ---

  Pour notre exemple, commencer à partir de b :

  1. DONE = {} , commencer à partir de b . Après la première passe, vous obtenez Résultat = [b, c4, c3, f, c2, c1] , cut = {c4, c2 } , = {fait c3, c1} ; Recurse c4 et c2 noeuds.
  2. done = {c3;} c1 , commencer à partir de c4 (récursion de 1). Après ce passage, vous obtenez Résultat = [c4, c, c5, c6, e, c3, c4] , cut = {c5 , c3} , fait + = {c6, c4} ; Recurse c5 .
  3. done = {c3, c4 c1;}; c6 , commencer à partir de c2 (récursion de 1). Après ce passage, vous obtenez Résultat = [c2, a, c1] , cut = {c1} , fait + = {} c2 ; Ne pas récursif à c1 , car il est dans fait ensemble;
  4. done = {c3, c4 c1;; c6; c2} , commencer à partir de c5 (récursion de 2). Après ce passage, vous obtenez Résultat = [c5, d, c6] , cut = {c5} , fait + = {} c6 ; Ne pas récursif c5 , car il est dans fait ensemble;

     Voila - vous obtenez 4 polygones que vous avez besoin .

     ---

     (*) Notez qu'il exige une plus grande représentation « mathématique » de la ligne. Par exemple, si l'un des sommets du polygone est sur la ligne, il faut doubler le sommet, à savoir si c point a été un peu plus près du côté droit et sur la ligne rouge, la ligne aurait < code> [c1, c2, c3, c, c, c6] points sur elle, et l'ensemble de polygone serait [a, c1, b, c, c, c, d, c6, e , c3, f, c2] .

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