魯棒，快速複雜多邊形（具有孔）的三角測量C/C++庫許可認證

我開源遊戲的開發者，Bitfighter。按下面的SO文章中，我們已經使用了網狀區代優秀的「三角」庫與我們在遊戲中AI用（機器人）：魯棒，快速複雜多邊形（具有孔）的三角測量C/C++庫許可認證

Polygon Triangulation with Holes

然而，我們遇到了一個小障礙當想要將我們的遊戲打包爲Debian時 - 使用'Triangle'庫會使我們的遊戲被視爲'非自由'。

我們一直非常高興與「三角」庫的表現，並沒有真的想放棄;不過，我們也不喜歡處理許可問題。因此，我們已經着手尋求一種適合的，許可的替代品，它的穩健性和速度與「三角形」相匹配。

我們正在尋找一個C或C++庫，用於將大的，複雜的，面積爲三角形，能夠處理以任何方式放置在一起的任何類型的不規則多邊形的，以及通孔。魯棒性是我們的首要需求，速度幾乎同樣重要。

我發現poly2tri，但是從它不能處理重合邊緣多邊形的錯誤受到影響。

我們已經發現了幾個庫，但似乎都來自一個東西或其他遭受：要麼太慢，或不處理孔，或從一些bug困擾。目前我們正在測試polypartition，我們寄予厚望。

什麼是偉大的'三角'圖書館的最佳選擇，但有一個許可證？

來源

2013-04-16 raptor

你能否詳細說明你真的需要像Triangle這樣的圖書館嗎？也許你可以自己編寫一些算法，並像你需要的那樣發佈你的代碼。 –

Triangle許可證是什麼？你有沒有試過給Jonathan Shewchuk發郵件詢問他是否會爲你重新授權？ –

@MareInfinitus我們有與他們的牆壁水平。一個關卡的整個可玩區域需要進行三角網格區域導航，以便我們的機器人可以移動。 – raptor

我找到了解決方案。畢竟，它是poly2tri，使用了優秀的Clipper庫，以及對輸入的一些小算法增加。

我們的過程如下：使用聯合與非零纏繞（這意味着內孔被卷繞相反的方向外的）

運行所有的孔通過推剪。 Clipper還保證在epsilon中沒有重複的乾淨輸入點。
將我們的孔過濾成逆時針順時針纏繞的孔。順時針孔意味着孔是迂迴和，有內部一個需要進行三角測量
使用poly2tri，三角測量外邊界和找到的每個順時針多邊形，使用空穴作爲輸入的其餘部分poly2tri另一個同心區域，如果他們發現在一個界限內。

結果： poly2tri似乎只是儘可能快地三角三角和成立至今，一直非常穩健與我們扔給它的一切。

對於那些感興趣的，here are our code changes。

更新

我試圖拔出我們推剪到poly2tri代碼，用我們的穩健性增加，到了我這裏開始獨立的庫：clip2tri

來源

2013-04-20 02:05:12 raptor

我只想跟進並說poly2tri，雖然很快，確實有時會遇到健壯性問題，通常涉及在epsilon中非常接近的點 – raptor

我使用了您描述的技術，也發現了poly2tri崩潰的一些情況。我可以用這個組合解決所有的情況：在Execute（）之前設置Clipper :: StrictlySimple（true）;之後，我使用CleanPolygon（），然後將edgeShrink（）應用於生成的多邊形和孔;最後，檢查具有相同座標的相鄰頂點並刪除其中的一個（當它到達少於3個頂點時，丟棄整個多邊形/孔）。 –

您可以看看CGAL的2D Triangulations包。用孔對三角形進行三角測量的示例給出here。包的許可證是GPLv3 +。

請注意，如果需要，只提取此包裝應該不會太困難。

來源

2013-04-17 05:06:40 sloriot

作爲一個小側面說明：

我最近不得不實施一個複雜的多邊形剪刀&三角形切割窗框進入房屋牆壁。

雖然我對Vatti削波器結果感到滿意，但poly2tri中使用的Delaunay三角測量太重，無法順利拖動窗框沿牆面的重心座標。抓我的頭有點後，我結束了欺騙這個更簡單的三角形有孔的工作：

http://wiki.unity3d.com/index.php?title=Triangulator

我所做的是通過水平最短剪裁聚的高度細分的牆面上。在我的情況下，他們總是矩形，但他們不需要。無論如何，它會迫使裁剪器只能使用常規或凹面的多邊形，因此可以使用更便宜的三角測量方法。

這裏是展示它的工作一些截圖：

https://www.dropbox.com/sh/zbzpvlkwj8b9gl3/sIBYCqa8ak

希望這有助於。

來源

2014-05-01 09:52:30

你是怎麼欺騙它接受漏洞的？ –

魯棒，快速複雜多邊形（具有孔）的三角測量C/C++庫許可認證

回答

相關問題