language-agnostic - 剔除内部三角形

Question

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

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

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

编辑:对 shell 形状的进一步限制

形状内部没有孔，它是一个单一的表面。

它包含凸部和凹部。

我有几个已知点位于 shell 内部。

Answer 1

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