6

给定凸多面体 (3D) 的顶点位置，我需要计算多面体的质心和体积。Mathworks 网站上提供了以下代码。

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用表达来代替平均值。

4

3 回答 3

3

有一种更简单的方法可以以最小的努力计算体积。第一种风格使用多面体的 3 个局部拓扑信息集，边缘的切线单位向量，该切线上的平面内法线的单位向量和面本身的单位向量（从顶点）。有关详细信息，请参阅多面体的体积。

根据这篇Wikipedia 文章，第二种风格使用面部区域、法线向量和面部重心来计算多面体体积。这两种算法都相当简单，很容易实现，并且通过简单的求和结构也很容易矢量化。我想这两种方法都比对多面体进行完全成熟的镶嵌要快得多。

然后可以通过应用发散定理将整个多面体体积上的积分转换为多面体表面上的积分来计算多面体的质心。详细描述可以在Calculating the volume and centroid of a polyhedron in 3d 中找到。我没有检查是否真的需要将多面体细分为三角形，或者是否也可以使用多面体的更复杂的多边形表面，但无论如何，面的区域细分比体积细分要简单得多。总的来说，这种组合方法应该比体积方法快得多。

于 2013-11-12T15:57:17.250 回答
1

如果你想要精确的解决方案，那么如果 quickhull 不够好，你唯一的选择就是cudahull 。虽然，即使那样，您也只能获得大约 40 倍的最大增幅（似乎）。

我假设您制作的每个凸包至少有 10 个顶点（如果它比这少得多，那么您无能为力）。如果您不介意“足够接近”的解决方案。您可以创建一个版本的 quickhull 来限制每个多边形的顶点数。如果需要，您限制计算的顶点数也将允许计算最大误差。

问题是，当凸包上的顶点数接近无穷大时，你最终会得到一个球体。这意味着由于快速外壳的工作方式，您添加到凸包的每个额外顶点的效果*都比之前的要小。

*根据 quickhull 的编码方式，这可能仅在一般意义上是正确的。在实践中实现这一点需要修改 quickhull 的递归算法，所以虽然总是计算“下一个顶点”（除了在添加最后一个顶点之后，或者该部分没有剩余点），顶点实际上是添加到凸包中使多面体体积增加最大化的顺序（可能按最远到最远的顺序）。跟踪添加顶点的顺序会产生一些性能成本，但只要待处理凸包点与待处理点的比率足够高，就应该值得。至于错误，最好的选择可能是在达到实际凸包时停止算法，或最大音量增加小于当前总音量的某个比例。如果性能更重要，那么只需限制每个多边形的凸包点数。

您还可以查看各种近似凸包算法，但我上面概述的方法应该适用于体积/质心近似并具有确定误差的能力。

于 2013-01-07T00:39:33.317 回答
0

你可以加速你的代码多少很大程度上取决于你想如何计算你的质心。请参阅有关质心计算的答案以获取您的选项。事实证明，如果你需要实心多面体的质心，那你基本上就不走运了。然而，如果只有多面体的顶点有重量，那么你可以简单地写

[k,volume] = convhulln(P);
centroid = mean(P(k,:));
于 2013-01-06T22:56:47.873 回答