当前位置: 首页 > news >正文

[math]判断线段是否相交及夹角

文章目录

    • 向量
      • 点乘
      • 叉乘
    • 线段相交
      • 快速排斥
      • 跨立实验
    • 线间夹角

通过向量间的叉乘与点乘,可判断线段间的关系。

向量

向量(也称为矢量),指具有大小和方向的量。它可以形象化地表示为带箭头的线段。

  • 箭头所指:代表向量的方向;
  • 线段长度:代表向量的大小。

点乘

a ( x 1 , y 1 ) , b ( x 2 , y 2 ) a(x_1,y_1),b(x_2,y_2) a(x1,y1),b(x2,y2)的点乘为: a ⋅ b = x 1 ∗ x 2 + y 1 ∗ y 2 a\cdot b=x_1*x_2 + y_1*y_2 ab=x1x2+y1y2

其几何意义: a ⋅ b = ∣ a ∣ ⋅ ∣ b ∣ ⋅ c o s θ a\cdot{b}=|a|\cdot |b|\cdot cos\theta ab=abcosθ

vec-dot

向量的点乘可以用来计算两个向量之间的夹角,进一步判断这两个向量是否正交(垂直)等方向关系:

  • a ⋅ b > 0 a\cdot b>0 ab>0:方向基本相同,夹角在0~90度之间
  • a ⋅ b = 0 a\cdot b=0 ab=0:正交,互相垂直
  • a ⋅ b < 0 a\cdot b<0 ab<0:方向基本相反,夹角在90~180度之间

同时,还可以用来计算一个向量在另一个向量方向上的投影长度。

叉乘

a ( x 1 , y 1 ) , b ( x 2 , y 2 ) a(x_1,y_1),b(x_2,y_2) a(x1,y1),b(x2,y2)的叉乘为:
a × b = ∣ x 1 , y 1 x 2 , y 2 ∣ = x 1 ∗ y 2 − x 2 ∗ y 1 a×b=\left| \begin{matrix} x_1, & y_1 \\ x_2, & y_2 \end{matrix} \right| =x_1*y_2 - x_2*y_1 a×b= x1,x2,y1y2 =x1y2x2y1

vec-cross

p ( 0 , 0 ) p(0,0) p(0,0)为原点,则:

  • a × b > 0 a×b>0 a×b>0,表示 p b ⃗ \vec{pb} pb p a ⃗ \vec{pa} pa 的逆时针方向;
  • a × b = 0 a×b=0 a×b=0,表示 p b ⃗ \vec{pb} pb p a ⃗ \vec{pa} pa 共线;
  • a × b < 0 a×b<0 a×b<0,表示 p b ⃗ \vec{pb} pb p a ⃗ \vec{pa} pa 的顺时针方向;
  • ∣ a × b ∣ |a×b| a×b,是以 p a ⃗ \vec{pa} pa p b ⃗ \vec{pb} pb 为临边的平行四边形的面积

线段相交

判断两条线段是否相交:

  • 快速排斥;
  • 跨立实验;

快速排斥

通过快速排斥实验,可初步判断两条线段是否有相交的可能性,从而减少计算量:以两条线段作为对角线画矩形,判断矩形是否重合;若不重合,肯定不相交。
line-rect

为此需要检验他们的最大坐标与最小坐标间的关系(任一项为真,则一定不相交):

  • max(C.x, D.x)<min(A.x, B.x)max(C.y, D.y)<min(A.y, B.y)
  • max(A.x, B.x)<min(C.x, D.x)max(A.y, B.y)<min(C.y, D.y)

跨立实验

两条线段AB、CD相交,则:

  • 线段AB与CD所在的直线相交:即A、B两点分别在直线CD的两侧;
  • 线段CD与AB所在的直线相交:即C、D两点分别在直线AB的两侧;

line-intersect

以C、D在AB两侧为例,连接AC、AD得到两个向量:

  • 向量AC在AB的逆时针方向:即AB×AC>0
  • 向量AC在AB的顺时针方向:即AB×AD<0
  • 两个叉乘结果为异号:即(AB×AC)*(AB×AD)<0
    若叉乘结果为同号,则说明在同一边,肯定不相交。

同理判断A、B是否在CD的两侧;若A、B两点分别在直线CD的两侧,且C、D两点分别在直线AB的两侧,则线段AB与CD一定相交(在完成排斥实验的基础上)

func lineIsIntersect(AB [2]Point, CD [2]Point) bool {
	ACx := CD[0].X - AB[0].X
	ACy := CD[0].Y - AB[0].Y
	ADx := CD[1].X - AB[0].X
	ADy := CD[1].Y - AB[0].Y

	ABx := AB[1].X - AB[0].X
	ABy := AB[1].Y - AB[0].Y

    AC_AB = ACx*ABy-ABx*ACy
    AD_AB = ADx*ABy-ABx*ADy
	return ()*() <= 0
}

线间夹角

通过点乘,可求出两条线间的夹角;通过计算夹角的cos值,可知向量间方向关系。

func dot(AB [2]image.Point, CD [2]image.Point) int {
	ABx := AB[1].X - AB[0].X
	ABy := AB[1].Y - AB[0].Y
	CDx := CD[1].X - CD[0].X
	CDy := CD[1].Y - CD[0].Y

	return ABx*CDx + ABy*CDy
}

func dist(line [2]image.Point) float64 {
	distX := line[1].X - line[0].X
	distY := line[1].Y - line[0].Y

	return math.Sqrt(float64(distX*distX + distY*distY))
}

func calcCos(AB [2]image.Point, CD [2]image.Point) float64 {
	return float64(dot(AB, CD)) / (dist(AB) * dist(CD))
}

相关文章:

  • 如何并行化普通的python代码
  • 人力资源团队怎样利用智能科技提升工作效率
  • 对角线的输出
  • Charles乱码和SSL 代理问题解决
  • SharedPreference使用
  • Javaweb安全——Shiro漏洞利用
  • java基本微信小程序的高校科研管理系统 uniapp小程序
  • C++ 20 协程(一)
  • 小米手机抓取hci log
  • 【Java深入学习】并发常见方法的注意事项
  • 微信小程序开发入门与实战(数据监听)
  • 【论文阅读】提升的自动作文评分通过Prompt预测和匹配
  • JPA-Specification常用条件查询构造方式
  • 瑞吉外卖(19) - 新增套餐业务开发
  • Android 的定位分层架构
  • [微信小程序] 使用ES6特性Class后出现编译异常
  • es6(二):字符串的扩展
  • Git 使用集
  • Java面向对象及其三大特征
  • Linux各目录及每个目录的详细介绍
  • 创建一种深思熟虑的文化
  • 分享一份非常强势的Android面试题
  • 记录:CentOS7.2配置LNMP环境记录
  • 经典排序算法及其 Java 实现
  • 马上搞懂 GeoJSON
  • 买一台 iPhone X,还是创建一家未来的独角兽?
  • 浅谈Kotlin实战篇之自定义View图片圆角简单应用(一)
  • 使用 Node.js 的 nodemailer 模块发送邮件(支持 QQ、163 等、支持附件)
  • 主流的CSS水平和垂直居中技术大全
  • ​LeetCode解法汇总2182. 构造限制重复的字符串
  • ​人工智能之父图灵诞辰纪念日,一起来看最受读者欢迎的AI技术好书
  • ###项目技术发展史
  • #{}和${}的区别?
  • (6)设计一个TimeMap
  • (a /b)*c的值
  • (MIT博士)林达华老师-概率模型与计算机视觉”
  • (附源码)计算机毕业设计SSM基于java的云顶博客系统
  • (十三)Java springcloud B2B2C o2o多用户商城 springcloud架构 - SSO单点登录之OAuth2.0 根据token获取用户信息(4)...
  • (数位dp) 算法竞赛入门到进阶 书本题集
  • (太强大了) - Linux 性能监控、测试、优化工具
  • (五)Python 垃圾回收机制
  • (一)Neo4j下载安装以及初次使用
  • (转)jQuery 基础
  • (转)自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
  • .“空心村”成因分析及解决对策122344
  • .bat文件调用java类的main方法
  • .net php 通信,flash与asp/php/asp.net通信的方法
  • .NET 使用 XPath 来读写 XML 文件
  • 。Net下Windows服务程序开发疑惑
  • @Autowired @Resource @Qualifier的区别
  • @FeignClient注解,fallback和fallbackFactory
  • [ C++ ] 继承
  • []Telit UC864E 拨号上网
  • [AIGC 大数据基础]hive浅谈
  • [BUG] Hadoop-3.3.4集群yarn管理页面子队列不显示任务