神剑山庄资源网 Design By www.hcban.com
(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.hcban.com
神剑山庄资源网
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com
暂无矩形相交以及求出相交的区域的原理解析的评论...
更新日志
2024年05月17日
2024年05月17日
- SALLY李莎丽《EASTERN YOUTH》[320K/MP3][14.49MB]
- 原音母版1:1直刻《民谣精逊[低速原抓WAV+CUE]
- 原音母版1:1直刻《卓依婷精选集》[低速原抓WAV+CUE]
- 【佛之吧沙发】VA-BuddhaBar-BestOf2byRavin(FLAC)
- [ABC唱片]-《雪莉—蓝》[SACD-008][SACD][WAV+CUE]
- 黎瑞恩.2002-理想的日子精选2CD【环球】【WAV+CUE】
- 【驰放沙发(J)】VA-2024-WinterTime,Vol.12(FLAC)
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 韩红《青藏高原+红+韩红精选集》3CD[WAV分轨][1.7G]
- 高胜美《经典金选》1991-1994 4CD[WAV整轨][1.9G]
- 【迷幻电音】AstralWaves-2023-Singles,RemixesandRaritiesII(FLAC)
- 中唱唱片群星《好歌珍藏-游子情深》2CDWAV
- 张国荣.2011-极品天碟LPCD45II(雨果版)【环球】【WAV+CUE】
- 张学友《醒着做梦》[DFF][1.1G]
- 刘惜君 《如我》[WAV分轨][403M]