高效的Delaunay三角剖分

我正在尋找一個.NET實現，從一組點構建Delaunay三角剖分。高效的Delaunay三角剖分

我已經測試了幾個實現，但它們都只適用於少量點（高達20,000）。

我需要能夠在合理的時間內處理500,000點的東西。

2011-09-05 AlonH

這很奇怪，它只能處理20000點;它只有O（n * log（n））運行時間 – Simone

您是否在http://www.s-hull.org/上試過C＃實現？它使用的算法應該是快速的。 – CodesInChaos

我已經使用了s-hull.org算法。由於代碼中出現的遞歸數量驚人，一旦達到100,000或更高點，性能就會顯着降低。不知道如何擊敗它。我聽說有另一個算法，它減少了代碼的遞歸性，不確定它被稱爲什麼（可能是De Wall或其他）。 – code4life

2012-01-28 11:48:22 Mohit

這是JTS的封裝 - 顯然不支持3D - http://tsusiatsoftware.net/jts/jts-faq/jts-faq.html – JumpingJezza

2012-03-01 19:16:55 BlackBada

我一直在尋找同樣的事情，我發現了一個C＃4.0庫稱爲MIConvexHull：

「用於二維，三維和更高維度的凸包算法和庫，該代碼還可用於計算輸入數據的Delaunay三角剖分和Voronoi網格，基準表明凸包代碼和4和更高的尺寸三角測量代碼與C++庫CGAL提供的解決方案相比甚至更好。「

更新月/ 2016：

這個庫已經轉移到Github上，似乎現在是在MIT許可下（一些的例子是GPL）發佈。你可以在這裏找到最新版本：

的文件實際上是在源代碼，它是簡單易用。下面是Delaunay三角相關的源文件：

如果你想看到從2012年的原始版本看看這裏：

2012-08-17 17:47:05 Pablo

仍然有訣竅。它在幾秒鐘內設置了500K點圖。 – OzrenTkalcecKrznaric

沒有下載，沒有文檔。下載頁面自豪地說，你不能下載它，而你需要解釋專有的項目格式，猜你的方式，直到你找到一些源代碼示例，並反向工程的說明。它是GPLv3，它排除了很多用途。不是一個好的圖書館！ – Adam

如果你看看Github的回購，你會發現源代碼被記錄下來，並且它在MIT的授權下。 – Pablo

有一個叫G#解決方案。

它有Delaunay三角剖分（也有斷裂線）。從他們網站上的性能圖表中，您應該能夠在30秒內對500k點進行三角測量。

2012-11-04 22:58:07 wackmc

不好的框架，而不是免費的 –

如果要構建2D Delaunay三角測量，請使用Triangle.Net。它是Shewchuk着名的Triangle程序的直接C＃端口。

2013-07-04 03:22:32

你真棒:)。我在尋找完全一樣的東西：D – Flamy

看起來Triangle.Net是根據MIT許可證獲得許可的，但顯然它是一個三角形到C＃的直接端口，Triangle未經MIT許可。我懷疑這是合法的。 –

我最終自己使用了Triangle.NET。將它用於Unity 5，只需修復兩個小問題即可使.Net 4.5與Unity一起工作。 –

回答