確定一個點是否在CGAL的3D Alpha形狀表面的內部或外部

我正在使用CGAL來使用ex_alpha_shapes_3 example創建一組3D點的凹形。接下來，我想知道空間中的點查詢是否位於由三角形凹殼面（ex_alpha_shapes_3代碼的輸出）創建的曲面內。一個「多邊形點」技術應該對此有用。如果有人能幫助我解決這個問題，我將不勝感激。確定一個點是否在CGAL的3D Alpha形狀表面的內部或外部

來源

2014-07-15 Vahid

我不熟悉CGAL，所以我不知道在那裏實現光線追蹤和射線碰撞算法是多麼容易。如果這很難，而且性能也不重要，那麼如果一個點在一個alpha形狀內，那麼原始點集+查詢點的alpha形狀應該與原始alpha形狀相同，並且您可能能夠檢查這個「平等」。 –

感謝您的回覆。實際上，性能非常關鍵，因爲我需要在每個時間步驟重複此過程，並且我的數據集中可能會有相當多的點（數十萬甚至更多）。 – Vahid

您可以使用locate函數，並根據單純形點和單純形函數classify的輸出結果，直接瞭解您是在內部，外部還是邊界上。

無論單純型，EXTERIOR是外部，INTERIOR是內部。
如果點落在邊緣，定期是在邊界上奇異取決於是否有什麼隔離的優勢應該在你的設置
如果這些點上的頂點回落，定期是在邊界上和奇異是取決於是否一個孤立的輸入點應該在你的設置

來源

2014-07-15 20:01:40 sloriot

感謝您的有用答案。目前，我只使用「Alpha_shapes_3」來構造凹面。這是否意味着我需要首先在整個體積（由凹面覆蓋）內生成一個三角形網格，以便能夠使用「Traiangulation_3」中的「定位」功能？我是一名具有基本C++經驗的新CGAL用戶，所以這讓我有點困惑。 – Vahid

Alpha_shape_3繼承Triangulation_3。 – sloriot

我試圖通過將下面幾行添加到代碼中來使用locate函數，但是在編譯時出現錯誤。 – Vahid

我不知道CGAL，但有幾個啓發式可以使用，因爲你的多面體已知是凸的。基本上2D可以做很多工作。您可以使用任何軸，但假設我們正在XY平面中工作並暫時忽略Z分量。由於你的形狀是凸的，通常只有兩個三角形的XY座標圍繞着你的點的XY座標。對於任何三角形，您可以快速確定是否x [min] < x [point] < x [max]，同樣對於y。如果這些測試失敗，繼續前進。如果他們成功了，需要進一步測試來確定點是否實際在三角形內。找到2個可接受的三角形後，找到該點（X，Y）處每個三角形的Z值。如果點的Z位於面的Z值之間，則該點位於實體內部。

來源

2014-07-15 18:49:09 Logicrat

對於凸包，這似乎是一個有趣的方法，謝謝。但是，在我的情況下，我有一個凹包，其中可能包含多個體積（空間中未連接的部分）或兩個以上的XY圍繞查詢點的三角形。我想這種算法在這種情況下不起作用。 – Vahid

我的不好，我在你原來的問題中誤讀爲「凸」。然而，基本邏輯仍然適用，儘管它更復雜。你必須在2D中找到所有周圍的三角形。然後，如果Z軸上方或下方的三角形的數量爲奇數，則該點位於其中一個體積內，特別是包含其Z值在任一方向上與測試點最接近的三角形的體積。 – Logicrat

確定一個點是否在CGAL的3D Alpha形狀表面的內部或外部

回答

相關問題