(1)设计一个算法,确定两个矩形是否相交(即有重叠区域)
(2)如果两个矩形相交,设计一个算法,求出相交的区域矩形
(1) 对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内。这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一 下。
如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形 内部。所以那种思路存在一个错误,对于这种情况的相交则检查不出。
仔细观察上图,想到另一种思路,那就是判断两个矩形的中心坐标的水平和垂直距离,只要这两个值满足某种条件就可以相交。
矩形A的宽 Wa = Xa2-Xa1 高 Ha = Ya2-Ya1
矩形B的宽 Wb = Xb2-Xb1 高 Hb = Yb2-Yb1
矩形A的中心坐标 (Xa3,Ya3) = ( (Xa2+Xa1)/2 ,(Ya2+Ya1)/2 )
矩形B的中心坐标 (Xb3,Yb3) = ( (Xb2+Xb1)/2 ,(Yb2+Yb1)/2 )
所以只要同时满足下面两个式子,就可以说明两个矩形相交。1) | Xb3-Xa3 | <= Wa/2 + Wb/2
2) | Yb3-Ya3 | <= Ha/2 + Hb/2
即:
| Xb2+Xb1-Xa2-Xa1 | <= Xa2-Xa1 + Xb2-Xb1
| Yb2+Yb1-Ya2-Ya1 | <=Y a2-Ya1 + Yb2-Yb1
(2) 对于这个问题,假设两个矩形相交,设相交之后的矩形为C,且矩形C的左上角坐标为(Xc1,Yc1),右下角坐标为(Xc2,Yc2),经过观察上图,很 显然可以得到:
Xc1 = max(Xa1,Xb1)
Yc1 = max(Ya1,Yb1)
Xc2 = min(Xa2,Xb2)
Yc2 = min(Ya2,Yb2)
这样就求出了矩形的相交区域。
另外,注意到在不假设矩形相交的前提下,定义(Xc1,Yc1),(Xc2,Yc2),且Xc1,Yc1,Xc2,Yc2的值由上面四个式子得出。这样, 可以依据Xc1,Yc1,Xc2,Yc2的值来判断矩形相交。
Xc1,Yc1,Xc2,Yc2只要同时满足下面两个式子,就可以说明两个矩形相交。
3) Xc1 <= Xc2
4) Yc1 <= Yc2
即:
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)
(2)如果两个矩形相交,设计一个算法,求出相交的区域矩形
(1) 对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内。这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一 下。
如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形 内部。所以那种思路存在一个错误,对于这种情况的相交则检查不出。
仔细观察上图,想到另一种思路,那就是判断两个矩形的中心坐标的水平和垂直距离,只要这两个值满足某种条件就可以相交。
矩形A的宽 Wa = Xa2-Xa1 高 Ha = Ya2-Ya1
矩形B的宽 Wb = Xb2-Xb1 高 Hb = Yb2-Yb1
矩形A的中心坐标 (Xa3,Ya3) = ( (Xa2+Xa1)/2 ,(Ya2+Ya1)/2 )
矩形B的中心坐标 (Xb3,Yb3) = ( (Xb2+Xb1)/2 ,(Yb2+Yb1)/2 )
所以只要同时满足下面两个式子,就可以说明两个矩形相交。1) | Xb3-Xa3 | <= Wa/2 + Wb/2
2) | Yb3-Ya3 | <= Ha/2 + Hb/2
即:
| Xb2+Xb1-Xa2-Xa1 | <= Xa2-Xa1 + Xb2-Xb1
| Yb2+Yb1-Ya2-Ya1 | <=Y a2-Ya1 + Yb2-Yb1
(2) 对于这个问题,假设两个矩形相交,设相交之后的矩形为C,且矩形C的左上角坐标为(Xc1,Yc1),右下角坐标为(Xc2,Yc2),经过观察上图,很 显然可以得到:
Xc1 = max(Xa1,Xb1)
Yc1 = max(Ya1,Yb1)
Xc2 = min(Xa2,Xb2)
Yc2 = min(Ya2,Yb2)
这样就求出了矩形的相交区域。
另外,注意到在不假设矩形相交的前提下,定义(Xc1,Yc1),(Xc2,Yc2),且Xc1,Yc1,Xc2,Yc2的值由上面四个式子得出。这样, 可以依据Xc1,Yc1,Xc2,Yc2的值来判断矩形相交。
Xc1,Yc1,Xc2,Yc2只要同时满足下面两个式子,就可以说明两个矩形相交。
3) Xc1 <= Xc2
4) Yc1 <= Yc2
即:
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)
华山资源网 Design By www.eoogi.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
华山资源网 Design By www.eoogi.com
暂无评论...
更新日志
2024年05月20日
2024年05月20日
- 张琍敏1978-雪中莲[台湾复刻版][WAV+CUE]
- 叶蕴仪1993-睡美人[日本版][WAV+CUE]
- 夜晚助兴音乐-群星《新时代床头音乐-性能量》2CD[WAV]
- 24K德国HD金碟《历届奥斯卡获奖金曲》3CD[WAV整轨]
- 邰正宵《重燃爱恋 贰 Walk On》[FLAC/分轨][431.72MB]
- 苏文劭《雨停出来走走》[320K/MP3][81.11MB]
- 苏文劭《雨停出来走走》[FLAC/分轨][210.76MB]
- 群星《2024好听新歌04》十倍音质WAV分轨
- 陈宁《弹指之间HQ》头版限量[低速原抓WAV+CUE]
- 陈宁《故人还》HQCDII限量签名版[低速原抓WAV+CUE]
- 苏文劭《春曲(Lessons)》[320K/MP3][39.8MB]
- 苏文劭《春曲(Lessons)》[FLAC/分轨][97.78MB]
- 群星《2006香港高级视听展原音精选 SACD》[ISO][2G]
- 张琍敏1977-枫林小雨[台湾复刻版][WAV+CUE]
- 林一峰2014-COOKINGMUSIC[香港首版][WAV+CUE]