maillage
bonjour,
disposant d'un nuage de point dont je connais les coordonnées de chacun, je voudrais creer un maillage triangulaire.
comment faire pour identifier chaque trois points, pour qu'aucun point ne reste à la fin, et qu'il n'y ait pas de triangles qui se croisent.
merci.
Imagine que tu travailles bestialement en partant d'un point et de son plus proche voisin, soit (1) et (2). Tu cherches un 3ème point (3) tel que la somme des distances à ces points soit la plus faible (tu as pu créer une table des distances à l'avance) et ça fait un triangle. Tu recommences avec le couple (1)-(3) etc...
S'il reste un orphelin tu cherches des points proches.
Ca ne garantit pas que des triangles ne vont pas se croiser, mais ça peut se détecter et alors tu es face à un quadrilatère ou au pis un hexagone et tu tâtonnes.
Si c'est pour une méthode des éléments finis, il y a des exigences sur la forme des triangles (pas trop pointus) et ça peut demander des retouches manuelles.
Bonjour,Envoyé par einstein
il doit exister des algorithmes mais je ne les connais pas.
Par contre, j'ai trouvé un procédé par couronne convexe qui ne semble pas trop difficile à programmer.
1ère couronne :
1er point : le point de plus grande ordonnée, et de plus grande abscisse s'il y en a plusieurs.
point suivant : sont construits E(e) et E(e+1) de telle manière que tous les points du nuage sont à gauche de E(e) E(e+1)* (quand on va de E(e) à E(e+1))
le point suivant E(e+2) est le point du nuage situé sur la demi-droite issue de E(e+1) tel que l'angle orienté (\vec{E(e)E(e+1)}, \vec{E(e+1)E(e+2)} * soit le plus petit (et le plus proche de E(e+1) en cas d'égalité). (Vu que les points du nuage sont tous du côté indiqué c'est une comparaison de cosinus).
Pour le départ il faut remplacer E(e)E(e+1) par la paralèle passant par E(1) et remplacer \vec{E(e)E(e+1)} par -\vec{i}
Comme le nombre de point est fini, le processus se termine quand on "revient" au point initial.
Une fois cette couronne construite, on considère formé par les points restants, et on construit une 2ème couronne, et ainsi de suite tant qu'il reste au moins trois points après la construction de la dernière couronne.
Maintenant entre deux couronnes successives (une est intérieure l'autre extérieure).
On relie les deux points initiaux notés E(1) et I(1) de chaque couronne (ça ne peut couper la couronne intérieure en un autre point ni les côtés de la couronne extérieure sans aboutir à une contradiction)
On "avance" sur chaque couronne dans le même sens direct qu'adopté précédemment.
Supposons que l'on ait "avancé" jusque E(e) et I(i) sans avoir "bouclé" sur une couronne (c'est le cas au départ)
Si I(i)I(i+1) coupe la droite E(e)E(e+1) à l'extérieur de [E(e)E(e+1)] on peut avancer sur la couronne intérieure (segment suivant : E(e)I(i+1)) ou sur la couronne extérieure (segment suivant : E(e+1)I(i))
Si I(i)I(i+1) coupe en I' [E(e)E(e+1)], I' n'est pas entre I(i) et I(i+1) qui sont du même côté par rapport à E(e)E(e+1), il y a donc deux cas :
I(i) est entre I' et I(i+1) : on avance sur la couronne extérieure,
I(i+1) est entre I' et I(i) : on avance sur la couronne intérieure.
Quand on a bouclé sur la couronne intérieure ou la couronne extérieure, on reste fixe sur cette couronne et on avance sur l'autre jusqu'à boucler.
Vu les constructions, avec un peu d'effort on montre qu'il ne peut y avoir d'intersection entre ces segments. Il en est de même avec ceux à l'extérieur de la couronne extérieur (les segments qui y sont construits sont entièrement dans cette zone) et de même pour l'intérieur de la couronne intérieure.
Reste l'intérieur de la dernière couronne :
s'il y a encore deux points, le procédé ci-dessus convient en prenant le segment doublé reliant ces deux points comme une couronne convexe, dégénérée mais qui convient ici.
s'il y a encore un point : ont fait le tour de la couronne autour de ce point, c'est le cas le plus facile.
s'il n'y a plus de points, on fait du saute sommet, on relie E(1) et E(3) (d'où le triangle E(1)E(2)E(3)), puis E(3) et E(5) etc
On termine selon la parité du nombre de points de la couronne au point initial ou son prédécesseur. On considère la nouvelle couronne formée des points de numéro impair (c'est encore convexe), on peut alors itérer s'il y a plus de trois points, sinon on a fini.
bonsoir,
j'avoir Homotopie que je n'ai pas vraiment compris ta methode, pourrais tu expliciter stp? merci
je viens de me rendre compte d'une contrainte que je n'ai pas evoqué au depart: mon nuage de point n'est pas libre mais contenu dans une enveloppe. cette enveloppe peut etre convexe, concave et avoir meme une geometrie assez compliquée. cette enveloppe est definie par les points "exterieur" du nuage de point. les lignes du maillage ne doivent pas couper l'enveloppe. la methode que tu as cité est elle conforme avec cette exigence?
en fait je pose ici le probleme pour un nuage 2D, juste pour comprendre le principe de la methode, mais apres je dois ecrire un algo pour un nuage 3D.
le contexte de ce probleme est le suivant: j'ai un objet créé par un outil CAO (qui peut etre complexe ou non). j'ai un algorithme qui à partir de ce fichier CAO me donne une liste de points pour un maillage EF. ce qui me manque c'est lier ces points entre eux.
merci
J'essaie d'éclaircir certains points mais le plus important est après.
1ère étape : construction de polygones convexes
Nuage 1=nuage de départ
1ère sous-étape : on prend l'enveloppe convexe du nuage 1, sa frontière est un polygone 1 (creux) convexe composé de segments reliant certains points (j'ai donné une méthode pour la construire directement)
Nuage 2=nuage de départ moins les points du polygone 1
2ème sous-étape : on prend l'enveloppe convexe du nuage 2, sa frontière est un polygone 2 (creux) convexe composé de segments reliant certains points
...
Nuage i=nuage de départ moins les points du polygone i-1
i-ème sous-étape : on prend l'enveloppe convexe du nuage i, sa frontière est un polygone i (creux) convexe composé de segments reliant certains points.
...
cette étape s'arrête quand nuage i est composé de 0, 1 ou 2 points (donc <3 points). La zone comprise entre deux polygones successifs sera appelé anneau.
2ème étape : trianguler les anneaux (fais un dessin de deux polygones conves l'un à l'intérieur à l'autre, tu te rendras compte que la méthode on part d'un segment puis on tourne en formant des triangles fonctionne)
3ème étape : trianguler l'intérieur du polygone n,
s'il reste un ou deux points, ils peuvent être pris comme polygone intérieur dans la méthode précédente.
s'il n'y a plus de points on forme des triangles en allant de sommet impair en sommet impair (les triangles formés ont un sommet pair et sont sur les bords), seront formés des triangles et un nouveau polygone convexe avec lequel on recommence jusqu'à ce polygone convexe soit un triangle (cas où le dernier polygone est un pentagone ou un hexagone) soit réduit à un segment (cas où le dernier polygone est un carré)
A un moment j'ai cherché une méthode pour d'abord découper des zones convexes à partir d'un zone dont la frontière est imposée (j'ai trouvé mais c'est pas beau) mais ça m'a permis de trouver plus simple.
Il suffit de savoir construire un segment qui ne coupe pas la frontière.
On choisit un sens de rotation sur la frontière (pour ma part je choisis le sens direct). Quand on tourne dans ce sens l'intérieur de la zone est à gauche.
On considère trois points successifs M, N, P tel que la frontière soit convexe (ça existe toujous cf. ci-après) càd de manière équivalente :
$ en N l'angle orienté (MN, MP) a un sinus positif (ceci est pour le test informatique)
$ P est à gauche par rapport à MN quand on va de M à N (sens choisi au départ).
Le segment MP est le candidat initial.
Mais comme la frontière n'est pas nécessairement convexe [MP] coupe éventuellement la frontière ce qui implique qu'il existe des points de la frontière à l'intérieur de MNP.
On a ceci d'agréable : si un point K de la frontière est à l'intérieur de MNP alors il existe un sommet de la frontière S qui est dans l'intérieur de MNP. De plus l'angle orienté (MN,MS) est plus petit (ou égal) que (MN,MK) (si on se restreint à [0,pi] ou autrement son cosinus est plus petit)
En effet : K est sur un côté [S'S"] de la frontière alors Sur une figure on voit facilement (la preuve demande juste un peu de patience mais n'est pas difficile) que :
si S' et S" sont à l'extérieur ou à la frontière de MNP alors ce point intérieur K implique que [S'S"] coupe deux côtés du triangle MNP donc au moins un des deux côtés de la frontière [MN] et [NP] (au mieux ça coupe en M, N ou P mais ceci contredit que [S'S"] soit un côté car S' et S" ne sont plus consécutifs)
S' ou S" est à l'intérieur à la fontière de MNP, on le note S, l'autre T. Plusieurs cas peuvent se présenter :
1er cas : T est aussi à l'intérieur, une petite figure et on voit que l'angle (MN,MK) est minimum à un des deux sommets que l'on renomme S si par malchance c'est T. C'est un minimum strict sauf dans le sous-cas particulier : M, S et T sont alignés (on reverra ce cas)
2ème cas : T est à la frontière ce qui implique que T est un des sommets M, N ou P car ceux-ci sont consécutifs si T=N alors ceic implique que S qui est un adjacent de T soit aussi adfjacent de N donc S=M ou P ce qui contredit que S est intérieur. On a donc T=M ou P. Si T=P S minimise (MN, MK) (strictement) pour K sur [ST] pas de problème. Le cas T=M est un cas particulier qui sera traité à part (on a quand (MN, MS) minimise (MN,MK) (ils sont tous égaux).
3ème cas : T est à l'extérieur de MNP [ST] coupe la frontière de MNP en un point qui n'est pas un sommet car S et T sont adjacents sur la frontière ; qui n'est pas non plus sur les côtés de la frontière [MN] et [NP] donc coupe ]MP[ on a bien (MN,MS) minimal (strictement)
En résumé :
s'il y a des points de la frontière intérieurs à MNP ou sur ]MP] (il y a au moins P) alors :
i) c'est en un sommet S de la frontière que (MN,MS) est minimal
ii) le minimum ne peut être atteint par un point autre qu'un sommet que si deux sommets adjacents S et T sont alignés avec M les angles on a alors (MN,MS)=(MN,MT)
iii) si plusieurs points minimisent (MN,MK) alors le minimum pour ces points K de MK est atteint en un de ces sommets sauf dans le cas pour le cas particulier où le sommet L antécédent de M minimise l'angle (MN,MK)
Dans le cas où L n'est pas le minimum, des points de la frontière à l'intérieur de MNP, ou sur ]MP] qui minimise (MN,MK) et en cas d'égalité minimise MK est un sommet de la frontière autre que M et N (ouf nous voilà ramené à l'étude d'un nombre fini de points)
Soit S un tel sommet, si S est distinct de M (cf 2ème cas) alors [MS] ne coupe pas la frontière ou est un côté de la frontière.
En effet, soit un point K de la frontière sur ]MS[ on a à la fois (MN,MS)=(MN,MK) et MK<MS ce qui contredit la minimalité de S.
Si L minimise les (MN,MK) [NL] ne coupe la frontière qu'en N et L.
En effet, tous les points G de [NL[ vérifient (MN,MG)<(MN,ML) donc aucun n'est sur la frontière
Remarque 1 : il est clair que prendre comme segment [ML] ne fait pas avancer dans ce cas car c'est déjà un côté de la frontière donc on n'ajoute rien.
Remarque-précision : tous les points K de ]LM[ minimisent aussi cet angle mais bien que MK<ML pour tous ces points ce sont les seuls de la frontière or aucun d'eux n'est un sommet donc la restriction aux sommets est bien justifié.
Ce qui précède se limite aux sommets de la frontière qui sont intérieurs à MNP ou sur ]MP] (P étant le 1er candidat), comment déterminer si un sommet est ainsi ?
un des moyens :
soit T un sommet autre que M et N (et P)
on détermine l'intersection I de (MS) et de (NP)
si I est extérieur à ]NP[ (vérification : NI+IP distinct de NP, ce sont des longueurs) alors T n'est pas ainsi
si T n'est pas entre M et I alors T est rejeté (vérification MT+TI distinct de MI, toujours des longueurs)
sinon T doit être testé pour le minimum car il n'est pas extérieur, il ne peut être sur [MN] ou [NP] (à moins que la frontière soit mal définie) donc est intérieur ou est sur ]MP[
Ceci constitue le 1er test
2ème test : le minimum (S est le minimum avant le test de T)
si cos(MN,MT)>cos(MN,MS) T rejeté
si cos(MN,MT)<cos(MN,MT) T remplace S
si égalité
MT<MS T remplace S
MT>MS T rejeté
MT=MS erreur : on a testé S=T deux fois
Astuce pour accélérer :
1) ce qui a été montré pour P peut l'être pour les autres sommets sauf pour L (mais ça marche aussi) donc remplacer dans le 1er test P par S (ça rejètera plus de points dès cette étape)
2) ajouter un test plus rapide (mais non suffisant) avant le test 1 : si T a une ordonnée qui n'est pas comprise entre la plus petite de celle de M, N et P et la plus grande de ces trois mêmes points alors T peut être rejeté, il en est de même pour les abscisses. Il est plus raide de comparer les coordonnées qui n'ont pas besoin d'être calculées que des tests de longueur (s'il y a un grand nuage la plupart des sommets seront rejetés dès ce test.
Pour l'instant on n'a construit qu'un segment et après ?
Ben... on recommence.
Après la construction du 1er segment on se retrouve avec deux parties d'intérieur disjoint ne se touchant qu'n le nouveau segment construit, on peut recoùmmencer avec ces deux parties (les segments construits sont çà l'intérieur de ces parties donc ne peuvent se couper on est tranquille)
On a des divisions de branches successives qui ne s'arrêtent que lorsque on aboutit à un triangle, une fois que toutes les parties auront été suffisamment découpées on aura une triangularisation.
Pourquoi existe-t-il nécessairement un sommet "convexe" si tous sont concaves on tourne constamment vers la droite en tournant dans le sens direct. Quand on a fini de boucler on se rend compte que l'on a tourné dans l'autre sens (sur une figure c'est évident)
Comment déterminer le sens direct : le plus simple on prend le sommet O de plus grande abscisse, de ces deux adjacents A et B celui qui minimise cos(i,OC) C=A ou B est le successeur de O quand on tourne dans le sens direct.
Maintenant reste le problème évoqué par Jean-Paul, il faudrait regarder sur des exemples si il n'y a pas possibilité de choisir les sommets M, N et P de telle manière à éviter au mieux les angles trop aigus (ou ajouter des sommets au cas quand ça devient inévitable)
Bonjour,
Je pense qu'il faut chercher du coté de la triangulation de Delaunay:
http://bobuse.free.fr/Delaunay/
Ca doit être beaucoup plus efficace algoririthmiquement que mon procédé (ceci dit ça m'a amusé d'en trouver un
Sinon grace à cette indication j'ai pu trouver ceci : triangulation
méthode pour non seulement trianguler une surface (méthode de Delaunay comme quoi ) mais également maillage en tétraèdre d'un polyèdre quelconque dont la triangulation de la surface est donnée (apparemment parfois il faut ajouter au moins un point).
bonjour,
il existe beaucoup de façons de trianguler le plan à partir d'un semis de points. La triangulation de Delaunay a des propriétés particulières, elle est duale (au sens de la dualité des graphes) de la tessellation en polygones de Voronoï.
On peut aussi la caractériser de la façon imagée suivante: si on fabrique une "planche de fakir" en enfonçant un clou dans une planche aux coordonnées du semis de points donné, et si on promène au-dessus de la planche une sphère suffisamment grande (qui joue le rôle du fakir), cette sphère va reposer sur trois pointes. Cets trois clous appartiennent à l'un des triangles de la triangulation de Delaunay (à vrai dire, il doit y avoir des problèmes sur les bords, si les points sont en nombre fini).
