Avoir des problèmes avec la coupure d'oreille

Question

Le problème que j'ai est à venir parce que je ne peux pas identifier un triangle cédé contre une oreille qui devrait être coupée.

Comment puis-je faire la différence entre un triangle convexe et un triangle concave?

Answer 1

Les triangles ne peuvent pas être concaves. Voulez-vous dire que votre maillage est concave?

---

Je n'avais pas réalisé que vous parliez d'une technique particulière. Après avoir fait un peu de recherche, je pense que je comprends suffisamment votre problème pour tenter une réponse. Supposons que vous traversez les sommets de votre polygone dans le sens inverse des aiguilles d'une montre. Si nous les traversons dans cet ordre, le corps du polygone sera toujours à gauche. Nous considérons trois sommets: A, B, et C. Imaginez que nous tirons un rayon de A à B. Si C est à gauche de ce rayon, alors c'est un triangle bien formé qui fait partie du polygone. Si C est à la droite de ce rayon, alors il représente l'espace négatif.

OK, donc nous allons créer des vecteurs v (qui est A → B) et w (qui est B → C). En outre, construisons v ', qui est v mais tourné 90 degrés CCW. v »= < -v [y], v [x]>

Pour savoir si C est à gauche ou à droite de v, nous avons simplement besoin de mesurer l'angle entre v ' et w. Si c'est dans (0, 90) ou (270, 360), alors c'est à gauche. Si c'est dans (90, 270), alors c'est à droite. C'est pratique car cela correspond exactement à cos (Θ)> 0 et cos (Θ) < 0, respectivement. Donc, si cos (Θ)> 0, alors C est à gauche, et si cos (Θ) < 0, alors C est à droite.

Nous pouvons utiliser des produits scalaires pour nous aider à déterminer cos (Θ). Rappelez-vous que cos (& thetav) = (v ' • w)/(mag (v') ⋅ mag (w)). Cependant, nous n'avons pas besoin de cos (Θ), nous n'avons besoin que de signe (cos (Θ)). Puisque mag (v ') et mag (w) doivent tous deux être positifs, nous pouvons les ignorer. Par conséquent, si v ' • w> 0, alors C est à gauche et les trois points correspondent à un triangle qui fait partie du polygone. D'autre part, si v ' • w < 0, alors C est à droite et les trois points correspondent à l'espace négatif à l'extérieur du polygone.

Je n'ai pas réellement essayé ceci au-delà des tests simples, mais je crois que cela (ou quelque chose de proche) fonctionnera. Oh, et pour d'autres qui (comme moi) n'avaient jamais entendu parler de cette technique, vous pouvez lire à ce sujet here.