Triangulation efficace des Delaunay
je cherche une implémentation .NET qui construit la triangulation Delaunay à partir d'un ensemble de points.
j'ai déjà testé quelques implémentations mais elles n'ont toutes fonctionné que pour une petite quantité de points (jusqu'à 20.000).
j'ai besoin de quelque chose qui peut gérer 500 000 points dans un délai raisonnable.
5 réponses
si vous voulez construire la triangulation 2D Delaunay, utilisez Triangle.Net. C'est un C# port direct du célèbre Shewchuk Triangle programme.
je suis à la recherche de la même chose et j'ai trouvé un C# 4.0 bibliothèque appelée MIConvexHull:
"Une enveloppe convexe de l'algorithme et de la bibliothèque pour la 2D, la 3D, et les dimensions supérieures. Le code peut également être utilisé pour calculer les triangulations Delaunay et les mesures Voronoi des données d'entrée. Les benchmarks indiquent que le code de coque convexe et le code de triangulation dimensionnelle 4 et supérieure est égal ou supérieur à la solution fournie par la bibliothèque C++ CGAL."
http://miconvexhull.codeplex.com/
Mettre À Jour Le Sep/2016:
cette bibliothèque s'est déplacée vers Github et il semble qu'elle soit maintenant disponible sous la licence MIT (certains exemples sont GPL). Vous pouvez trouver la dernière version ici:
https://github.com/DesignEngrLab/MIConvexHull
la documentation est en fait dans le code source et elle est simple à utiliser. Voici le fichier source correspondant pour La triangulation de Delaunay:
https://github.com/DesignEngrLab/MIConvexHull/blob/master/MIConvexHull/Triangulation.cs
si vous voulez voir la version originale de 2012. Jetez un oeil ici:
il y a une implémentation C# qui pourrait vous aider à générer le diagramme de Voronoy ainsi que la triangulation Delaunay: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C