判断矩形相交以及求出相交的区域

kyanag 发布于2019-08-21 14:14 / 1835人阅读

摘要：设计一个算法，确定两个矩形是否相交即有重叠区域如果两个矩形相交，设计一个算法，求出相交的区域矩形对于这个问题，一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内。这样，可以依据的值来判断矩形相交。

问题：给定两个矩形A和B，矩形A的左上角坐标为（Xa1,Ya1），右下角坐标为（Xa2,Ya2），矩形B的左上角坐标为（Xb1,Yb1），右下角坐标为（Xb2,Yb2）。
（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
附上js实现

intersect = function(rect1, rect2) {
    var half1Width = rect1.width / 2,
        half1Height = rect1.height / 2,
        half2Width = rect2.width / 2,
        half2Height = rect2.height / 2,
        cen1 = {
            x: rect1.x + half1Width,
            y: rect1.y + half1Height
        },
        cen2 = {
            x: rect2.x + half2Width,
            y: rect2.y + half2Height
        };

    return Math.abs(cen2.x - cen1.x) <= half1Width + half2Width &&
        Math.abs(cen2.y - cen1.y) <= half1Height + half2Height;
};

(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)

宣传下我的区块管理框架Magix：https://github.com/thx/magix

欢迎试用Magix、star与fork

GPU云服务器云服务器 php 数组相交判断可视区域 js判断所选区域免费的域名以及服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/87821.html

你不知道的前端算法之文字避让

摘要：避让算法采用的是四分位模型算法，接下来手把手教你写避让算法，老司机带你装逼带你飞。创建四分位模型所谓四分位模型，每一个标记点都有上下左右四个放文字的位子，如果左边放不下，那就放右边试试，还不行就放到下面试试，以此类推，原理就这么简单，哈哈。本文作者：TalkingData 可视化工程师李凤禄编辑：Aresn inMap 是一款基于 canvas 的大数据可视化库，专注于大数据方向点线...

yedf 2019-08-21 18:44 评论0 收藏0
H5中优化碰撞检测

摘要：微信端口的小游戏相信大家已经做了很多类似于碰撞检测这种也是数不胜数因为障碍物和主角都是图片也就意味着碰撞检测实际上是两个矩形直接是否有交叉的判断包括这样的框架也是这样子做的当然这种方法也无可厚非然而唯一的问题是如果素材障碍物和主角并不能铺满微信端口的小游戏相信大家已经做了很多,类似于碰撞检测这种也是数不胜数.因为障碍物和主角都是图片,也就意味着碰撞检测实际上是两个矩形直接是否有交叉...

苏丹 2019-08-22 11:05 评论0 收藏0
TalkingData 开源地理信息可视化框架 inMap

摘要：本文作者可视化工程师李凤禄是可视化团队开源的一款基于的大数据可视化库，专注于大数据方向点线面的可视化效果展示。目前支持散点围栏热力网格聚合等方式致力于让大数据可视化变得简单易用。后续会输出创造更好的可视化图形和算法，并后续推出版本。 showImg(https://segmentfault.com/img/bV0yHB?w=1600&h=900); 本文作者：TalkingData 可...

xeblog 2019-08-22 11:21 评论0 收藏0