Question

判断两个矩形是否相交

Answer 1

以前写过一篇如何判断线段相交的问题，上网查了一些方法，在这里做一下后一个问题的总结：方法一：假定矩形是用一对点表达的(minx,miny)(maxx, maxy) ，那么两个矩形rect1{(minx1,miny1)(maxx1, maxy1)}, rect2{(minx2,miny2)(maxx2, maxy2)} 相交的结果一定是个矩形，构成这个相交矩形rect{(minx,miny)(maxx, maxy)}的点对坐标是： minx = max(minx1, minx2) miny = max(miny1, miny2) maxx = min(maxx1, maxx2) maxy = min(maxy1, maxy2) 如果两个矩形不相交，那么计算得到的点对坐标必然满足 minx > maxx 或者 miny > maxy bool CPreprocess::crossAlgorithm1(CvRect r1,CvRect r2) { int nMaxLeft = 0; int nMaxTop = 0; int nMinRight = 0; int nMinBottom = 0; //计算两矩形可能的相交矩形的边界 nMaxLeft = r1.x >= r2.x ? r1.x : r2.x; nMaxTop = r1.y >= r2.y ? r1.y : r2.y; nMinRight = (r1.x + r1.width) <= (r2.x + r2.width) ? (r1.x + r1.width) : (r2.x + r2.width); nMinBottom = (r1.y + r1.height) <= (r2.y + r2.height) ? (r1.y + r1.height) : (r2.y + r2.height); // 判断是否相交 if (nMaxLeft > nMinRight || nMaxTop > nMinBottom) { return false; } else { return true; } }方法二：如果两个矩形相交，则必然存在线条交叉，而能交叉的线条只有横线和竖线，两根横线或两根竖线都不可能交叉。所以，这个问题就转化成寻找是否存在交叉的横线与竖线。// bool CPreprocess::crossAlgorithm2(CvRect r1,CvRect r2) { //， //从一个矩形中取出一条横线，与另一矩形中的一条竖线判断是否交叉 return crossLine(r1.x, r1.x + r1.width, r1.y, r2.y, r2.y + r2.height, r2.x) || crossLine(r1.x, r1.x + r1.width, r1.y, r2.y, r2.y + r2.height, r2.x + r2.width) || crossLine(r1.x, r1.x + r1.width, r1.y + r1.height, r2.y, r2.y + r2.height, r2.x) || crossLine(r1.x, r1.x + r1.width, r1.y + r1.height, r2.y, r2.y + r2.height, r2.x r2.width) || crossLine(r2.x, r2.x + r2.width, r2.y, r1.y, r1.y + r1.height, r1.x) || crossLine(r2.x, r2.x + r2.width, r2.y, r1.y, r1.y + r1.height, r1.x + r1.width) || crossLine(r2.x, r2.x + r2.width, r2.y + r2.height, r1.y, r1.y + r1.height, r1.x) || crossLine(r2.x, r2.x + r2.width, r2.y r2.height, r1.y + r1.height, r1.y + r1.height, r1.x r1.width); } //判断直线是否相交 bool CPreprocess::crossLine(int left,int right,int x,int top,int bottom,int y) { return (top < y) && (bottom > y) && (left < x) && (right > x); }