代表更高維度的凸包（3+）

Question

在2d中，凸包表示爲基本巡視點。似乎這種表示可能會超出2個維度。因爲我很快就會和他們一起工作，所以我想提前知道這個標準是什麼意思，如果有這樣做的話，那麼其他人就可以使用它。

澄清： 我所指的標準是在輸出格式方面，例如從輸出中，程序可以將船體用於其他事情。

Answer 1

點的集合總是足以完全指定任何船體，但是在實踐中，計算點的連通性通常需要再次運行船體算法。

編輯：如果你需要邊緣或面部數據，你可以在quickhull等算法中免費得到這個數據。我會假設N個維度。基本上，人們不斷地找到由N個點定義的平面以及相關的法向量。如果法向矢量給出的平面邊上仍然存在點，則可以創建由最遠點定義的新平面，並刪除新平面的錯誤邊上的任何平面。這些平面定義（N-1）個單元（在3D中，這些是面，2D是邊），並給出了算法中此時的最高尺寸的船體表示。算法一直繼續，直到沒有錯誤點上的平面。最後的飛機給出最後一個船體的（N-1）個單元，其定義點是頂點。關於平面的問題可以用N個以上的點來定義，但有多種方法可以處理它們，見http://www.qhull.org/使用了許多策略，其中最明顯的是使用Delaunay三角測量法（它一旦你有一個凸包算法，你就有了代碼）。

在兩個維度中，您有一個點和一些邊的列表。如果您願意，您可以命令他們進行巡迴演出。你需要邊和任何船體的點。

在3D中，您需要點和邊，或者面和邊，或點和麪作爲最小表示。但有時候有三個人可能會很高效。也許你想用他們所製作的邊緣來表現人臉，也許這些觀點，也許都是。這是記憶與時間或可達性之間的折衷。

在高維中有相同的東西，但是單元（3D +面）以及面，邊和點。隨着更高的尺寸，存儲單元數據所需的空間可能變得相當大，因此點和邊的集合可能變得可取，您可以在這裏看到這種模式的證據：http://en.wikipedia.org/wiki/Hypercube#Elements。

然後，您可以選擇高維單元如何表示，它們是參考點，邊，面，低維單元，高維單元。問題是：你跟蹤不同維度單元之間的每一個關係（比如面和邊之間的關係，但是更高的維度）？或者這些關係類型的數量將超線性增加，這是一個額外的組合數，每種類型的數字關係都需要表示。所以，你把它全部扔掉，並在飛行中計算它。即使是中等規模的問題，空間和時間的要求也會變得非常重要 - 因此選擇代表權取決於你在做什麼。

就我個人而言，我通常使用帶邊的點集合來引用它們。

ND幾何：http://en.wikipedia.org/wiki/Polytope