triangulation de polygones concaves et convexes
c’est un algorithme de triangulation de polygones simples.
UPDATE bon, donc je sais pas si ça vous arrive de vous sentir très intelligent pendant une semaine puis de redescendre sur terre avec l’impression d’avoir été ramoné par un mamouth.
c’est désagréable et ça vient juste de m’arriver:http://makc.coverthesky.com/FlashFX/ffx.php?id=18
ça annule juste tout ce qui suit.
en voila un qui sera bien utile dans certains cas.
c’est un algorithme de triangulation de polygones simples.
et qu’est ce qu’un polygone simple?
il faut qu’il ne soit pas pas auto-sécant (selfintersecting).
ça veut dire qu’on ne peut pas gérer tous les types de polygones. Mais en tous cas il va plutot vite et gère pas mal de cas de figure et c’est tout ce qu’on lui demande.
bon évidemment, il y a déja des gens qui l’ont porté:http://blog.touchmypixel.com/archives/17 mais je suis juste trop con et j’ai pas compris. donc j’ai repris à la base en observant les règles décrites dans ce document:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/introduction.html
du coup mon truc marche dans les deux sens et pas juste en counterclockwise. il y a aussi une méthode pour vérifier si le polygone est autosécant mais ça peut être super violent vu que chaque segment doit être testé avec tous les autres une boucle de N*(N-1) tests avec N points. faut passer le paramètre additionnel de la méthode cut() à true.
var triangles:Array = EarCutting.cut( points, TRUE );
ça peut sauver la vie quand on n’est pas certain que le poly passera mais ça coute cher.
Bon, pas grand chose d’autre à dire.
regardes la démo si ce que je viens de dire est imbitable
au click, on voit la forme à trianguler, puis au reclick, on voit les triangles.
les sources
sinon:
la fonction d’intersection de segments vient de chez Keith Hair: http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
on doit pouvoir accélérer le test sur les segment notes bien
Est-ce qu’il est possible de choisir le point de départ de l’envoyage de triangle ?
J’avais abandone il y a qques mois un trip avec Box2D justement par paresse d’implementer cet algo (et de chercher sur le net un truc deja fait).
En gros ct de pouvoir “decouper” des elements d’une scene avec la souris, et de jouer avec (mon truc marchait que avec des formes convexes du coup).
Ptet prendre la peine de le finir maintenant ^^
Merci pour le post en tout cas.
Génial ! T’es un génie
Ça m’a bien aidé avec un petit projet… ça semble un truc assez simple et outil dans pas mal de situations mais on trouve pas beaucoup de références ou liens outils ni sources façiles à lire… merci !
Keep up the good work - all your articles are very interesting and enlightening !