Tessellating un polygone arbitraire par des triangles de carrelage

StackOverflow https://stackoverflow.com/questions/1999397

Question

Je dois remplir un polygone arbitraire en utilisant un pavage quasi uniforme des triangles. Comment puis-je faire cela? Vous pouvez fournir soit des références à des algorithmes existants ou même simplement des idées ou des conseils de votre propre.

Ce qui suit est présumée:

  • Le polygone peut être (mais des points bonus si vous venez avec un algorithme qui fonctionne pour des formes concaves) convexes
  • Le polygone a un nombre arbitraire de bords (3 ou plus)
  • La quantité de tessellation (de préférence le nombre de sommets ajoutés par l'algorithme) doit être paramétré
  • peuvent être divisés les bords du polygone par l'algorithme
  • Triangles devrait être à peu près uniforme dans la taille et la forme (à savoir les coins ont tendance vers 60 degrés)
  • De préférence, le nombre des bords à un sommet devrait être peu plutôt que beaucoup. Cela suivra probablement du point précédent (par exemple l'algorithme doit produire un « maillage propre »).

Ce n'est pas un problème facile à résoudre et je pense qu'une solution « heuristique » peut être le plus efficace ... (à droite?)

Était-ce utile?

La solution

Comme Jason Orendorff a souligné, vous devriez essayer d'utiliser Triangle pour générer un maillage de qualité. Il a beaucoup d'options que vous pouvez jouer avec pour essayer d'obtenir un maillage isotrope. Ensuite, vous pouvez essayer d'utiliser un algorithme itératif pour créer une triangulation bien centrée. Plus de détails sont répertoriés sur cette publications . Je l'ai mis en œuvre le document de 2007 « Bien-Centré Planar Triangulation - une approche itérative, » et il donne des résultats décents sur des mailles de taille moyenne. Une triangulation bien centrée est une dans laquelle toutes les circumcenters de triangles se trouvent à l'intérieur du triangle respectif. Puisque vous voulez quelque chose de légèrement différent, vous pouvez simplement essayer de changer l'erreur métrique impliquée. Vous pouvez trouver une mesure de « non-congruence » entre les triangles et de minimiser cette erreur. Très probablement une telle fonction d'erreur sera non-convexe, de sorte que l'optimisation du gradient conjugué non linéaire décrit est ainsi que vous pouvez le faire.

Autres conseils

Triangle faire ce que vous voulez?

(Les explications des algorithmes sur ce site sont mieux que tout ce que je pouvais trouver.)

Ne sonne pas si compliqué que ça en fait, algorithmiquement. Ou suis-je manque quelque chose?

Certains pseudo-code:

  • Placer un axe aligné enfermant hermétiquement carré autour du polygone.
  • Subdiviser chaque carré en quatre enfants (quad-tree comme), où le nombre d'itérations détermine votre « quantité de tessellation ».
  • Chaque carré résultant est soit nettement en dehors de votre polygone (= ignorer), propre à l'intérieur de votre polygone (= divisé en deux triangles résultant pavage le long de la diagonale) ou recoupe le polygone.
  • cas exactes pour les places d'intersection sont laissés comme un exercice au lecteur. ;-) [A ce moment, au moins.]

Il vous donnera des triangles avec 45 ° / 45 ° / 90 ° angles cependant. Si vous voulez que près de 60 ° que possible, vous devriez commencer par tessellation la surface de votre polygone avec des hexagones (avec la taille de l'hexagone étant votre « quantité de tessellation »), puis de vérifier chacun des six 60 ° / 60 ° / 60 ° triangles qui composent ces hexagones. Pour ces triangles que vous faites la même chose que les places dans le pseudocode ci-dessus, à l'exception du fait que vous n'avez pas besoin de diviser ceux qui proprement l'intérieur de votre polygone car ils sont déjà eux-mêmes triangles.

Est-ce d'aucune aide? Devrait travailler pour un polygone (convexe / concave / troués), je pense, étant donné que exactement ce que vous faites pour les carrés d'intersection / triangles poignées de ces polygones.

Cela peut être fait pour les polygones concaves / convexes en utilisant une méthode simple oreille coupure (en supposant que nous ne devons soutenir les trous).

est à 2 pas, il peut être plus efficace pour couper itérativement l'oreille « meilleur » pour obtenir des résultats plus uniformes, de sorte que vous n'avez pas à réarranger la topologie d'une seconde passe (YMMV).
(Notez que les raisons 2 étapes sont utilisées ici est que le calcul de répartition plus équitable est pas toujours nécessaire).

La divulgation complète, je suis tombé sur ce problème moi-même, quand je besoin d'un tessellator rapide pour les polygones pour une application de modélisation en temps réel.

Mise en oeuvre de travail écrit en C,
qui prennent et le retour de POD (le tableau de float[2], remplir un tableau de uint[3]):

(Note, la coupure de l'oreille est basée sur libgdx avec des optimisations spatiales aux contrôles d'intersection, à l'échelle jusqu'à des milliers de côtés sans un tel succès significatif de la performance, puisque écrêtage chaque oreille vérifiait tout autre -Points à chaque fois).

example sortie

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top