如何测试三角形和正方形是否相交？
当我们知道它是正方形而不是矩形时，有什么方法可以优化它？另外，正方形是轴对齐的，所以应该对性能有更多的提升吗？
还是我应该把正方形分成三角形，然后检查两次三角形-三角形相交？
编辑：澄清：我正在尝试检查这两个形状是否以任何方式相互重叠。所以三角形可以在正方形里面，正方形可以在三角形里面，它也应该返回true。
问问题
5966 次
3 回答
4
将矩形（或正方形）与三角形的每条边进行比较，方法是获取三角形的顶点并为每条边建立直线方程，并以一致的顺序（围绕三角形顺时针或逆时针）。
如果矩形在任何边上完全位于三角形之外，则它不相交。
用矩形的边缘对着三角形再次测试。
通过知道矩形是轴对齐的，可能会提高性能，因为您可以计算出哪个角最有可能在三角形内，并仅测试那个角，而不是测试所有四个角。
这是否是一场胜利取决于实施。有时盲目地检查四个坐标而不是实际计算最好的坐标会更快。
对照矩形检查三角形应该更容易，因为当矩形轴对齐时，线方程是针对 x 或 y 的简单测试。
这是分离轴测试的一种广义形式 - 找到将两个对象分开的线或平面，从而证明它们不能相交。如果您想要更高的性能，您可以找到两个对象的最近特征来计算出最合适的线/平面来使用，而不是尝试所有这些。
于 2012-12-09T18:32:44.920 回答
4
这是一个经典的碰撞检测问题。如果满足以下任一条件，则形状相交：
- 三角形中至少有一个顶点包含在矩形中。
- 矩形的至少一个顶点包含在三角形内。
- 三角形的任何边与矩形的任何边相交。
前两个条件涵盖了其中一个形状完全包含在另一个形状中的可能性（在这种情况下，边缘不会相交）。
一些优化是可能的。
计算形状的外接圆。如果两个形状的中心点之间的距离大于外接圆的半径之和，则可以排除碰撞。请注意，外接矩形的圆的中心点是其对角线的中点。三角形外接圆的中心点可以通过求任意两条边的垂直平分线的交点来获得。找到完全包含三角形的悲观估计圆的两种方法是：（1）使用最长边作为圆的直径，（2）创建一个边界矩形，角在（mintx，minty），（mintx，maxty）， （最大TX，最大) 和 ( maxtx , minty ) 其中maxtx是任何三角形角的最大 X 坐标，mintx是任何三角形角的最小 X 坐标，依此类推。
形状可以平移和旋转，以便矩形的顶点之一位于原点，矩形的底边沿 X 轴正方向。这使得查找三角形中的顶点是否包含在矩形内变得简单。
平移、旋转和线相交是很好理解的问题，您应该可以在 stackoverflow 、stackoverflow或网络上的其他地方找到合适的代码。
提示：
- 平移很容易——从每个 X 或 Y 坐标中添加或减去相同的值。
从概念上讲，旋转很容易——对于每个点，转换为极坐标，加上或减去旋转角度，然后再转换回笛卡尔坐标。由于转换到/从极坐标在计算上很昂贵，因此您可以使用以下公式进行旋转：
Xrot = X * cos(theta) - Y * sin(theta)
Yrot = X * sin(theta) + Y * cos(theta)您可以通过取矩形的一侧来找到角度theta，并注意
theta = atan2(deltaX, deltaY)
于 2012-12-13T03:52:26.763 回答
2
作为对 Jay Elston 答案的改进，您可以将正方形/四边形拆分为两个三角形，然后使用Möller–Trumbore相交算法来比较包含的顶点。如果你阅读发表的论文，最后有一个算法的 C 实现。
这将让您检查顶点包含。然后使用 Jay 的链接之一作为交叉口。
于 2014-03-11T02:20:08.973 回答