矩形相交以及求出相交的区域的原理解析

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

相关推荐

  • 矩形相交以及求出相交的区域的原理解析

    矩形相交以及求出相交的区域的原理解析

    (1)设计一个算法,确定两个矩形是否相交(即有重叠区域) (2)如果两个矩形相交,设计一个算法,求出相交的区域矩形 (1) 对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内.这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一 下. 如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形 内部.所以那种思路存在一个错误,对于这种情况的相交则检查不出. 仔细观察上图,想

  • 点击弹出层外区域关闭弹出层jquery特效示例

    点击弹出层外区域关闭弹出层jquery特效,废话不说,上代码,简洁明了: 复制代码 代码如下: <html> <head> <style> .hide{display:none;} .con{width:500px;height:300px;background:#000;} </style> <title>点击弹出层 ,点击弹出层外区域关闭弹出层jquery特效</title> <script type="text/

  • Python求出0~100以内的所有素数

    质数又称素数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数:否则称为合数. 一.判断一个数是否为素数: 基于定义 def is_prime(num): if num <= 1: return '%d是一个合数' % num for i in range(2, num): if not num % i: return '%d是一个合数' % num else: return '%d是一个素数' % num 考虑合数的性质 def is_prime(num): if num

  • Java读取一行空格隔开的数字字符串并求出这些数字的和方法

    如下所示: import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while(in.hasNextLine())//判断是否有输入一行数据 { String tmp = in.nextLine();//将一行数据读出 if(tmp.equals("q"))//输入q退出程序 break; Str

  • Python二维数组实现求出3*3矩阵对角线元素的和示例

    题目:求一个3*3矩阵对角线元素之和. 程序分析:利用双重for循环控制输入二维数组,再将a[i][i]累加后输出. def two_dimensionalArray(self): '二维数组实现求三阶矩阵的对角线元素之和' sum = 0 matrix = [[0, 1, 0], [0, 21, 0], [0, 12, 0]] matrix2 = [[0 for i in range(3)] for i in range(3)] matrix2[0][0] = 123 matrix2[1][1

  • python 对任意数据和曲线进行拟合并求出函数表达式的三种解决方案

    第一种是进行多项式拟合,数学上可以证明,任意函数都可以表示为多项式形式.具体示例如下. ###拟合年龄 import numpy as np import matplotlib.pyplot as plt #定义x.y散点坐标 x = [10,20,30,40,50,60,70,80] x = np.array(x) print('x is :\n',x) num = [174,236,305,334,349,351,342,323] y = np.array(num) print('y is

  • Python递归求出列表(包括列表中的子列表)的最大值实例

    要求:求出列表中的所有值的最大数,包括列表中带有子列表的. 按照Python给出的内置函数(max)只能求出列表中的最大值,无法求出包括列表中的子列表的最大值 Python3代码如下: #!/usr/bin/env python3 # _*_ coding:UTF-8 _*_ list_tmp = [1,3,5,7,9,11] print(max(list_tmp)) 返回的结果为:11 按照Python3给出内置函数(max)的方法想要违和他的要求求出列表包括子列表的数,他就会给你进行报错.

  • SQL查询语句求出用户的连续登陆天数

    SQL查询语句求出用户的连续登陆天数

    一.题目描述 求解用户登陆信息表中,每个用户连续登陆平台的天数,连续登陆基础为汇总日期必须登陆,表中每天只有一条用户登陆数据(计算中不涉及天内去重). 表描述:user_id:用户的id: sigin_date:用户的登陆日期. 二.解法分析 注:求解过程有多种方式,下述求解解法为笔者思路,其他解法可在评论区交流. 思路: 该问题的突破的在于登陆时间,计算得到连续登陆标识,以标识分组为过滤条件,得到连续登陆的天数,最后以user_id分组,以count()函数求和得到每个用户的连续登陆天数. 连

  • 如何通过C++求出链表中环的入口结点

    如何通过C++求出链表中环的入口结点

    目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 测试代码: 题目描述: 给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null. 数据范围: n≤10000,1<=结点值<=10000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示: 可以看到环的入口结点的结点值为3,所以返回结点值为3的结点. 输入描述: 输入分为2段,第一段是入环前的链表部分,第二段是链表环的部分,后台会根据第二段

  • Java求出任意数字的各个位数之和方式

    目录 求出任意数字的各个位数之和 求一个整数各位数之和 思路分析 代码 求出任意数字的各个位数之和 import java.util.Scanner; /** * 用JAVA求任意一个数的各个位数之和 * @author Administrator * */ public class test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入一

随机推荐