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

Я ищу реализацию .NET, которая строит триангуляцию Delaunay из множества точек.

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

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

Ответы

Ответ 1

Если вы хотите построить триангуляцию 2D Delaunay, используйте Triangle.Net. Это прямой порт С# знаменитой программы Треугольник Шевчука.

Ответ 2

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

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

http://miconvexhull.codeplex.com/

Обновление Sep/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

Ответ 5

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

В нем есть триангуляции Делоне (также с ломаными линиями). На графике производительности на их веб-сайте вы сможете триангулировать 500 тыс. Точек примерно за 30 с.