4D中的凸殼

Question

假設四個4D點[1/3,1/6,1/3,1/6]，[0,0,1/2,1/2]，[0,0,0 ，1]和[0,0,2/3,1/3]。如何在Python中計算它們的凸包的以下屬性？

1）設定的極值點

2）的凸包的投影到不同的座標軸，即X軸，Y軸，...。

Answer 1

我不能爲Python說話特別，但你想要的算法是Jarvis March (aka gift-wrapping method).開始通過尋找已知極值點一個（簡單地通過數字比較的座標）。然後，將該點與該集合中的每個其他點B配對，直到找到一個點，使得該集合中的所有其他點位於AB的一邊。這意味着B是一個極端點，因此用A替換B並重復該過程。最終的結果是極端點和凸包。

注意複雜度爲O（NH），其中ħ最終發現船體的頂點的數量。 Graham scan更高效，但它不能在三個維度上進行調整。