計算給定頂點時多面體的質心和體積

Question

給定凸多面體（3D）頂點的位置，我需要計算多面體的質心和體積。以下代碼可在Mathworks site獲得。

function C = centroid(P) 
k=convhulln(P); 
if length(unique(k(:)))<size(P,1) 
    error('Polyhedron is not convex.'); 
end 
T = delaunayn(P); 
n = size(T,1); 
W = zeros(n,1); 
C=0; 
for m = 1:n 
    sp = P(T(m,:),:); 
    [null,W(m)]=convhulln(sp); 
    C = C + W(m) * mean(sp); 
end 
C=C./sum(W); 
return 
end 

該代碼是優雅的，但速度非常慢。我需要計算成千上萬個多面體的體積和質心數百次。在當前狀態下使用此代碼是不可行的。有沒有人知道更好的方法，或者這個代碼可以做得更快？我可以想到一些小的變化，例如用表達式來代替mean。

Answer 1

您可以加快代碼的速度取決於您想要如何計算質心。請參閱this answer about centroid calculation以瞭解您的選擇。事實證明，如果你需要實體多面體的質心，你基本上運氣不好。但是，如果只在多面體的頂點具有權重，那麼你可以簡單的寫

[k,volume] = convhulln(P); 
centroid = mean(P(k,:)); 

Answer 2

思考你唯一的選擇，如果quickhull不夠好是cudahull如果你想精確解。儘管如此，即使這樣，你只能獲得最大40倍的增長（看起來）。

我假設你製作的凸包每個都有至少10個頂點（如果它比這少得多，那麼你可以做的事情就不多）。如果你不介意「足夠接近」的解決方案。您可以創建一個限制每個多邊形頂點數量的quickhull版本。如果需要，限制計算的頂點數量也將允許計算最大誤差。

問題是，隨着凸包上頂點的數量接近無窮大，最終會出現一個球體。這意味着由於快速船體的工作方式，添加到凸包的每個附加頂點的效果*都比之前的更少。

*根據quickhull的編碼方式，這可能只是一般意義上的事實。在實踐中做到這一點將需要修改quickhull的遞歸算法，所以雖然總是計算「下一個頂點」（除了最後一個頂點被添加之後，或者該段沒有剩餘點），頂點實際上被添加到凸包中最大化增加多面體體積的順序（可能按照距離最遠到最遠的順序）。爲了跟蹤添加頂點的順序，您會產生一些性能成本，但只要待處理的凸包點與待處理點的比例足夠高，就應該值得。至於誤差，最好的選擇可能是在達到實際凸包時停止算法，或者最大體積增加量小於當前總體積的一定比例。如果性能更重要，那麼只需限制每個多邊形的凸包點數。

您也可以查看各種近似凸包算法，但是我上面概述的方法應該適用於具有確定誤差能力的體積/質心近似。

Answer 3

有一個簡單得多的方法來以最小的努力來計算音量。第一種風味使用多面體的3個局部拓撲信息集合，邊緣的切線單位矢量，該切線上的平面內法線的單位矢量以及該小平面本身的單位矢量（這些非常容易從頂點）。更多詳情請參閱Volume of a Polyhedron。

第二種風味使用面部區域，法向量和麪部重心根據此Wikipedia Article計算多面體體積。這兩種算法都非常簡單並且非常容易實現，並且通過簡單的求和結構也易於矢量化。我認爲這兩種方法比完成多面體的分解要快得多。

然後可以通過應用將完整多面體體積上的積分轉換爲多面體表面上的積分的發散定理來計算多面體的質心。詳細描述可在Calculating the volume and centroid of a polyhedron in 3d找到。我沒有檢查多面體的三角剖分是否真的是必要的，或者是否可以與多面體的更復雜的多邊形表面一起工作，但是在任何情況下，面的區域鑲嵌比體積鑲嵌要簡單得多。 總的來說，這種組合方法應該比卷積方法快得多。