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

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

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

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


.net c# delaunay triangulation
person AlonH    schedule 05.09.2011    source источник
comment
странно, что всего 20000 баллов он может обрабатывать; у него только время работы O (n * log (n))   -  person Simone    schedule 05.09.2011
comment
Вы пробовали реализацию C # на s-hull.org? Используемый алгоритм должен быть быстрым.   -  person CodesInChaos    schedule 05.09.2011
comment
Я использовал алгоритм s-hull.org. Производительность значительно снижается, когда вы набираете 100 000 или более баллов из-за феноменального количества рекурсий, происходящих в коде. Не знаю, как это победить. Я слышал, что существует еще один алгоритм, который снижает рекурсивность кода, не знаю, как он назывался (возможно, это был Де Валл или что-то в этом роде).   -  person code4life    schedule 07.09.2011
comment
Вы использовали qhull? Хотя это не C #.   -  person Joan Venge    schedule 14.01.2012
comment
Я использовал Triangle, и он мне очень понравился. cs.cmu.edu/~quake/triangle.html Удачи! Максим   -  person Maxim Eliseev    schedule 09.02.2012
comment
Что для этой конкретной проблемы является разумным временем, кстати? Сможете ли вы жить с 60-секундным оборотом? 1 секунда? 100 мс?   -  person Mike    schedule 09.02.2012
comment
Я только что написал триангулятор C #, который занимает ~ 30 секунд на 500 тыс. Точек входных данных, не распараллеленных. Не знаю, полезно это или нет, могу опубликовать.   -  person Mike    schedule 10.02.2012
comment
@Mike Это довольно медленно. Треугольник должен управлять таким количеством точек примерно за 1 с.   -  person David Heffernan    schedule 18.03.2012
comment
@Mike, 500 тыс. Очков и 30 секунд, я думаю, производительность действительно хороша, не могли бы вы поделиться ею.   -  person sendreams    schedule 27.06.2015

Ответы (5)


arrow_upward
19
arrow_downward

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

person Ashwin Nanjappa    schedule 04.07.2013
comment
Похоже, что Triangle.Net находится под лицензией MIT, но очевидно, что это прямой перенос Triangle на C #, а Triangle не лицензировался в рамках MIT. Сомневаюсь, что это законность. - person Eagle-Eye; 20.07.2014
comment
В итоге я сам использовал Triangle.NET. Используя его для Unity 5, нужно было исправить только две мелочи, чтобы заставить .Net 4.5 работать с единством. - person Mikael Högström; 07.08.2015
comment
@ MikaelHögström, не могли бы вы рассказать нам, что вы исправили в треугольнике.net, чтобы он работал с единством? - person seek; 21.02.2016
comment
Я точно не помню, что, но насколько я помню, это было не так уж сложно, думаю, заняло час или два. Если вы застряли, я могу поделиться с вами своим кодом! - person Mikael Högström; 23.02.2016
comment
Это библиотека, которая наконец-то сработала для меня, особенно порт Unity, найденный на github: github. com / parahunter / Triangle-net-for-unity Получил гораздо более органичные, не похожие на сетку результаты в моих усилиях по созданию ландшафта. Спасибо, что разместили это. Это было довольно легко использовать, и DelaunayDemo в папке Scenes этого порта Unity - на высшем уровне. - person Joseph Knight; 30.04.2016
comment
Поскольку @ MikaelHögström et al не документировали свои исправления, а на основном сайте все еще есть ошибки в текущей версии, вот ссылка на два исправления, которые вам нужно сделать, занимает примерно 2 минуты: Triangle.codeplex.com/discussions/651181 - person Adam; 09.07.2016
comment
Для Unity 5 используйте this, он содержит все необходимые исправления. . Протестировано с Unity 32 bit 5.5 и 5.6 в Windows 7. - person Vignesh; 25.06.2017
comment
@ Орлиный глаз: Конечно. В частности, на исходном веб-сайте говорится: Обратите внимание, что хотя Triangle находится в свободном доступе, он защищен авторским правом автора и не может быть продан или включен в коммерческие продукты без лицензии. - person O. R. Mapper; 02.07.2018

arrow_upward
16
arrow_downward

Я искал то же самое и нашел библиотеку 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

person Pablo    schedule 17.08.2012
comment
По-прежнему помогает. Он устанавливает диаграмму из 500 тыс. Точек за считанные секунды. - person OzrenTkalcecKrznaric; 22.10.2015
comment
Никаких загрузок, никаких документов. На странице загрузки с гордостью говорится, что вы не можете его загрузить, и вместо этого вам нужно интерпретировать проприетарный формат проекта, угадывать свой путь, пока вы не найдете несколько исходных примеров, и перепроектировать инструкции. И это GPLv3, которая исключает множество применений. Не самая лучшая библиотека! - person Adam; 09.07.2016
comment
Если вы посмотрите репозиторий Github, вы обнаружите, что исходный код задокументирован и лицензирован MIT. - person Pablo; 10.09.2016

arrow_upward
2
arrow_downward

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

person Mohit Vashistha    schedule 28.01.2012
comment
Это оболочка для JTS, которая явно не поддерживает 3D - tsusiatsoftware.net/ jts / jts-faq / jts-faq.html - person JumpingJezza; 17.03.2016

arrow_upward
1
arrow_downward

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

person blackbada_cpp    schedule 01.03.2012

arrow_upward
1
arrow_downward

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

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

person wackmc    schedule 04.11.2012