Algorithme graphique 2D

[Médiat]

Bonjour,

Je dispose d'une courbe fermée, discrétisée, comme sur l'exemple en rouge ci-dessous, je me demandais s'il existe un algorithme "bien connu" pour trianguler l'intéieur de la courbe, on peut constater sur l'exemple en jaune que la solution "naturelle' ne marche pas toujours.

Ma question est bien "Est-ce que cela existe" mais si la réponse est non je suis ouvert aux suggestions, mais j'ai des pistes





-----

[polo974]

Bonjour Médiat,
oui, bien sûr que ça existe...
déjà dans les années 80, on parlait de l'algo de Delaunay.

que certains ont amélioré depuis...

et si tu as la flemme totale, il y a des codes dispos à adapter à ton projet.

https://fr.wikipedia.org/wiki/Triang...%27un_polygone
https://fr.wikipedia.org/wiki/Triangulation_de_Delaunay

et selon ce que tu cherches: http://www.cs.cmu.edu/~quake/triangle.html ("belle" triangulation, source dans le zip)

Sinon, il semble que tu as déjà discrétisé tes courbes, sans indiscrétion, selon quel critère/algo ? (perso, j'ai un truc qui sur 1 point, donc 2 segments les recoupe en 2 quand la surface du triangle initial plus est supérieure à une certaine limite.)

en fait, il y en a plein...
https://awesomeopensource.com/projec...-triangulation
https://www.geom.at/fade2d/html/

[Médiat]

Bonjour polo,

Merci beaucoup, je vais regarder tout cela avec attention, vu la banalité de la question je me doutais que quelque chose existait. (je suis curieux de voir si ces algorithmes utilisent ou non les idées qui m'ont traversé).

Mes courbes sont paramétrées, une première façon de les discrétiser est de découper le domaine en morceaux égaux (certainement la solution la plus simple et la plus bête) une deuxième façon consiste à découper la courbe en segments de longueurs égales. Ces deux méthodes sont simplistes et rapides, mais elles ne détectent pas les "singularités" de la courbe (ce qui ne me dérange pas), quant à la taille des triangles elle m'est indifférente, la courbe est plane, mais le but est de fermer (boucher) une surface si la courbe est un carré, deux triangles résolvent bien le problème.

Merci beaucoup.

[Paraboloide_Hyperbolique]

Bonjour,

Je recommanderais le troisième lien cité par polo (à savoir https://www.cs.cmu.edu/~quake/triangle.html). Celui-ci est en effet l'un des plus populaires en termes de performances et de robustesse.

[A voir en vidéo sur Futura]

[Médiat]

Merci Paraboloide_Hyperbolique,

J'ai téléchargé le source, malheureusement il utilise une librairie que je n'ai pas, et il y a assez de "trucs sur mon ordi .

Je pense m'orienter vers l'algorithme des oreilles (voire vers celui auquel j'ai pensé) et développer moi-même

[umfred]

ça doit être les librairies X11, qui sont des librairies Linux pour le terminal X; sous windows, il faut passer par cygwin, ou par une machine virtuelle linux (ou encore le WSL sous windows 10 https://docs.microsoft.com/en-us/windows/wsl/about )

[Médiat]

Merci umfred de l'info, mais cela me fait beaucoup de boulot, pour un algorithme que je peux sans doute écrire en 1 heure (je parle des oreilles), certainement moins général et moins optimisé mais mes polygones ont une moyenne de 200 points (et le plus gros doit en avoir 1000) donc les problèmes de performance ne sont pas critiques

[polo974]

Il n'y a besoin de X11 que pour le programme de visyalisation.
Le programme de triangulation n'a besoin que de la librairie mathematique.
Il doit bien y avoir un équivalent chez microsoft.

[Médiat]

Merci polo, mais l'algorithme des oreilles est bien documenté et facile à programmer, c'est dans cette direction que je compte aller
Encore merci de me l'avoir fait connaître