如何计算一个凸多面体与另一个多面体的交集？

Question

手头的问题是关于3D空间中2D增长的科学模拟的一部分。2D形状通过向先前增长的形状添加(三角形)分段来增长。

​

​

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

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

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

​

​

在第一步中，我计算了所有相交的边到面。然后，我使用CGAL Delaunay三角剖分软件包在3D中对四面体网格中的结果点集进行网格划分。作为最后一步，我丢弃了所有与先前插入的线段相交的四面体。这在大多数情况下都很有效--但我现在确信，由于根本原因，这个想法是行不通的。

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

Answer 1

所以你想找两个凸壳的交集？

我认为你的方法并不适用于所有情况，而只适用于某些退化的情况，这一点我认为是正确的。例如，如果一个凸包完全在另一个凸包内，则没有面/边的交点。

一种更明显的健壮方法是从一个足够大的凸壳开始(所以基本上表示所有空间)，然后对于两个凸壳中的每个平面，用该平面划分这个外壳，丢弃“外部”上的部分。

结果将是交集--它可能什么都不是。