博客首页 > Life in Coding > 数据结构和算法 > 判断矩形是否重叠

判断矩形是否重叠

5月 7th, 2013 3,596 留下评论 阅读评论

正常思维下，就会去判断一个矩形的每个点是否在另一个矩形中，然后衍生出4个判断，每个判断都要带上4对大于小于比较，甚是麻烦。

1
2
3
4
5
6

boolean judgeOverlap(Rect A, Rect B){
	for(Point p : all points in A){
		if(p in B) return true;
	}
	return false;
}

上面这段代码其实有一点问题，设A的左上右下点为A1和A2，B的为B1和B2，就是：A与B重叠不等价于judgeOverlap(A1, A2, B1, B2) == true （比如当B真包含于A时就返回false了），而是等价于judgeOverlap(A1, A2, B1, B2) == true || judgeOverlap(B1, B2, A1, A2) == true，这里很容易犯bug。

有一个更容易的方法来解决这个问题，反向思维也很容易，就是排除那些A和B不可能重叠的情况，就4种。

1
2
3
4
5
6
7

boolean judgeOverlap(Rect A, Rect B){
	if(A.right < B.left) return false;
	if(A.left > B.right ) return false;
	if(A.top < B.bottom) return false;
	if(A.bottom > B.top) return false;
	return true;
}

现在项目中还在使用上面版本的代码跑着，觉得第二种方法应该没有问题但没有测试过也没有应用到项目中去实践。

Categories: 数据结构和算法 标签：
  1. 还没有评论呢。