这是来自《Java编程入门-综合版》中的练习3.28。该代码测试两个矩形是否缩进，一个矩形是否在另一个矩形内，一个矩形是否在另一个矩形外。如果这些条件都不满足，则两者重叠。

**3.28(几何:两个矩形)编写一个程序，提示用户进入 中心x, y坐标，宽度和高度的两个矩形，并确定 第二个矩形是在第一个矩形的内部还是与第一个矩形重叠，如图所示 如图3.9所示。测试您的程序以覆盖所有情况。 下面是示例运行:

输入r1的中心x坐标，y坐标，宽度和高度:2.5 4 2.5 43 输入r2的中心x坐标，y坐标，宽度和高度:1.5 5 0.5 3 R2在r1里面

输入r1的中心x坐标，y坐标，宽度和高度:1 2 3 5.5 输入r2的中心x坐标，y坐标，宽度和高度:3 4 4.5 5 R2和r1重叠

输入r1的中心x坐标，y坐标，宽度和高度:1 2 3 3 输入r2的中心x坐标，y坐标，宽度和高度:40 45 3 2 R2不与r1重叠

import java.util.Scanner;

public class ProgrammingEx3_28 {
public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    System.out
            .print("Enter r1's center x-, y-coordinates, width, and height:");
    double x1 = input.nextDouble();
    double y1 = input.nextDouble();
    double w1 = input.nextDouble();
    double h1 = input.nextDouble();
    w1 = w1 / 2;
    h1 = h1 / 2;
    System.out
            .print("Enter r2's center x-, y-coordinates, width, and height:");
    double x2 = input.nextDouble();
    double y2 = input.nextDouble();
    double w2 = input.nextDouble();
    double h2 = input.nextDouble();
    w2 = w2 / 2;
    h2 = h2 / 2;

    // Calculating range of r1 and r2
    double x1max = x1 + w1;
    double y1max = y1 + h1;
    double x1min = x1 - w1;
    double y1min = y1 - h1;
    double x2max = x2 + w2;
    double y2max = y2 + h2;
    double x2min = x2 - w2;
    double y2min = y2 - h2;

    if (x1max == x2max && x1min == x2min && y1max == y2max
            && y1min == y2min) {
        // Check if the two are identicle
        System.out.print("r1 and r2 are indentical");

    } else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
            && y1min >= y2min) {
        // Check if r1 is in r2
        System.out.print("r1 is inside r2");
    } else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
            && y2min >= y1min) {
        // Check if r2 is in r1
        System.out.print("r2 is inside r1");
    } else if (x1max < x2min || x1min > x2max || y1max < y2min
            || y2min > y1max) {
        // Check if the two overlap
        System.out.print("r2 does not overlaps r1");
    } else {
        System.out.print("r2 overlaps r1");
    }

}
}

这是一个用c++快速检查两个矩形是否重叠的方法:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

它的工作原理是计算相交矩形的左右边界，然后比较它们:如果右边界等于或小于左边界，这意味着交点是空的，因此矩形不重叠;否则，它将再次尝试顶部和底部边框。

What is the advantage of this method over the conventional alternative of 4 comparisons? It's about how modern processors are designed. They have something called branch prediction, which works well when the result of a comparison is always the same, but have a huge performance penalty otherwise. However, in the absence of branch instructions, the CPU performs quite well. By calculating the borders of the intersection instead of having two separate checks for each axis, we're saving two branches, one per pair.

如果第一个比较有很高的错误几率，那么四个比较方法可能比这个方法更好。但这是非常罕见的，因为这意味着第二个矩形通常在第一个矩形的左边，而不是在右边或重叠;大多数情况下，您需要检查第一个矩形的两侧，这通常会使分支预测的优势失效。

根据矩形的预期分布，这种方法还可以进一步改进:

If you expect the checked rectangles to be predominantly to the left or right of each other, then the method above works best. This is probably the case, for example, when you're using the rectangle intersection to check collisions for a game, where the game objects are predominantly distributed horizontally (e.g. a SuperMarioBros-like game). If you expect the checked rectangles to be predominantly to the top or bottom of each other, e.g. in an Icy Tower type of game, then checking top/bottom first and left/right last will probably be faster:

return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
    && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

然而，如果相交的概率接近于不相交的概率，那么最好有一个完全无分支的替代方案:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
     & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

(注意&&变成了一个&)

最简单的方法是

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

首先要记住在计算机中坐标系统是颠倒的。x轴与数学中的相同，但y轴向下增大，向上减小。 如果矩形是从中心画的。 如果x1坐标大于x2加上它的一半宽。然后这意味着他们会互相接触。用同样的方法向下+一半高。它会碰撞的。

更容易检查一个矩形是否完全在另一个矩形之外，如果它是其中之一

在左边……

(r1.x + r1.width < r2.x)

或者在右边…

(r1.x > r2.x + r2.width)

或者在上面…

(r1.y + r1.height < r2.y)

或者在底部…

(r1.y > r2.y + r2.height)

对于第二个矩形，它不可能与它碰撞。因此，要有一个返回布尔值的函数，表示矩形是否碰撞，我们只需通过逻辑or组合这些条件，并对结果求反:

function checkOverlap(r1, r2) : Boolean
{ 
    return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}

如果只在触摸时得到阳性结果，我们可以通过“<=”和“>=”来更改“<”和“>”。

struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.y1 > r1.y2;

    return !noOverlap;
}

问你自己一个相反的问题:我如何确定两个矩形是否完全不相交?显然，矩形a完全在矩形B的左边不相交。如果A完全在右边。同样，如果A完全高于B或完全低于B，在任何其他情况下，A和B相交。

以下内容可能有bug，但我对算法相当有信心:

struct Rectangle { int x; int y; int width; int height; };

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_intersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool intersect(Rectangle const & a, Rectangle const & b) {
  return !not_intersect(a, b);
}