我正在寻找一种算法来检测两个矩形是否相交(一个以任意角度相交,另一个仅以垂直/水平线相交)。
测试一个角是否在另一个ALMOST中是可行的。如果矩形形成十字形,则失败。
避免使用直线的斜率似乎是个好主意,因为直线的斜率需要特殊情况。
标准方法是进行分离轴测试(对此进行Google搜索)。
简而言之:
有趣的是,仅检查两个矩形的所有边缘就足够了。如果矩形不重叠,则边缘之一将成为分隔轴。
在2D中,你可以不使用坡度来执行此操作。边简单定义为两个顶点之间的差,例如
edge = v(n) - v(n-1)
你可以通过将其旋转90°来获得垂直于此的角度。在2D中,这很容易,因为:
rotated.x = -unrotated.y
rotated.y = unrotated.x
因此,不涉及三角函数或斜率。也不需要将向量归一化为单位长度。
如果要测试点是否在直线的一侧或另一侧,则可以使用点积。标牌会告诉你你在哪一边:
// rotated: your rotated edge
// v(n-1) any point from the edge.
// testpoint: the point you want to find out which side it's on.
side = sign (rotated.x * (testpoint.x - v(n-1).x) +
rotated.y * (testpoint.y - v(n-1).y);
现在,针对矩形B的边缘测试矩形A的所有点,反之亦然。如果找到分离的边缘,则对象不相交(假设B中的所有其他点都在要测试的边缘的另一侧-请参见下图)。如果找不到分隔边,则两个矩形相交,或者另一个矩形中包含一个矩形。
该测试适用于所有凸多边形btw ..
修正:要确定分隔边缘,仅将一个矩形的所有点与另一个矩形的每个边缘进行对比测试是不够的。由于A中的所有点都在E的同一半平面中,因此候选边E(如下)将被标识为分离边。但是,它不是分离边,因为B的顶点Vb1和Vb2也在那个半平面内。如果不是这种情况,那只会是一个分离的边缘 。http://www.iassess.com/collision.png
此算法不适用于所有情况。可以将第二个矩形旋转到第一个矩形45度并沿对角线偏移,以使其满足上述相交测试但不相交。
Skizz,检查所有八个边缘。如果对象不相交,则八个边缘之一将分隔它们。您为什么不张贴展示您的案件的图像?我可以告诉你轴。
我的错,确实可以解决这种情况。
该图像现在已消失(2012年11月)
我在可视化该图像时遇到了很多麻烦,因此我重新创建了我认为参考图像的外观。imgur.com/bNwrzsv