题目
给出两个矩形的一个顶点和宽度高度，判断两个矩形是否相交并计算出相交的区域。
解法
下面给了出几种算法的C代码并对其进行了测试，算法依次更简单快速：
#include <stdio.h>
int IsOverlap1(double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh)
{
double ax2, ay2, bx2, by2;
#define _PARAM_CHECK_(a, b, c) \
do { if (b < 0.0) { a += b; b = 0 - b; } c = a + b; } while(0)
_PARAM_CHECK_(ax1, aw, ax2);
_PARAM_CHECK_(ay1, ah, ay2);
_PARAM_CHECK_(bx1, bw, bx2);
_PARAM_CHECK_(by1, bh, by2);
#undef _PARAM_CHECK_
#define _IS_BETWEEN_(a, b, c) (a <= b && b <= c)
/*
1.B有顶点在A中
-------A
| |
| ------B
| | | |
----|-- |
| |
------
*/
if (_IS_BETWEEN_(ax1, bx1, ax2) && _IS_BETWEEN_(ay1, by1, ay2)) return 1;
if (_IS_BETWEEN_(ax1, bx1, ax2) && _IS_BETWEEN_(ay1, by2, ay2)) return 1;
if (_IS_BETWEEN_(ax1, bx2, ax2) && _IS_BETWEEN_(ay1, by1, ay2)) return 1;
if (_IS_BETWEEN_(ax1, bx2, ax2) && _IS_BETWEEN_(ay1, by2, ay2)) return 1;
/*
2.A有2或4个顶点在B中
-------B
| --- |
--|-|--
---A
-------
| --- |
| |A| |
| --- |
-------B
*/
if (_IS_BETWEEN_(bx1, ax1, bx2) && _IS_BETWEEN_(by1, ay1, by2)) return 1;
if (_IS_BETWEEN_(bx1, ax2, bx2) && _IS_BETWEEN_(by1, ay2, by2)) return 1;
/*
3.A与B十字相交且A横B竖
---B
| |
---|-|---A
| | | |
---|-|---
| |
---
*/
if (_IS_BETWEEN_(ax1, bx1, ax2) && _IS_BETWEEN_(ax1, bx2, ax2)
&& _IS_BETWEEN_(by1, ay1, by2) && _IS_BETWEEN_(by1, ay2, by2))
return 1;
/*
3.A与B十字相交且A竖B横
---A
| |
---|-|---B
| | | |
---|-|---
| |
---
*/
if (_IS_BETWEEN_(bx1, ax1, bx2) && _IS_BETWEEN_(bx1, ax2, bx2)
&& _IS_BETWEEN_(ay1, by1, ay2) && _IS_BETWEEN_(ay1, by2, ay2))
return 1;
return 0;
}
int IsOverlap2(double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh)
{
/*
如果A与B中心在X和Y轴上的距离小于他们边长和的一半就相交
*/
double ax2, ay2, bx2, by2;
double dx, dy;
#define _PARAM_CHECK_(a, b, c) \
do { if (b < 0.0) { a += b; b = 0 - b; } c = a + b; } while(0)
_PARAM_CHECK_(ax1, aw, ax2);
_PARAM_CHECK_(ay1, ah, ay2);
_PARAM_CHECK_(bx1, bw, bx2);
_PARAM_CHECK_(by1, bh, by2);
#undef _PARAM_CHECK_
dx = ax1 + ax2 - (bx1 + bx2); /* A与B中心在X轴上距离的2倍 */
dy = ay1 + ay2 - (by1 + by2); /* A与B中心在Y轴上距离的2倍 */
if (dx < 0.0) dx = 0 - dx;
if (dy < 0.0) dy = 0 - dy;
if (dx <= aw + bw && dy <= ah + bh)
return 1;
return 0;
}
int IsOverlap3(double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh)
{
/*
找出不相交的情况，取反
*/
double ax2, ay2, bx2, by2;
#define _PARAM_CHECK_(a, b, c) \
do { if (b < 0.0) { a += b; b = 0 - b; } c = a + b; } while(0)
_PARAM_CHECK_(ax1, aw, ax2);
_PARAM_CHECK_(ay1, ah, ay2);
_PARAM_CHECK_(bx1, bw, bx2);
_PARAM_CHECK_(by1, bh, by2);
#undef _PARAM_CHECK_
/* A在B左边 */
if (ax2 < bx1) return 0;
/* A在B右边 */
if (bx2 < ax1) return 0;
/* A在B上边 */
if (by2 < ay1) return 0;
/* A在B下边 */
if (ay2 < by1) return 0;
return 1;
}
int IsOverlap4(double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh)
{
double ax2, ay2, bx2, by2;
#define _PARAM_CHECK_(a, b, c) \
do { if (b < 0.0) { a += b; b = 0 - b; } c = a + b; } while(0)
_PARAM_CHECK_(ax1, aw, ax2);
_PARAM_CHECK_(ay1, ah, ay2);
_PARAM_CHECK_(bx1, bw, bx2);
_PARAM_CHECK_(by1, bh, by2);
#undef _PARAM_CHECK_
return (ax1 <= bx2 && bx1 <= ax2 && ay1 <= by2 && by1 <= ay2) ? 1 : 0;
}
int GetOverlap(double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh,
double* cx1, double* cy1, double* cw, double* ch)
{
double ax2, ay2, bx2, by2;
double x1, y1, x2, y2;
#define _PARAM_CHECK_(a, b, c) \
do { if (b < 0.0) { a += b; b = 0 - b; } c = a + b; } while(0)
_PARAM_CHECK_(ax1, aw, ax2);
_PARAM_CHECK_(ay1, ah, ay2);
_PARAM_CHECK_(bx1, bw, bx2);
_PARAM_CHECK_(by1, bh, by2);
#undef _PARAM_CHECK_
if (ax1 <= bx2 && bx1 <= ax2 && ay1 <= by2 && by1 <= ay2)
{
x1 = ax1 > bx1 ? ax1 : bx1;
y1 = ay1 > by1 ? ay1 : by1;
x2 = ax2 < bx2 ? ax2 : bx2;
y2 = ay2 < by2 ? ay2 : by2;
if (NULL != cx1) *cx1 = x1;
if (NULL != cy1) *cy1 = y1;
if (NULL != cw) *cw = x2 - x1;
if (NULL != ch) *ch = y2 - y1;
return 1;
}
return 0;
}
void Test(const char* s, double ax1, double ay1, double aw, double ah,
double bx1, double by1, double bw, double bh)
{
double cx1 = 0.0;
double cy1 = 0.0;
double cw = 0.0;
double ch = 0.0;
if (NULL == s) return;
printf("-----------------------------------------------\n");
printf("Test:%s\n", s);
printf("A:%lf, %lf, %lf, %lf\n", ax1, ay1, aw, ah);
printf("B:%lf, %lf, %lf, %lf\n", bx1, by1, bw, bh);
printf("Result1:%d\n", IsOverlap1(ax1, ay1, aw, ah, bx1, by1, bw, bh));
printf("Result2:%d\n", IsOverlap2(ax1, ay1, aw, ah, bx1, by1, bw, bh));
printf("Result3:%d\n", IsOverlap3(ax1, ay1, aw, ah, bx1, by1, bw, bh));
printf("Result4:%d\n", IsOverlap4(ax1, ay1, aw, ah, bx1, by1, bw, bh));
GetOverlap(ax1, ay1, aw, ah, bx1, by1, bw, bh, &cx1, &cy1, &cw, &ch);
printf("Overlap:%lf, %lf, %lf, %lf\n", cx1, cy1, cw, ch);
}
int main(int argc, char** argv)
{
Test("The left-up of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, -2.0);
Test("The left-down of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 2.0, 2.0);
Test("The right-up of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, -2.0, -2.0);
Test("The right-down of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, -2.0, 2.0);
Test("The left-up of A in B", 2.0, 2.0, 2.0, -2.0, 1.0, 1.0, 2.0, 2.0);
Test("The left-down of A in B", 2.0, 2.0, 2.0, 2.0, 1.0, 1.0, 2.0, 2.0);
Test("The right-up of A in B", 2.0, 2.0, -2.0, -2.0, 1.0, 1.0, 2.0, 2.0);
Test("The right-down of A in B", 2.0, 2.0, -2.0, 2.0, 1.0, 1.0, 2.0, 2.0);
Test("The up of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 0.5, -4.0);
Test("The down of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 0.5, 4.0);
Test("The left of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, -4.0, 0.5);
Test("The right of B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 4.0, 0.5);
Test("The up of A in B", 2.0, 2.0, 0.5, -4.0, 1.0, 1.0, 2.0, 2.0);
Test("The down of A in B", 2.0, 2.0, 0.5, 4.0, 1.0, 1.0, 2.0, 2.0);
Test("The left of A in B", 2.0, 2.0, -4.0, 0.5, 1.0, 1.0, 2.0, 2.0);
Test("The right of A in B", 2.0, 2.0, 4.0, 0.5, 1.0, 1.0, 2.0, 2.0);
Test("The B in A", 1.0, 1.0, 2.0, 2.0, 2.0, 2.0, 0.5, 0.5);
Test("The A in B", 2.0, 2.0, 0.5, 0.5, 1.0, 1.0, 2.0, 2.0);
Test("horizontal A cross vertical B", 0.0, 1.0, 2.0, 1.0, 1.0, 0.0, 1.0, 2.0);
Test("horizontal B cross vertical A", 1.0, 0.0, 1.0, 2.0, 0.0, 1.0, 2.0, 1.0);
return 0;
}代码测试结果
-----------------------------------------------
Test:The left-up of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 2.000000, -2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 1.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The left-down of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The right-up of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, -2.000000, -2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 1.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The right-down of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, -2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 2.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The left-up of A in B
A:2.000000, 2.000000, 2.000000, -2.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 1.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The left-down of A in B
A:2.000000, 2.000000, 2.000000, 2.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The right-up of A in B
A:2.000000, 2.000000, -2.000000, -2.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 1.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The right-down of A in B
A:2.000000, 2.000000, -2.000000, 2.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 2.000000, 1.000000, 1.000000
-----------------------------------------------
Test:The up of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 0.500000, -4.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 1.000000, 0.500000, 1.000000
-----------------------------------------------
Test:The down of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 0.500000, 4.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 0.500000, 1.000000
-----------------------------------------------
Test:The left of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, -4.000000, 0.500000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 2.000000, 1.000000, 0.500000
-----------------------------------------------
Test:The right of B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 4.000000, 0.500000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 1.000000, 0.500000
-----------------------------------------------
Test:The up of A in B
A:2.000000, 2.000000, 0.500000, -4.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 1.000000, 0.500000, 1.000000
-----------------------------------------------
Test:The down of A in B
A:2.000000, 2.000000, 0.500000, 4.000000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 0.500000, 1.000000
-----------------------------------------------
Test:The left of A in B
A:2.000000, 2.000000, -4.000000, 0.500000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 2.000000, 1.000000, 0.500000
-----------------------------------------------
Test:The right of A in B
A:2.000000, 2.000000, 4.000000, 0.500000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 1.000000, 0.500000
-----------------------------------------------
Test:The B in A
A:1.000000, 1.000000, 2.000000, 2.000000
B:2.000000, 2.000000, 0.500000, 0.500000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 0.500000, 0.500000
-----------------------------------------------
Test:The A in B
A:2.000000, 2.000000, 0.500000, 0.500000
B:1.000000, 1.000000, 2.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:2.000000, 2.000000, 0.500000, 0.500000
-----------------------------------------------
Test:horizontal A cross vertical B
A:0.000000, 1.000000, 2.000000, 1.000000
B:1.000000, 0.000000, 1.000000, 2.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 1.000000, 1.000000, 1.000000
-----------------------------------------------
Test:horizontal B cross vertical A
A:1.000000, 0.000000, 1.000000, 2.000000
B:0.000000, 1.000000, 2.000000, 1.000000
Result1:1
Result2:1
Result3:1
Result4:1
Overlap:1.000000, 1.000000, 1.000000, 1.000000
