language-agnostic - 剔除内部三角形

Question

我有数千个四边形数组；4 面 3D 多边形。我所知道的只是四角的坐标。

这些四边形的子集定义了 3D 形状的封闭外壳。其余的四边形位于这个封闭实体的内部。

如何确定哪些四边形是外壳的一部分，哪些四边形是内部的一部分？这不是性能关键代码。

---

编辑：对外壳形状的进一步限制

• 形状内部没有孔，它是一个单一的表面。
• 它包含凸面和凹面部分。
• 我有一些已知在外壳内部的点。

Answer 1

如果您的形状自相交，这可能很难实现，但是如果您能找到一个您知道在表面上的四边形（可能离质心最远的一个），然后在其周围绘制出同心圆的四边形。然后在它之外找到一个连续的四边形环，依此类推，直到你最终到达“对面”。如果你的四边形相交，或者内部连接，那就更难了。我会尝试分解那些相交的表面，然后找到所有可能的光滑表面，然后选择具有最大内部体积的表面。

Answer 2

这个怎么样？

计算四边形的法线向量（称之为“当前”四边形）。对该向量和所有剩余的四边形进行交集测试。如果它在向量的正部分与另一个四边形相交，则您知道当前四边形是内部四边形。对所有剩余的四边形重复此操作。

这假设四边形“面向”向外。

Answer 3

如果形状是凸的，它可以很容易地完成。当形状是凹的时，它更难。

在凸的情况下，通过计算所有点的平均值来找到质心。这给出了在内部具有以下属性的点：

如果您从质心向四边形的每个角投射四条光线，您将定义一个被切割成两部分的金字塔，一部分包含形状内部的空间，另一部分定义可能位于形状外部的空间。

这两个卷为您提供了一个决策过程来检查一个四边形是否在边界上。如果另一个四边形的任何点出现在外部体积中，则该四边形不在边界上，可以作为内部四边形丢弃。

编辑：刚刚看到你上面的澄清。在更难的情况下，形状是凹的，那么你需要两件事之一；

1. 可用于选择四边形的形状描述（参数化），或
2. 其他一些属性，例如所有边界四边形都是连续的

进一步编辑：刚刚意识到您所描述的将是点的凹壳。尝试查看此搜索页面中的一些结果。

Answer 4

考虑到所有的四边形都住在一个大的密封盒子里。选择一个四边形。进行光线追踪；将该四边形视为光源，并将所有其他四边形视为反射和模糊，其中对四边形的命中将从该表面向所有方向发送光，但不会在角落周围。

如果在所有节点都有机会被击中后没有光线照射到外部盒子，则将该四边形视为内部盒子。

如果它是凸的，或者内部四边形不与外部四边形共享边，则有更简单的方法。

Answer 5

您可以通过减少必须处理的四边形数量来使您的问题更容易。

你知道一些四边形形成一个封闭的壳。因此，这些四边形在其边缘连接。如果一个四边形的三个相互相邻的边（即，边形成一个闭环）与另一个四边形的边重叠，那么这些四边形可能是壳的一部分（这些相互相邻的边用作二维区域的边界；让我们将该区域称为四边形的“连接面”）。列出这些“shell 候选者”。现在，查看此列表并丢弃任何具有不与另一个候选重叠的边缘的候选（即，该边缘与不在列表中的四边形的边缘重叠）。重复此剔除过程，直到您不再能够删除任何四边形。你剩下的应该是你的壳。创建一个“非壳四边形”

在这个壳周围绘制一个边界框（或球体、椭圆等）。现在，查看您的非壳四边形列表，并丢弃任何位于边界区域之外的四边形。这些绝对不在内部。

取剩下的非壳四边形。这些可能在也可能不在形状的内部。对于这些四边形中的每一个，从每个面的中心绘制垂直于四边形的线，并在边界形状的表面上结束。跟踪每条线并计算线穿过 shell 列表中四边形的“连接面”的次数。如果这个数字是奇数，则该顶点位于形状的内部。如果是偶数，则顶点在外部。您可以根据四边形的顶点是在内部还是外部来确定四边形是在内部还是外部。