Question à propos de Delaunay..

Version imprimable

13/02/2013, 10h39
souviron34

Question à propos de Delaunay..

Bonjour à tous..

Une petie question...

Contexte : soit un polygone, et une triangulation de Delaunay de ce polygone..

Question : peut-on dire que la triangulation Delaunay consiste à trouver les segments les plus proches maximisant les angles relatifs ??

Je m'explque : Delaunay est censé éviter les triangles aplatis : "Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation......However, the Delaunay triangulation does not necessarily minimize the maximum angle."

Si donc on fait la triangulation d'un polygone (sans ajouter de points), je me pose la question ci-dessus...

En d'autres termes, si on cherche le segment le plus proche d'un sommet et maximisant l'angle relatif, peut-on dire que l'on a trouvé le segment le plus proche au sens de Delaunay ??
14/02/2013, 10h53
souviron34

Personne pour me fournir une idée, une piste, ou une réfutation ??

La question est :

Si j'ai un polygone, et un point intérieur (par exemple) à ce polygone :

si , parmi l'ensemble des segments du polygone, je ne cherche pas celui qui est le plus proche, mais celui qui est le plus proche ET pour lequel le rapport distance/angle est maximum, est-ce que cela satisfait au critère de Delaunay ?

Le segment le plus proche peut donner un triangle extrêmement aplati. Si je prend en compte le rapport distance/angle, lje peux éventuellement trouver un segment un peu plus éloigné en distance, mais dont le rapport distance/angle est plus grand.. Est-ce que ce segment correspondrait alors "au segment le plus proche au sens de Delaunay" ?
14/02/2013, 12h35
souviron34

Je me suis trompé dans l'expression ..

Ce n'est pas :

Citation:

Envoyé par souviron34

pour lequel le rapport distance/angle est maximum

mais

pour lequel le rapport de distance est minimum ET le rapport d'angle est maximum...

Le segment le plus proche peut donner un triangle extrêmement aplati. Si je prend en compte les rapports de distance et d'angle, je peux éventuellement trouver un segment un peu plus éloigné en distance, mais dont le rapport d'angle est plus grand.. En gros, celui qui minimise le rapport de distance tout en maximisant le rapport d'angle... Est-ce que ce segment correspondrait alors "au segment le plus proche au sens de Delaunay" ?
14/02/2013, 23h52
pseudocode

Je ne pense pas qu'il y ait un critère de décision sur la distance point/segment dans une triangulation de Delaunay contrainte.

Ca peut bien sur être une heuristique pour choisir un segment candidat, mais je ne pense pas que ca soit suffisant pour construire à coup sûr une triangulation de Delaunay.
15/02/2013, 10h29
souviron34

Citation:

Envoyé par pseudocode

J
Ca peut bien sur être une heuristique pour choisir un segment candidat, mais je ne pense pas que ca soit suffisant pour construire à coup sûr une triangulation de Delaunay.

Disons que mon questionnement était en sens inverse :

Si j'obtiens le segment du polygone à la fois le plus proche et donnant l'angle maximum, pourrais-je dire que ce segment définit avec le point un triangle de Delaunay ?

(dans ce cas, bien que cela ne construise pas la triangulation, on aurait sans conteste un des triangles partant du point. A la limite, on pourrait itérer en laissant ce segment de côté pour obtenir les autres triangles issus de ce point)