Discussion :

[FlashLogic]

Bonjour.

J'implémente pour la première fois une structure type quad-edge. C'est pour de l'intelligence artificielle. Je vise une implémentation respectant l'interface conventionnelle (Next, Rot...), tout en étant efficace (recherche des adjacences en temps constant) et souple (ajout/suppression de vertex, flip edge...).

Je n'ai jamais eu une implémentation des quad-edge sous les yeux. Je me pose donc des questions sur la nature des données stockées.

J'ai en tête d'implémenter 2 graphes A et B (duaux). Chaque sommet d'un graphe aura des références vers ses voisins directs en ordre CCW. Chaque sommet d'un graphe aura des références vers les sommets du polygone correspondant dans l'autre graphe, toujours en CCW.

Voilà, il semble que par dessus ça je peux implémenter efficacement l'interface quad-edge. Mais est-ce la façon "conventionnelle" de procéder ?

[bretus]

Bonjour,

Voilà, il semble que par dessus ça je peux implémenter efficacement l'interface quad-edge. Mais est-ce la façon "conventionnelle" de procéder ?

Ça me parait étrange de faire pointer un vertex vers des faces. Il n'est pas plus judicieux de faire pointer un edge vers une face?

Peut-être peux tu t'inspirer des structures présentes dans CGAL (Halfedge Data Structures) et JTS (com.vividsolutions.jts.triangulate.quadedge.QuadEdge)?

[FlashLogic]

Ah oui excellent lien merci !

[FlashLogic]

Un lien intéressant où ils expliquent une implémentation possible:

http://www.cs.cmu.edu/afs/andrew/scs.../quadedge.html

Apparemment ils ne stockent qu'un fragment des données, le reste se déduisant logiquement:

"Internally, our implementation stores only four essential pieces of information with each edge (origin vertex, left face, Onext, and quadedge index) and the rest of the adjacency operators (Dest, Right, Lnext, Rprev, Dnext, ...) are derived using Sym and Rot."

Je note aussi la phrase suivante:

"Duals are also extremely useful for Voronoi diagrams and Delaunay triangulation, but that's another course (computational geometry)."

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

[bretus]

"Internally, our implementation stores only four essential pieces of information with each edge (origin vertex, left face, Onext, and quadedge index) and the rest of the adjacency operators (Dest, Right, Lnext, Rprev, Dnext, ...) are derived using Sym and Rot."

Oui, une partie des opérateurs peut être calculé. Si tu as uniquement le vertex source et le edge opposé, tu calcules le vertex target comme étant la source du edge opposé.

"Duals are also extremely useful for Voronoi diagrams and Delaunay triangulation, but that's another course (computational geometry)."

Ton dual peut être implicite non?

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

Tout dépend de ce que tu veux faire en IA avec cette structure. Après, chercher une structure générique me semble voué à l'échec (c'est un peu comme chercher à faire une classe Arbre qui réponde de manière optimale à tous les besoins).

[pseudocode]

Je me demande donc si pour de l'IA, le mieux est de considérer une structure de graphes duaux ou une structure quad-edge. Sachant que les 2 sont apparemment équivalentes... peut-être devrais-essayer d'implémenter une structure polyvalente ?

La structure QuadEdge est un moyen "assez simple" à la fois pour naviguer dans un graphe dual et pour modifier ce graphe dual. Cette structure n'est optimale pour aucun des deux cas pris indépendamment, mais elle offre un bon compromis.

Elle a effectivement tout son intérêt dans l'implémentation des algos de triangulation, car on y alterne les étapes de navigation (find) et de modification (make/slice) aussi bien sur les faces que les edges.

[FlashLogic]

Je veux savoir implémenter de A à Z un pathfinding sur structure planaire polygonale. Notamment la méthode décrite dans la thèse de Douglas Jon Demyen:

http://citeseerx.ist.psu.edu/viewdoc...0.1.1.130.4581

Donc passer par la triangulation itérative de Delauney sous contrainte.

Je vais prendre le temps qu"il faut et je compte passer par une bonne compréhension des bases, donc de la structure de données.

Je vais implémenter les algos sur les 2 structures (Quad-edge et graphe/dual) pour les comparer. Même si je ne me fais pas d'illusion, le quad-edge sortira vraisemblablement vainqueur, mais ça me permettra de bien comprendre les différences.