两个凹多边形在给定方向上的交点
inn*_*nti 2 algorithm 3d computational-geometry
输入:两个3d凹面多边形A和B,单位矢量d.没有多边形在时间t = 0 处相交.预期方向d不会经常变化,因此需要一些预处理阶段.
问题:在某个时间t确定两个凹多边形A和B是否可以在方向d上相交.换句话说:如果我们在给定方向d上移动一个多边形,它是否会与另一个多边形相交？
输出: 1 - 交叉存在,0 - 其他.
首先,你应该找到垂直于矢量d的平面.
对于这两个三维多边形,您应该计算此平面上的投影.然后,如果投影重叠,那么3d多边形将在某个时间t相交.
现在你有一个更简单的问题:检查两个2d非凸多边形是否相交.您可以通过简单地遍历每对边缘并检查它们是否相交来实现.