在3D空間中追蹤2D多邊形 - 適當的算法？

Question

我目前正在研究一個問題，我需要對3D空間中構成平面多邊形的節點進行正確排序（使用類似於右手規則的東西）。到目前爲止，我的想法是構建一個轉換矩陣將節點轉換爲x-y平面，然後使用Graham掃描。我需要確保用戶只輸入凸多邊形，所以如果我找到任何「內部」節點，我知道多邊形是凹的，可以拋出錯誤。除了檢查凸面之外，格雷厄姆掃描的排序過程將爲我排序節點。

我並不熟悉優化的幾何算法。這看起來像是一個適當/有效的過程嗎？或者有更好的方法：

1）按照一些規則（例如RH規則）和 排列多邊形的節點2）確保平面多邊形（可能不在x-y平面中）是凸的？

Answer 1

是的，這是一個非常好的解決方案。以下是如何實現它以忽略數字不準確性。

- take any 3 points; these determine the plane, rotate appropriately 
- check that abs(z)<THRESHOLD for all z-coordinates, now you can ignore them 
- perform Graham scan which is O(n log(n)) time 
- return order, else throw error if results.size < #points (non-convex) 

您可能希望充分選擇3點相距甚遠，或許多點的組合（仍然有它的問題），並作出閾值之間的最大距離的某一部分。

若干假設，這是可證明一樣好，你可以做漸近，因爲否則的話，你可以使用它來在不到O(n log(n))時間進行比較排序，我們知道這是不可能的，無需額外的知識（中問題映射就是將未排序數組的每個元素X放置在平面中的[X，X^2]位置加上[0，max^2]處的一個點）。