碰撞检测:判断线段相交

2024-02-04 10:48

本文主要是介绍碰撞检测:判断线段相交,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文乃Siliphen原创,转载请注明出处:http://blog.csdn.net/stevenkylelee

文本demo演示:

在这里插入图片描述

本文介绍的判断线段相交的算法用到2D向量叉乘,
所以先来了解一下:2D向量的叉乘(叉积)

2D叉乘

3D 叉乘:
3D 叉乘的结果是一个 3D 向量,这个向量垂直于参与运算的2个向量的法向量。
3D 叉乘计算公式:( a.y * b.z - b.y * a.z , a.z * b.x - b.z * a.x , a.x * b.y - b.x * a.y )

2D叉乘:
2D 叉乘的结果是一个标量。
2D 叉乘就是把 2D 点看作 3D 的点( z 轴的值为 0 ),套进 3D 叉乘公式进行计算。
例如:有2个2D向量 a , b ,计算叉乘就是:
( a.y * b.z - b.y * 0 , 0 * b.x - b.z * a.x , a.x * b.y - b.x * a.y )= ( 0 , 0 , a.x * b.y - b.x * a.y )
套进3D叉乘公式计算的2D叉乘的结果的 x , y 分量均为 0 ,只有 z 有意义。
所以,标量 z 是 2D 叉乘的结果。

2D 叉乘公式:
设两个 2D 向量 a , b,叉乘公式:a.x * b.y - b.x * a.y

向量 a 叉乘 向量 b 结果的意义:

  • a ,b 向量构成的平行四边形的面积。
  • 方位:以 a 为参考轴,b 相对于 a 的方位。
    结果 > 0 正数 :b 在 a 的左边,a 的逆时针旋转方向。a 逆时针旋转到 b 的角度小于180°。
    结果 < 0 负数 :b 在 a 的右边,a 的顺时针旋转方向。a 顺时针旋转到 b 的角度小于180°。
    结果 = 0 :a 和 b 向量是平行的。

在这里插入图片描述

如上图所示:
向量 a 把空间分为2部分:

  • 左边的空间:逆时针旋转180°范围内的空间。
  • 右边的空间:顺时针旋转180°范围内的空间。

a 叉乘 b 的结果是 > 0 的正数,b 在 a 的左边。
a 叉乘 c , d 的结果是 < 0 的负数,c , d 在 a 的右边。
a 叉乘 a 的结果是0。因为 a 和它自己是平行的。

2D向量叉乘demo演示:在这里插入图片描述

判断线段是否相交:基于2D叉乘

基本思想:

一个线段会把空间分为2部分,以这个线段为分界线,判断是否另一个线段2个端点分别在这个线段分割的2个空间中。
如果2个线段的2个端点都分别在另一个线段分割的2个空间中,那么就认为是相交。

如下图,有线段 a 和 b
在这里插入图片描述

线段 a 把空间分为2部分,浅蓝和浅绿2部分。
b 的2个端点 bp1、bp2 分别在 a 划分出来的2个空间中。
在这里插入图片描述

同样的,线段 b 把空间分为2部分,浅蓝和浅绿2部分。
a 的 2个端点 ap1 , ap2 分别在 b 划分出来的2个空间中。
在这里插入图片描述

如上图所示,
2个线段的2个端点都在另一个线段分割出来的2个空间中,这2个线段相交。

算法描述:

设有2个线段 a , b 。线段 a 的2个端点为:ap1 , ap2 , 线段 b 的 2个端点为:bp1 , bp2 。
条件1:是否 向量 ap1->bp1 、ap1->bp2 分别位于向量 ap1->ap2 的左右2端。
条件2:是否 向量 bp1->ap1 、bp1->ap2 分别位于向量 bp1->bp2 的左右2端。
当条件1和条件2同时满足时,线段 a , b 相交。

判断一个向量之于另一个向量的方位,可以用2D叉乘。

下图演示如何判断 线段 a 的2个端点分别在线段 b 分割出来的2个空间中。
在这里插入图片描述

以 bp2 为起点,拉出3条向量。分别是 v = bp2->bp1 ,v1 = bp2->ap1 , v2 = bp2->ap2
计算:
c1 = v 叉乘 v1
c2 = v 叉乘 v2
如果 c1 , c2 有一个为负数另一个为正数或者为0,那么说明线段a的2端分别在线段b分割的2个空间中。
c1 和 c2 的值相乘,结果为负数说明互为相反符号的数,否者是相同符号。
条件1计算完毕。

条件2的计算示意图如下,计算过程如法炮制条件1。
在这里插入图片描述

本文demo工程下载:

demo 工程是 cocos creator 2.0.8 写的。
可执行文件是一个网页,直接运行 index.htm 即可。

下载地址:
https://download.csdn.net/download/stevenkylelee/10977144

这篇关于碰撞检测:判断线段相交的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/677234

相关文章

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

判断PyTorch是GPU版还是CPU版的方法小结

《判断PyTorch是GPU版还是CPU版的方法小结》PyTorch作为当前最流行的深度学习框架之一,支持在CPU和GPU(NVIDIACUDA)上运行,所以对于深度学习开发者来说,正确识别PyTor... 目录前言为什么需要区分GPU和CPU版本?性能差异硬件要求如何检查PyTorch版本?方法1:使用命

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D