文档章节

判断两个矩形是否相交的算法

robslove
 robslove
发布于 2015/09/27 21:38
字数 356
阅读 3025
收藏 3

判断矩形是否相交,有很多种方法,比如说判断矩形的任意两条边是否相交。但是这种方法存在一个缺陷,就是当一个矩形被另外一个矩形包含的时候,没有边是相交的但是依然符合相交的定义

另一种比较严格的数学方法,我觉得比较容易理解也比较好实现,所以就记下了吧。这个方法很简单,就是分别比较两个矩形的重心在x轴方向上和y轴方向上的距离与两个矩形的长或者宽的一半的和的大小。如果重心的在x轴和y轴上的距离都比他们边长和的一半要小就符合相交的条件

#include<stdio.h>
int ab(int n)
{
    if(n >= 0)
        return n;
    else
        return -n;
}

int main()
{
    int cases;
    int x01 , x02 , y01 , y02;
    int x11 , x12 , y11 , y12;
    scanf("%d" , &cases);
    while(cases--)
    {
        scanf("%d %d %d %d" ,&x01 ,&y01 ,&x02 , &y02);
        scanf("%d %d %d %d" ,&x11 , &y11 , &x12 , &y12);
        int zx = ab(x01+x02-x11-x12); //两个矩形重心在x轴上的距离的两倍
        int x = ab(x01-x02)+ab(x11-x12); //两矩形在x方向的边长的和
        int zy = ab(y01+y02-y11-y12); //重心在y轴上距离的两倍
        int y = ab(y01-y02)+ab(y11-y12); //y方向边长的和
        if(zx <= x && zy <= y)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}










本文转载自:http://blog.sina.com.cn/s/blog_7865b083010100ah.html

robslove

robslove

粉丝 5
博文 196
码字总数 83377
作品 0
成都
程序员
私信 提问
判断两线段是否相交

算法一 1. 快速排斥实验:设一线段P1P2为对角线的矩形为P,设一线段Q1Q2为对角线的矩形为Q,如果P和Q不相交,显然两线段不会相交。 以下2种(方法1、方法2)方法判断矩形是否相交仅限于正矩形...

乙知
2016/11/03
458
0
Unity算法——矩形技能伤害判断

前言 在大型游戏中在Unity使用物理引擎是十分消耗性能的,特别是在移动端设备中,如果过多的使用物理引擎来进行行为判断,对设备性能消耗是很厉害的,一般情况我们在Unity游戏开发中,会通过...

htlas
2018/04/25
0
0
简单地判断判断两矩形相交/重叠 C#

最近需要用到矩形相交算法的简单应用,所以特地拿一个很简单的算法出来供新手参考,为什么说是给新手的参考呢因为这个算法效率并不是很高,但是这个算法只有简简单单的三行。程序使用了两种方...

Maolic
10/31
0
0
HT for Web可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍...

xhload3d
2014/12/06
2.1K
0
HTML5实现3D和2D可视化QuadTree四叉树碰撞检测

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍...

xhload3d
2015/12/14
3.3K
3

没有更多内容

加载失败,请刷新页面

加载更多

Java 运行时获取方法参数名

本文整理 Java 运行时获取方法参数名的两种方法,Java 8 的最新的方法和 Java 8 之前的方法。 Java 8 的新特性 翻阅 Java 8 的新特性,可以看到有这么一条“JEP 118: Access to Parameter Na...

xiaomin0322
15分钟前
3
0
varchar和nvarchar有什么区别?

只是nvarchar支持多字节字符吗? 如果是这种情况,除了存储问题之外,使用varchars什么意义吗? #1楼 nVarchar将帮助您存储Unicode字符。 如果要存储本地化数据,这是可行的方法。 #2楼 nvar...

javail
18分钟前
3
0
如何通过curl调用使用HTTP请求发送标头?

我希望在Linux机器上向我的Apache服务器发送一个标头。 如何通过卷曲调用实现此目的? #1楼 得到: 使用JSON: curl -i -H "Accept: application/json" -H "Content-Type: application/json......

技术盛宴
34分钟前
4
0
SQL语句的执行过程

(一)架构组件 (二)执行流程

麦馍
39分钟前
4
0
如何快速核对Excel数据表?这样操作不同的数据一目了然

怎么快速的核对两个Excel数据表呢?组长给了同事两份报表让他在半小时内核对完毕,不同的地方要标记起来,这时候同事抱怨起来:“数据那么多半小时怎么够呢”?虽然嘴上在抱怨,但是他还是乖...

百因必有果
45分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部