Warm tip: This article is reproduced from serverfault.com, please click

math-检测两个矩形相交的算法?

(math - Algorithm to detect intersection of two rectangles?)

发布于 2008-09-22 15:15:53

我正在寻找一种算法来检测两个矩形是否相交(一个以任意角度相交,另一个仅以垂直/水平线相交)。

测试一个角是否在另一个ALMOST中是可行的。如果矩形形成十字形,则失败。

避免使用直线的斜率似乎是个好主意,因为直线的斜率需要特殊情况。

Questioner
user20493
Viewed
0
2011-04-11 23:58:04

标准方法是进行分离轴测试(对此进行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