检测两个矩形相交的算法? [英] Algorithm to detect intersection of two rectangles?

问题描述

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

I'm looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines).

测试一个角落是否在另一个角落几乎有效.如果矩形形成十字形，则失败.

Testing if a corner of one is in the other ALMOST works. It fails if the rectangles form a cross-like shape.

避免使用线的斜率似乎是个好主意，这需要垂直线的特殊情况.

It seems like a good idea to avoid using slopes of the lines, which would require special cases for vertical lines.

推荐答案

标准方法是进行分离轴测试(谷歌搜索).

The standard method would be to do the separating axis test (do a google search on that).

简而言之:

• 如果您能找到一条线来分隔两个对象，则两个对象不会相交.例如对象/对象的所有点都位于线的不同侧.

有趣的是，只需检查两个矩形的所有边就足够了.如果矩形不重叠，其中一条边将作为分隔轴.

The fun thing is, that it's sufficient to just check all edges of the two rectangles. If the rectangles don't overlap one of the edges will be the separating axis.

在 2D 中，您可以在不使用斜坡的情况下执行此操作.边被简单地定义为两个顶点之间的差异，例如

In 2D you can do this without using slopes. An edge is simply defined as the difference between two vertices, e.g.

  edge = v(n) - v(n-1)

您可以通过将其旋转 90° 来获得与此垂直的方向.在 2D 中，这很简单:

You can get a perpendicular to this by rotating it by 90°. In 2D this is easy as:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

所以不涉及三角函数或斜率.也不需要将向量归一化为单位长度.

So no trigonometry or slopes involved. Normalizing the vector to unit-length is not required either.

如果你想测试一个点是在线的一侧还是另一侧，你可以使用点积.标志会告诉你你站在哪一边:

If you want to test if a point is on one or another side of the line you can just use the dot-product. the sign will tell you which side you're on:

  // 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 中的所有其他点都在被测试边缘的另一侧 - 见下图).如果您发现没有分隔边，则要么是矩形相交，要么是一个矩形包含在另一个中.

Now test all points of rectangle A against the edges of rectangle B and vice versa. If you find a separating edge the objects don't intersect (providing all other points in B are on the other side of the edge being tested for - see drawing below). If you find no separating edge either the rectangles are intersecting or one rectangle is contained in the other.

该测试适用于任何凸多边形 btw..

The test works with any convex polygons btw..

修正:要识别分离边，仅针对另一个矩形的每条边测试一个矩形的所有点是不够的.候选边 E(如下)将被识别为分离边，因为 A 中的所有点都在 E 的同一半平面中. 然而，它不是分离边，因为 B 的顶点 Vb1 和 Vb2也在那个半平面内.如果不是这样，那只会是一个分离的边缘http://www.iassess.com/collision.png

Amendment: To identify a separating edge, it is not enough to test all points of one rectangle against each edge of the other. The candidate-edge E (below) would as such be identified as a separating edge, as all points in A are in the same half-plane of E. However, it isn't a separating edge because the vertices Vb1 and Vb2 of B are also in that half-plane. It would only have been a separating edge if that had not been the case http://www.iassess.com/collision.png

这篇关于检测两个矩形相交的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！