算法来检测两个矩形相交？ [英] 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中的所有点都在相同半平面大肠杆菌。然而，这不是一个分开的边缘，因为顶点的Vb1和B Vb2的还在于半平面。它将仅是一个分离的边缘，如果尚未过的情况下

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

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