Эффективная триангуляция Делоне

Question

Я ищу реализацию .NET, которая строит триангуляцию Делоне из набора точек.

Я уже протестировал несколько реализаций, но все они работали только для небольшого количества точек (до 20 000).

Мне нужно что-то, что может обработать 500 000 очков в разумные сроки.

Answer 1

Если вы хотите построить 2D триангуляцию Делоне, используйте Triangle.Net .Это прямой порт C # знаменитой программы Triangle .

Answer 2

Я искал то же самое и нашел библиотеку C # 4.0 под названием MIConvexHull:

"Алгоритм выпуклой оболочки и библиотека для 2D, 3D и более высоких измерений. Код также можно использовать для вычисленияТриангуляции Делоне и сетки Вороного входных данных. Тесты показывают, что код выпуклой оболочки и код триангуляции 4 и более размерности соответствуют или лучше решения, предоставленного библиотекой C ++ CGAL. ​​"

http://miconvexhull.codeplex.com/

Обновление сентябрь / 2016:

Эта библиотека перемещена на Github, и похоже, что теперь она выпущена под лицензией MIT (некоторые примеры - GPL).Вы можете найти последнюю версию здесь:

https://github.com/DesignEngrLab/MIConvexHull

Документация на самом деле находится в исходном коде и проста в использовании.Вот соответствующий исходный файл для триангуляции Делоне:

https://github.com/DesignEngrLab/MIConvexHull/blob/master/MIConvexHull/Triangulation.cs

Если вы хотите увидеть оригинальную версию 2012 года. Посмотрите здесь:

http://miconvexhull.codeplex.com/SourceControl/changeset/view/e1b26677eb1a#MIConvexHull/Triangulation/Triangulation.cs

Answer 3

Существует решение под названием G # .

. Оно имеет триангуляции Делоне (также с линиями разрыва).Из графика производительности на их сайте вы сможете триангулировать 500 тыс. Баллов примерно за 30 секунд.

Answer 4

Существует реализация C #, которая может помочь вам сгенерировать диаграмму Вороного, а также триангуляцию Делоне: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Answer 5

Вы пробовали NetTopologySuite