判断矩形是否重叠

五月 7th, 2013 1,118 留下评论 阅读评论

正常思维下,就会去判断一个矩形的每个点是否在另一个矩形中,然后衍生出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. 还没有评论呢。
icon_wink.gif icon_neutral.gif icon_mad.gif icon_twisted.gif icon_smile.gif icon_eek.gif icon_sad.gif icon_rolleyes.gif icon_razz.gif icon_redface.gif icon_surprised.gif icon_mrgreen.gif icon_lol.gif icon_idea.gif icon_biggrin.gif icon_evil.gif icon_cry.gif icon_cool.gif icon_arrow.gif icon_confused.gif icon_question.gif icon_exclaim.gif