c++ - 三角形 - 二维正方形相交测试

Question

如何测试三角形和正方形是否相交？

当我们知道它是正方形而不是矩形时，有什么方法可以优化它吗？此外，正方形是轴对齐的，这样应该可以进一步提升性能？

或者我应该把正方形分成三角形，然后对三角形-三角形相交检查两次？

编辑:澄清一下:我正在尝试检查这两个形状是否以任何方式相互重叠。所以三角形可以在正方形内部，正方形可以在三角形内部，它也应该返回 true。

Answer 1

将矩形(或正方形)与三角形的每条边进行比较，方法是获取三角形的顶点并为每条边构建直线方程，顺序一致(顺时针或逆时针围绕三角形)。

如果矩形在任何边上都完全位于三角形之外，则它不相交。

用矩形的边对着三角形再次测试。

知道矩形是轴对齐的可能会提高性能，因为您可以计算出哪个角最有可能在三角形内，然后只测试那个角，而不是测试所有四个角。

这是否成功取决于实现。有时，盲目检查四个坐标比实际计算最佳坐标更快。

检查三角形与矩形应该更容易，因为当矩形轴对齐时，线方程是针对 x 或 y 的简单测试。

这是分离轴测试的一般形式 - 找到一条线或平面将两个对象分开，从而证明它们不能相交。如果你想要更高的性能，你可以找到两个对象最接近的特征来计算出最合适的线/平面来使用，而不是尝试所有的。