3D Delaunay增量算法的最佳初始形狀是什麼？

Question

我正在做3D Delaunay，增量法。我已經用二維測試了它的初始三角形插入頂點，它的效果很好，但是如果我使用三角形作爲3D，某些頂點不會落入任何外接球體，因此它們不會被插入。 我嘗試過使用四面體，但如果第一個節點落入四個面中，則所有頂點都會創建朝向此新頂點的新邊，並刪除所有初始三角形。

Answer 1

無論你採取什麼樣的形狀，你總會不得不面對副作用。 最好的形狀是沒有形狀。 這就是我們正在做的CGAL庫 http://www.cgal.org 看看手冊，章節「二維三角剖分」和「三維三角剖分」。 請參閱或期刊論文https://hal.inria.fr/inria-00167199/

Answer 2

你可以閱讀我對這個問題的回答（Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices）。如果超級三角形太小，有時你會在超級三角形外面結束外接圓。你可以嘗試一個點多邊形測試來避免它。