algorithm - 3D多边形与立方体的交集算法

Question

我需要一个快速算法来检查 3D 多边形（共面的 3D 坐标列表，给定逆时针或顺时针顺序的点列表，多边形可以是凸的或凹的，换句话说，它必须是不相交的简单多边形）和一个立方体（给定左下角和右上角的坐标，立方体边缘与 X/Y/Z 轴对齐）相交。

有什么快速的方法可以做到这一点吗？谢谢.. 我用谷歌搜索了几页，但还没有找到完全相同的东西。

非常感谢..

编辑 对不起，当我说“盒子”时，我的意思是“立方体”。一个立方体被定义为两个角点。左下角和右上角（或另一对，没关系）。

Answer 1

1. 检查多边形和框的每一侧之间的多边形-多边形相交。
2. 检查是否有任何多边形的点在框内。

Answer 2

以下是一些应该有效的测试

1. 检查框内是否有 1 个或多个多边形点，但不是全部。
2. 检查多边形的任何边缘是否与框的边缘相交。
3. 检查多边形的任何面是否与盒子的面相交。

如果上述任何一个成立，那么它们相交。列出的所有区域可能都值得麻烦测试它们，因为提取面部并计算它们是否相交可能无法在线性时间内完成。