2D下的三角形-矩形相交测试

Question

7

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

如果我们知道它是正方形而不是矩形，有什么优化的方法吗？此外，正方形是轴对齐的，这应该可以提高性能？

还是应该将正方形分成三角形，并两次进行三角形相交检查？

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

- Rookie

您是想查看是否有任何边相交，还是想查找区域是否相交。对于后者，您还需要考虑一个形状完全包含在另一个形状中的情况。 - Jay Elston

@JayElston，我想知道这两个形状是否以任何方式重叠在一起。 - Rookie

@Rookie :: 如果你找到了答案，能否更新一下回答...你能否评论一下计算时间和实现的高级流程...谢谢 - santiago_apr1

3个回答

4

这是一个经典的碰撞检测问题。如果以下任一条件成立，则形状相交：

前两个条件涵盖了一种形状完全包含在另一种形状内的情况（此时边将不相交）。

一些优化是可能的。

计算形状的外接圆。如果两个形状中心点之间的距离大于外接圆半径之和，则可以排除碰撞。请注意，外接矩形的中心点是其对角线的中点。通过找到任意两条边的垂直平分线的交点，可以得到三角形的外接圆的中心点。两种找到一个悲观估计圆形的方法，以完全包含一个三角形：（1）使用最长的边作为圆的直径，（2）创建一个边界矩形，其角落位于(mintx, minty), (mintx, maxty), (maxtx, maxty)和(maxtx, minty)，其中maxtx是任何三角形角落的最大X坐标，mintx是任何三角形角落的最小X坐标等。
可以将形状平移和旋转，使矩形的一个顶点位于原点，并且矩形的底边沿着正X轴。这使得查找三角形中是否包含一个顶点在矩形内变得简单。

平移、旋转和线段相交是非常了解的问题，您应该没有问题找到适合的代码在stackoverflow上，或者其他地方在网络上。

提示：

平移很容易 - 从每个X或Y坐标中添加或减去相同的值。
概念上，旋转很容易 - 对于每个点，将其转换为极坐标，加或减旋转角度，然后再转换回笛卡尔坐标。由于转换为/从极坐标的计算成本很高，因此可以使用以下公式进行旋转：

Xrot = X * cos(theta) - Y * sin(theta)
Yrot = X * sin(theta) + Y * cos(theta)
您可以通过取矩形的一条边来找到角度theta，并注意到

theta = atan2(deltaX, deltaY)

- Jay Elston

添加了旋转公式，感谢monster860的建议。 - Jay Elston

2

作为对Jay Elston回答的进一步改进，您可以将正方形/四边形分成两个三角形，然后使用Möller–Trumbore交点算法来比较顶点的包含情况。如果您阅读了发布的论文，则在结尾处有该算法的C语言实现。

这将让您检查顶点是否被包含。然后使用Jay提供的一个链接来处理交点。

- yarbelk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JasonD · Accepted Answer

将矩形（或正方形）与三角形的每条边进行比较，通过采用顶点并为每条边建立一个方程式，按照一致的顺序（顺时针或逆时针）绕着三角形。

如果矩形在任何一条边上完全在三角形外部，则它们不相交。

再次使用矩形的边缘测试三角形。

如果您知道矩形轴对齐，则可以提高性能，因为您可以计算出哪个角落最有可能在三角形内，并仅测试该角落，而不是测试所有四个角落。

这是否胜利取决于具体实现。有时候盲目地检查四个坐标比实际计算最佳坐标更快。

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

这是分离轴测试的广义形式 - 查找将两个对象分开的线或平面，从而证明它们不会相交。如果您想获得更好的性能，可以找到两个对象的最近特征，以找出最合适的线/平面，而不必尝试所有这些。