判断两矩形是否相交

PS：红色颜色字体为2016/6/8更新。

近期一次笔试中考到了这个题目，答题之后回来再看，发现网上的解答有些十分复杂，让人懒得去看。

隐约记得之前学习计算机图像学的课程时有这个算法。

我把自己的思路记下来，如有遗漏情况没有考虑或者方法有问题，欢迎拍砖：P

问题定义：给定两个边与坐标轴平行的矩形，分别由左上角与右下角两点指定（以此同时，我们可以用右上和左下的两个点来进行推出同样的结果。），即矩形(P1，P2)与(P3，P4)，判断两矩形是否相交。

我的思路：如下图所示，首先求出P1与P3点在X方向较大值与Y方向较大值的交点，在下图中就是P3，用红点(记为M点)表示。

然后求出P2与P4点在X方向较小值与Y方向较小值的交点，在下图中就是P2，用橙色点(记为N点)表示。

如果M点的X坐标和Y坐标值均比N点相应的X坐标和Y坐标值小，亦即M和N可以分别构成一个矩形的左上角点和右上角点，则两矩形相交；其余情况则不相交。

                                   图1

 

 

下图给出第二个示例，表明相交则矩形的某一个顶点位于另一矩形内部作为判断依据是错误的。

                            图2

 

图3给出了相互包含的情况：

                            图3

下图给出了不相交时的示例，两矩形为上下关系，可见红点不在橙色点左上角，不能构成矩形，因此不相交。

                          图4

 

下面的例子同上，给出了两矩形为左右关系的情况。

                 图5

=============================2015/6/8更新================================

由上面的解答，我们应该很明白我们这里所谓的相交，应该定义为面积上的相交。

那么，同理：我们是可以推出来以（p1，p2） 左下，（p3，p4）右上两个矩形的是否相交。

又翻看这个博文是因为，在做leetcode的时候，出现了一个小的问题。就是有关这个问题的。

https://leetcode.com/submissions/detail/29546329/

有兴趣兴趣的童鞋可以test一下自己的程序的。

这个问题主要就是求两个平行x，y轴的矩形的面积和。好像的2014年广州赛区的一个题目的子问题。

这个问题的思路正好其实求解leetcode的上那个题目的大部分思路。

我们需要求出两个点，看着两个点是否还是可以组成同样的矩形（所谓同样的矩形指的是，如果给出的是左上，右下，还是左上，右下）。

Code：

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
		int s1 = (C - A) * (D - B), s2 = (G - E) * (H - F);

		int mix = max(A, E), miy = max(B, F), maxx = min(C, G), maxy = min(D, H);

		if(mix <= maxx && miy <= maxy){
			int s3 = (maxx - mix) * (maxy - miy);
			return s1 + s2 - s3;
		}
		else return s1 + s2;
    }
};