交叉口

Question

输入：两个3D凹多边形甲和乙，单位矢量d。没有多边形在时间相交t = 0.预计方向d不会经常变化，所以需要一些预处理阶段。

问题：确定两个凹多边形甲和乙可以在方向相交d，在一段时间吨。换句话说：如果我们在给定方向移动一个多边形d，它会与另一个多边形相交吗？

输出： 1 - 交叉存在，0 - 其他。

Answer 1

首先你应该找到与矢量垂直的平面d。

对于这两种3D多边形，你应该在这个平面上的投影计算。 然后，如果投影重叠，那么3d多边形将在某个时间t相交。

现在你有更简单的问题：检查两个2d非凸多边形是否相交。 你可以通过迭代每一对边来检查它们是否相交。