Discussion :

[electroremy]

Bonjour,

J'ai téléchargé et testé Triangle.NET

ici : https://github.com/eppz/Triangle.NET

et ici : https://archive.codeplex.com/?p=triangle

Ca correspond à mes besoins, l'application de test montre de bons résultats et je souhaite utiliser Triangle.Dll dans un de mes logiciels en VB.NET

Poly2Tri n'est plus mis à jour depuis plusieurs années et elle comporte un bug non résolu bloquant, l'auteur de Poly2Tri l'a reconnu à la fin d'un long fil de discussion en anglais mais dommage sur la page d’accueil, Poly2Tri est toujours présentée comme la meilleure bibliothèque de triangularisation, robuste et réussissant tous les tests... c'est les joies de l'open source

J'ai passé des mois à adapter mon code à Poly2Tri il faut tout recommencer.

Je vais tester Triangle.NET, en intégrant Triangle.DLL a mon projet VB.NET.

La bonne nouvelle c'est que j'ai accumulé assez d'exemples "difficiles" pour bien tester la nouvelle bibliothèque.

Petit problème : Triangle.NET ne comporte aucune documentation et le code source en C# est avare en commentaires et subdivisé en de très nombreuses fonctions.

Je peux retrouver comment utiliser la DLL en passant beaucoup de temps à rétro-concevoir le code source de l'application exemple mais même si j'y parviens je risque de passer à côté de choses importantes.

L'un d'entre vous a-t-il déjà utilisé Triangle, Triangle.NET ou Triangle.DLL dans un projet (pas forcément en VB.NET d'ailleurs) ?

Merci

[wallace1]

Bonsoir,
Perso je n ai jamais utilisé mais si tu donnais déjà des pistes ciblants le ou les bugs peut être qui une âme charitable se jetterai a l eau.. Tu ne crois pas.... C est ça l esprit open source..

[electroremy]

Bonsoir,
Perso je n ai jamais utilisé mais si tu donnais déjà des pistes ciblants le ou les bugs peut être qui une âme charitable se jetterai a l eau.. Tu ne crois pas.... C est ça l esprit open source..

Le soucis c'est qu'on touche à un domaine des mathématiques où tout devient très compliqué... C'est un niveau assez élevé que seul une poignée de spécialistes maîtrisent vraiment.

En particulier, l'instabilité numérique, liée au fait qu'un ordinateur ne peut représenter des nombres réels qu'avec une précision limité complique énormément les choses.

Angus Johnson a traité ce problème dans sa bibliothèque Clipper en utilisant des entiers sur 128 bits ; sa solution revient en fait à utiliser des nombres à virgule fixe pour représenter des coordonnées plutôt que des nombres à virgule flottante. C'est très intelligent, car en virgule fixe, on peut translater une forme sans que la précision ne change.

Dans un système de coordonnées X,Y en virgule flottante, plus on s'approche de zéro, plus la précision augmente, mais plus on s'éloigne de zéro, plus la précision baisse.
Conséquence : le simple fait de déplacer une forme (translation) la déforme

C'est pour cela que dès qu'on manipule des coordonnées, il faut le faire en virgule fixe.

Malheureusement, Poly2Tri utilise des nombres réels (type single) et c'est en partie pour cela qu'il est dans l'impasse.

Le bug en question correspond à un cas de figure épineux dans lequel 4 points A,B,C,D sont alignés mais du fait des erreurs d'arrondi, le code considère que A,B,D sont alignés mais pas B,C,D ce qui fait qu'une des fonctions de Poly2Tri se retrouve dans une boucle infinie.

Contrairement à ce qu'on pourrait penser, corriger ce bug est tout sauf simple. Les points alignés peuvent correspondre à des appels différents d'une fonction récursive, sur un polygone de milliers de points, donc impossible de mettre un compteur pour stopper la boucle infinie.

J'aimerais modifier Poly2Tri pour qu'il utilise des entiers longs (64 bits) mais c'est plus facile à dire qu'à faire...

Angus Johnson avait du recoder toutes les opérations mathématiques en créant soit même le type entier long sur 64 bits... aujourd'hui c'est plus simple car ce type existe dans .NET

Le code de Poly2Tri en C# fait au moins 10.000 lignes, réparties dans de nombreuses classes et fonctions, et je n'ai que le code parsemé ici et la de quelques rares commentaires, je n'ai pas le dossier d'analyse et les explications qui va avec.

Quand on programme ce genre de chose, il y a toute une phase de réflexion "papier" avec des schémas, des explications, les grands principes de l'algorithme qui sont essentiels pour comprendre le code et que je ne possède pas.

Ma fameuse appli en VB.NET, si vous n'avez pas le gros classeur avec mes dessins, mes schémas, mes exemples, je peux vous donner le code, même en y passant des heures dessus et avec tous les commentaires en Français des points essentiels vous échapperons.

Pour ne rien arranger, si Poly2Tri est "juste" une implémentation de la CDT (triangulation de Delauney contrainte), le code est beaucoup plus compliqué que l'algorithme de Delauney (Delauney n'avait pas d'ordinateur et lors des calculs à la main on n'a pas de problème d'instabilité numérique) et surtout le bug se trouve dans l’algorithme "FlipScan" qui est le seul dans Poly2Tri a être à 100% une invention de l'auteur de Poly2Tri (les autres parties de Poly2Tri étant la transposition d'algorithmes connus)

Poly2Tri n'a plus de mises à jour depuis 2013

J'ai trouvé sur GitHub d'autres codes :

- Earcut (2017), mais elle est buguée

- LibTess (2015) , mais elles est buguée aussi

- Triangle.NET, elle est plus ancienne (2003), je ne sais pas si elle est vraiment robuste, mais ça a l'air d'être le cas

La seule doc complète sur Triangle est celle d'origine http://www.cs.cmu.edu/~quake/triangle.html mais elle correspond à l'utilisation de l'exe de 2003 en ligne de commande, rien à voir avec la description des fonctions de la DLL.

Au moins, Angus Johnson a fait pour Clipper une vrai doc : http://www.angusj.com/delphi/clipper...s/ClipType.htm

Actuellement, la seule solution pour moi c'est de faire le reverse ingeneering de la version C# de l'application test de Triangle.NET pour deviner le fonctionnement de Triangle.Dll
Et évidemment, le code C# de l'application Test n'utilise pas Triangle.DLL, car Triangle.DLL est le résultat de la génération de la solution...

Si au moins j'avais une application exemple qui utilise Triangle.DLL ce serait assez facile.

Bref, en 2018, nous sommes encore nombreux à nous casser des dents à réinventer la roue sur la triangulation de polygones simples avec trous.
Pourtant ce problème a été résolu des milliers de fois (c'est à la base de l'affichage 3D sur ordinateur et aussi de la création de fichiers STL pour imprimante 3D) mais le code robuste et rapide, que l'on voit tous les jours sans le savoir derrière nos écrans, n'est publié nul part.

Voilà