algorithm - 计算 3D 缩减凸包

Question

我正在寻找一种算法，它可以提供我所说的 3D 中的“缩小的凸包”(与“缩小的凸包”不同)。我将收缩包 H' 定义为与某个原始凸包 H 的距离不小于 D 的空间体积。

从分析上讲，这可以通过将 H 的每个平面沿其法线向内移动 D，然后计算所得平面的凸包(如果存在)来形成。棘手的一点是一些平面可能会被修剪或丢弃，其他平面可能会越过其他平面，并且由于正常反转而被完全“剪掉”(如果 D 足够大)。我对如何执行算法有点模糊，但在下面有一些经过深思熟虑的想法。

我这样做是为了识别数据集中的点子集，这些点保证与原始点集的表面(假定为凸面，我有这个)的距离不小于给定距离。这是为了消除在我们正在进行的某些计算中干扰信号的表面效应。

我真的在寻找一个名字，或者任何人这样做的例子，或者另一种计算方法。理想情况下，一些古老的开放代码会很棒，但我认为我的问题太小众了。

我发现了缩小的凸包，但这似乎是一个不同的想法。目前我能找到的最接近的东西是“Hausdorff Cores”——然而这似乎是非凸多边形的更复杂的情况，而且非常密集。

---

除非你真的想要，否则不要阅读这里以外的内容。

当前的、不完整的/考虑不周的算法

识别缩减点集的缓慢方法(即当前方法)是计算所有点的符号距离，并拒绝那些小于给定距离的点。但是，这非常慢，因为点数可能高达 100M。我认为在原始船体上运行以生成缩小的船体，并计算其 AABB 和球形 BB，然后仅保留缩小的船体内部的那些可能要快得多(我希望 - 愿意接受评论说这是愚蠢的)。

我认为这应该是可能的，因为我并不严格需要每个点的完整距离信息，只需 D_point > D。所以一旦我知道这一点，我就应该能够停止。

我可以看到如何在 2D 中完成缩小的外壳，您可以在其中查看每个顶点，然后使用恒速 Eikonal 的解析解，然后沿着从每个角派生的向量移动顶点。

但是，对于 3D 版本 afaics，情况更为复杂，因为每个顶点都有多个面 (>2)。我目前的计划是单独查看每个边缘对，然后从那里开始工作(以某种方式 - 创建半空间并将它们合并？)来构建这个船体。

Answer 1

你的想法是缩小3D凸包，它的工作原理就像缩小2D图像一样，除了角度如何

算法的大纲(2D)看起来像这样:

1. Compute the convex hull.
2. For each point, P, in the convex hull:
3.     Find the hull points before and after, P
4.     Bisect the angle formed to obtain the angle, A, required.
5.     Create a new point, P', along the angle A at a distance, D, from `P`.
7.     Add P' to the scaled-down (shrunken) convex hull.

3D 中唯一的区别出现在第 3 行和第 4 行。在 3D 中，第 3 步获得 3 个点。在步骤 4 中，使用 3D 角度。因此，您会发现在图形/几何库中使用 3D 变换有很多好处，因为数学可能很棘手。