输入:两个 3d 凹多边形A和B，单位向量d。在时间 t = 0 时没有多边形相交。预计方向 d 不会经常改变，因此需要一些预处理阶段。
问题:确定两个凹多边形A和B是否可以在方向d上相交，在某些情况下时间t。换句话说:如果我们沿给定方向d移动一个多边形，它会与另一个多边形相交吗？
输出: 1 - 存在交集，0 - 否则。
最佳答案
首先你应该找到垂直于向量d的平面。
对于这两个 3d 多边形，您应该计算该平面上的投影。 然后，如果投影重叠，则 3d 多边形将在某个时间 t 相交。
现在你有更简单的问题:检查两个二维非凸多边形是否相交。 您可以通过简单地迭代每对边并检查它们是否相交来完成此操作。
关于algorithm - 给定方向上两个凹多边形之间的交点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9903753/