Recherche de chemin dans un environnement triangularisé

Bonjour,

Je bosse actuellement sur des algos de recherche de chemin dans des environnements triangularisés. Pour ça, je m'appuie notamment sur les travaux de Kallmann, et sur son article "Shortest Paths with Arbitrary Clearance from Navigation Meshes" : http://graphics.ucmerced.edu/papers/10-sca-tripath.pdf

Les triangles sont stockées avec une data structure en HalfEdge. Chaque HalfEdge possède un pointeur vers son next, et un vers son pair.

En fait, j'ai du mal avec ce que Kallmann appelle la "clearance" d'un angle (expliqué à la fin de la page 3, avec un schéma en haut de la page 4). Je comprends très bien ce que ça représente, le schéma parle très bien. Mais j'ai du mal à trouver un algo pour la calculer, cette "clearance", dans le cas où (sur le schéma) ac n'est pas une contrainte.

Pour l'instant j'ai quelque chose du type :

si l'edge en face du corner est contraint
- clearance = distance entre l'angle et la projection de l'angle sur l'edge en face
sinon
- clearance = min(dist(ab),dist(ac))

J'aimerais maintenant trouver un algo qui analyserait un à un tous les edges dans le bout de cercle abc et qui, s'ils sont contraints, calcule leur distance par rapport au corner, et la compare avec clearance. Et ça, j'y arrive pas :weird:

Je me relis, je sais pas si j'ai été très clair en fait :D

Quelqu'un a déjà été confronté à ce problème ?