矩形相交以及求出相交的区域的原理解析
发布时间：2023-08-17 18:39:09
（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)
0
投稿猜你喜欢
CSRF全拼为Cross Site Request Forgery，译为跨站请求伪造。CSRF指攻击者盗用了你的身份，以你的名义发送恶意请求- 本文实例讲述了PHP实现基于3DES算法加密解密字符串。分享给大家供大家参考，具体如下：3DES（或称为Triple DES）是三重数据加密
- 本文实例讲述了Go语言通过smtp发送邮件的方法。分享给大家供大家参考。具体实现方法如下：package mainimport (
- 活在当下的程序员应该都听过“面向对象编程”一词，也经常有人问能不能用一句话解释下什么是“面向对象编程”，我们先来看看比较正式的说法。把一组数
- 很久没写blog，太忙了。没什么时间写复杂的东西，重新把颜色渐变效果写一遍。关于颜色的效果一般就两个，颜色梯度变化和样式的颜色渐变，前者在i
- Dataset类是TensorFlow非常流行的存储数据的格式。常用来作为输入输出。data模块主要的用途就是通过这种方法创建Dataset
- 当然，5.6的GUID功能的出现也带来了multi-master的无限可能，不过这个已经是题外话了。 本文主要介绍一种非实时的适用于各版本M
- 今天项目经理刚交给一个活儿，要我实现这样一个功能：要实现的是验证码文本框变窄一点，然后右边加入一副验证码图片，并且在响应式布局的情况下在移动
- 滚动回归所谓滚动回归，通常用在时间序列上。记当前时刻为 t，回归时长为 s，则一直使用 当作自变量来预测 。使用滚动回归的目的通常是为了避免
- php判断正常访问和外部访问 <?php session_start(); if(isset($_POST['check
- 这篇文章我们玩玩numpy的数值数据类型转换导入numpy>>> import numpy as np一、随便玩玩生成一个
- 不话不多说了，直接上代码吧：<div class="layui-btn-group demoTable" styl
- 本笔记目的是通过tensorflow实现一个两层的神经网络。目的是实现一个二次函数的拟合。如何添加一层网络代码如下：def add_laye
- 本文较为详细的分析了php单一入口应用程序。分享给大家供大家参考。具体如下：什么是单一入口应用程序？在解释什么是单一入口应用程序之前，我们先
- 前言本实验中所用数据库创建SQL语句以及插入数据到数据库中的SQL语句链接：链接: https://pan.baidu.com/s/1BnF
- 最近无意中接触到了一篇文章，里面写了一个SQL的用法，是with...as，中午抽空记录一下用MySQL试了一下，发现并不支持该语法（版本:
- 很简单的一个函数，就是根据当前的日期生成一个随机数。<％ Function getRnd() '**********
- 使用pytorch的dataloader报错：RuntimeError: stack expects each tensor to be e
- 本文实例讲述了Python编程中event对象的用法。分享给大家供大家参考，具体如下：Python提供了Event对象用于线程间通信，它是由
- python加密打包程序加密方式：将py文件转为pyd格式安装easycython模块 pip install easycython使用ea
