computational-geometry - 如何计算凸多面体和另一个多面体之间的交集？

Question

手头的问题是与 3D 空间内的 2D 增长有关的科学模拟的一部分。2D 形状通过将（三角形）段添加到先前增长的形状来增长。

请注意，3D 中的实际段具有厚度，因此，我的代码实际上适用于三角棱镜。

在某一时刻，这些 2D 形状（具有任何相对方向和位置）发生碰撞。

如果其中一个新的三角棱柱与先前插入的线段相交，我只想插入与先前插入的线段不相交的线段的“部分”。如下所示，标记为 T1 和 T2 的段。

在第一步中，我计算了所有相交边到面。然后，我使用 3D 中的 CGAL Delaunay Triangulation 包对四面体网格中的结果点集进行网格划分。最后一步，我扔掉所有与之前插入的线段相交的四面体。在大多数情况下，这很有效——但我现在确信这个想法由于根本原因而行不通。

有什么更可靠的计算方法？

Answer 1

所以你正在寻找 2 个凸包的交集？

我认为您的正确方法并非在所有情况下都有效，而仅在某些退化的情况下有效。例如，如果一个凸包完全在另一个凸包内，则没有面/边相交。

一个更明显更强大的方法是从一个足够大的凸包开始，以包围你的两个外壳（所以基本上代表所有空间），然后对于你的两个凸包中的每个平面，用那个平面划分这个外壳，扔掉部分在外面”。

结果将是交叉点 - 这可能什么都没有。