计算给定顶点时多面体的质心和体积

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找到。我没有检查多面体的三角剖分是否真的是必要的，或者是否可以与多面体的更复杂的多边形表面一起工作，但是在任何情况下，面的区域镶嵌比体积镶嵌要简单得多。 总的来说，这种组合方法应该比卷积方法快得多。