草庐IT

几何算法：矩形碰撞和包含检测算法

前端西瓜哥 2023-03-28 原文

大家好，我是前端西瓜哥。今天来讲讲几何算法中，比较经典的算法：矩形碰撞和包含检测算法。

矩形碰撞检测是被广泛使用的算法。

比如在游戏中，为了优化图形碰撞判断效率（复杂不规则图形之间的碰撞算法很复杂），经常会使用到包围盒。

所谓包围盒子是一个矩形，通常正好包围住一个规则或不规则的图形。如果两个图形的包围盒没有发生碰撞，那这两个图形一定不会发生碰撞，因为矩形的碰撞算法很简单，所以能够很好地优化性能。

算法实现

考虑到有些读者对原理不感兴趣，想赶紧找到算法复制粘贴，很急，我这里先直接贴上代码实现。

判断矩形是否碰撞：

function isRectIntersect(rect1, rect2) {
return (
rect1.x <= rect2.x + rect2.width &&
rect1.x + rect1.width >= rect2.x &&
rect1.y <= rect2.y + rect2.height &&
rect1.y + rect1.height >= rect2.y
);
}
判断矩形 1 是否包含矩形 2：

function isRectContain(rect1, rect2) {
return (
rect1.x <= rect2.x &&
rect1.x + rect1.width >= rect2.x + rect2.width &&
rect1.y <= rect2.y &&
rect1.y + rect1.height >= rect2.y + rect2.height
);
}

矩形碰撞检测原理

首先明确矩形的定义。我们用 4 个属性来描述一个矩形，分别为 x、y、width、height，表示矩形的左上角位置和尺寸。

这里用主流的坐标系统表示，以屏幕左上角为原点，x轴正方向向右，y 轴正方形向下。

或者我们可以用 minX、minY、maxX，minY 来表示：

矩形碰撞，也叫矩形相交。矩形发生碰撞的条件是：两个矩形有重叠的区域。

下图是两个矩形碰撞的一些情况：

先看 x 维度，将两个矩形往 x 轴线上投影，我们得到两条线段。

矩形要相交，首先 x 的范围上就应该有交集，等价于判断两个线段是否有交点。

先看看什么情况下它们 不会相交？答案是：一条线段的右端点在另一条线的的左端点的左侧。

所以相交的逻辑是：

!(rect1.x > rect2.x + rect2.width || rect1.x + rect1.width < rect2.x)
转换一下，就是：

rect1.x <= rect2.x + rect2.width &&
rect1.x + rect1.width >= rect2.x
y 维度同理，为：

rect1.y <= rect2.y + rect2.height &&
rect1.y + rect1.height >= rect2.y
所以最终算法实现为：

function isRectIntersect(rect1: IRect, rect2: IRect) {
return (
rect1.x <= rect2.x + rect2.width && // minX1 <maxX
rect1.x + rect1.width >= rect2.x &&
rect1.y <= rect2.y + rect2.height &&
rect1.y + rect1.height >= rect2.y
);
}

矩形包含原理

思路类似矩形碰撞。

也是判断两条线段的位置关系，rect 1 包含 rect 2，首先在 x 维度上需要满足 rect 2 的两个点都在 rect 1 的 x 范围内。

代码为：

rect1.x <= rect2.x &&
rect1.x + rect1.width >= rect2.x + rect2.width
y 同理，最终代码实现为：

function isRectContain(rect1, rect2) {
return (
rect1.x <= rect2.x &&
rect1.x + rect1.width >= rect2.x + rect2.width &&
rect1.y <= rect2.y &&
rect1.y + rect1.height >= rect2.y + rect2.height
);
}

结尾

矩形算法的碰撞和包含算法，思路是降低维度，分解为判断线段的相交关系。

算法几何spanstylecolor开发前端$几何算法矩形碰撞检测

有关几何算法：矩形碰撞和包含检测算法的更多相关文章

  1. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  2. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. 旋转矩阵的几何意义 - 2

    点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前，先介绍一下点向量坐标矩阵的几何含义点：在一维空间下就是一个标量，如同一条直线上，以任意某一个位置为0点，以一定的尺度间隔为1，2，3...,相反方向为-1，-2，-3...；如此就形成了一维坐标系，这时候任何一个点都可以用一个数值表示，如点p1=5，即即从原点出发沿着x轴正方向移动5个尺度；点p2=-3，负方向移动3个尺度；     在一维坐标系上过原点做垂直于一维坐标系的直线，则形成了二维坐标系，此时描述一个点需要两个数值来表示点p3=（3，2），即从原点出发沿着x轴正方向移动3个尺度，在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。

  5. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  6. ruby-on-rails - 使用包含多个关联和单独的条件 - 2

    我的Gallery模型中有以下查询:media_items.includes(:photo,:video).rank(:position_in_gallery)我的图库模型有_许多媒体项，每个都有一个照片或视频关联。到目前为止，一切正常。它返回所有media_items包括它们的photo或video关联，由media_item的position_in_gallery属性排序。但是我现在需要将此查询返回的照片限制为仅具有is_processing属性的照片，即nil。是否可以进行相同的查询，但条件是返回的照片等同于:.where(photo:'photo.is_processingIS

  7. ruby - 我怎样才能只写一次 "Text"并同时检查 path_info 是否包含 'A' ？ - 2

    -if!request.path_info.include?'A'%{:id=>'A'}"Text"-else"Text"“文本”写了两次。我怎样才能只写一次并同时检查path_info是否包含“A”？ 最佳答案 有两种方法可以做到这一点。使用部分，或使用content_forblock:如果“文本”较长，或者是一个重要的子树，您可以将其提取到一个部分。这会使您的代码变干一点。在给出的示例中，这似乎有点矫枉过正。在这种情况下更好的方法是使用content_forblock，如下所示:-if!request.path_info.inc

  8. Ruby，使用包含 TK GUI 的 ocra 部署一个 exe - 2

    Ocra无法处理需要“tk”的应用程序require'tk'puts'nope'用奥克拉http://github.com/larsch/ocra不起作用(如链接中的一个问题所述)问题:https://github.com/larsch/ocra/issues/29(Ocra是1.9的"new"rubyscript2exe，本质上它用于将rb脚本部署为可执行文件)唯一的问题似乎是缺少tcl的DLL文件我不认为这是一个问题据我所知，问题是缺少tk的DLL文件如果它们是已知的，则可以在执行ocra时将它们包括在内有没有办法知道tk工作所需的DLL依赖项？ 最佳答

  9. ruby - 允许主机名包含下划线的 URI.parse 的替代方法 - 2

    我正在使用DMOZ的listofurltopics，其中包含一些具有包含下划线的主机名的url。例如:608609TheOuterHeaven610InformationandimagegalleryofMcFarlane'sactionfiguresforTrigun,Akira,TenchiMuyoandotherJapaneseSci-Fianimations.611Top/Arts/Animation/Anime/Collectibles/Models_and_Figures/Action_Figures612虽然此url可以在网络浏览器中使用(或者至少在我的浏览器中可以使用:

  10. Ruby 计数数组对象，如果对象包含值 - 2

    我有一个数组:array=['Footballs','Baseball','football','Soccer']而且我需要计算看到Football或Baseball的次数，无论大小写和复数形式如何。这是我尝试做的，但没有成功:array.count{|x|x.downcase.include?'football'||x.downcase.include?'baseball'}编写这段代码的正确或更好的方法是什么？我正在寻找3作为答案。 最佳答案 我会将count与一个block结合使用，该block根据与您正在寻找的约束相匹配的正

随机推荐