程序员经验分享-hwhale

判断两条线段是否相交（三种算法）

2023-05-16

转载于 ： http://blog.csdn.net/rickliuxiao/article/details/6259322


算法1：

 

[cpp]  view plain  copy
  1. ///----------alg 1------------  
  2. struct Point  
  3. {   
  4.     double x, y;  
  5. };   
  6.   
  7. bool between(double a, double X0, double X1)  
  8. {  
  9.     double temp1= a-X0;  
  10.     double temp2= a-X1;  
  11.     if ( ( temp1<1e-8 && temp2>-1e-8 ) || ( temp2<1e-6 && temp1>-1e-8 ) )  
  12.     {  
  13.         return true;  
  14.     }  
  15.     else  
  16.     {  
  17.         return false;  
  18.     }  
  19. }  
  20.   
  21.   
  22. // 判断两条直线段是否有交点，有则计算交点的坐标  
  23. // p1,p2是直线一的端点坐标  
  24. // p3,p4是直线二的端点坐标  
  25. bool detectIntersect(Point p1, Point p2, Point p3, Point p4)  
  26. {  
  27.     double line_x,line_y; //交点  
  28.     if ( (fabs(p1.x-p2.x)<1e-6) && (fabs(p3.x-p4.x)<1e-6) )  
  29.     {  
  30.         return false;  
  31.     }  
  32.     else if ( (fabs(p1.x-p2.x)<1e-6) ) //如果直线段p1p2垂直与y轴  
  33.     {  
  34.         if (between(p1.x,p3.x,p4.x))  
  35.         {  
  36.             double k = (p4.y-p3.y)/(p4.x-p3.x);  
  37.             line_x = p1.x;  
  38.             line_y = k*(line_x-p3.x)+p3.y;  
  39.   
  40.             if (between(line_y,p1.y,p2.y))  
  41.             {  
  42.                 return true;  
  43.             }  
  44.             else  
  45.             {  
  46.                 return false;  
  47.             }  
  48.         }  
  49.         else   
  50.         {  
  51.             return false;  
  52.         }  
  53.     }  
  54.     else if ( (fabs(p3.x-p4.x)<1e-6) ) //如果直线段p3p4垂直与y轴  
  55.     {  
  56.         if (between(p3.x,p1.x,p2.x))  
  57.         {  
  58.             double k = (p2.y-p1.y)/(p2.x-p1.x);  
  59.             line_x = p3.x;  
  60.             line_y = k*(line_x-p2.x)+p2.y;  
  61.   
  62.             if (between(line_y,p3.y,p4.y))  
  63.             {  
  64.                 return true;  
  65.             }  
  66.             else  
  67.             {  
  68.                 return false;  
  69.             }  
  70.         }  
  71.         else   
  72.         {  
  73.             return false;  
  74.         }  
  75.     }  
  76.     else  
  77.     {  
  78.         double k1 = (p2.y-p1.y)/(p2.x-p1.x);   
  79.         double k2 = (p4.y-p3.y)/(p4.x-p3.x);  
  80.   
  81.         if (fabs(k1-k2)<1e-6)  
  82.         {  
  83.             return false;  
  84.         }  
  85.         else   
  86.         {  
  87.             line_x = ((p3.y - p1.y) - (k2*p3.x - k1*p1.x)) / (k1-k2);  
  88.             line_y = k1*(line_x-p1.x)+p1.y;  
  89.         }  
  90.   
  91.         if (between(line_x,p1.x,p2.x)&&between(line_x,p3.x,p4.x))  
  92.         {  
  93.             return true;  
  94.         }  
  95.         else   
  96.         {  
  97.             return false;  
  98.         }  
  99.     }  
  100. }  
  101. ///------------alg 1------------  

 

 

算法2：

[cpp]  view plain  copy
  1. ///------------alg 2------------  
  2. //叉积  
  3. double mult(Point a, Point b, Point c)  
  4. {  
  5.     return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);  
  6. }  
  7.   
  8. //aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false  
  9. bool intersect(Point aa, Point bb, Point cc, Point dd)  
  10. {  
  11.     if ( max(aa.x, bb.x)<min(cc.x, dd.x) )  
  12.     {  
  13.         return false;  
  14.     }  
  15.     if ( max(aa.y, bb.y)<min(cc.y, dd.y) )  
  16.     {  
  17.         return false;  
  18.     }  
  19.     if ( max(cc.x, dd.x)<min(aa.x, bb.x) )  
  20.     {  
  21.         return false;  
  22.     }  
  23.     if ( max(cc.y, dd.y)<min(aa.y, bb.y) )  
  24.     {  
  25.         return false;  
  26.     }  
  27.     if ( mult(cc, bb, aa)*mult(bb, dd, aa)<0 )  
  28.     {  
  29.         return false;  
  30.     }  
  31.     if ( mult(aa, dd, cc)*mult(dd, bb, cc)<0 )  
  32.     {  
  33.         return false;  
  34.     }  
  35.     return true;  
  36. }  
  37. ///------------alg 2------------  
  

 

 

算法3：http://dec3.jlu.edu.cn/webcourse/t000096/graphics/chapter5/01_1.

html

[c-sharp]  view plain  copy
  1. ///------------alg 3------------  
  2. double determinant(double v1, double v2, double v3, double v4)  // 行列式  
  3. {  
  4.     return (v1*v3-v2*v4);  
  5. }  
  6.   
  7. bool intersect3(Point aa, Point bb, Point cc, Point dd)  
  8. {  
  9.     double delta = determinant(bb.x-aa.x, cc.x-dd.x, bb.y-aa.y, cc.y-dd.y);  
  10.     if ( delta<=(1e-6) && delta>=-(1e-6) )  // delta=0，表示两线段重合或平行  
  11.     {  
  12.         return false;  
  13.     }  
  14.     double namenda = determinant(cc.x-aa.x, cc.x-dd.x, cc.y-aa.y, cc.y-dd.y) / delta;  
  15.     if ( namenda>1 || namenda<0 )  
  16.     {  
  17.         return false;  
  18.     }  
  19.     double miu = determinant(bb.x-aa.x, cc.x-aa.x, bb.y-aa.y, cc.y-aa.y) / delta;  
  20.     if ( miu>1 || miu<0 )  
  21.     {  
  22.         return false;  
  23.     }  
  24.     return true;  
  25. }  
  26. ///------------alg 3------------  

 

main函数测试：

 

[cpp]  view plain  copy
  1. int main()  
  2. {  
  3.     Point p1, p2, p3, p4;  
  4.     p1.x = 1;  
  5.     p1.y = 4;  
  6.     p2.x = 3;  
  7.     p2.y = 0;  
  8.     p3.x = 0;  
  9.     p3.y = 1;  
  10.     p4.x = 4;  
  11.     p4.y = 3;  
  12.   
  13.   
  14.     int i=0, j=0;  
  15.     bool flag = false;  
  16.     flag = intersect3(p1, p2, p3, p4);  
  17.   
  18.     // alg 2  
  19.     time_t seconds1 = time (NULL);  
  20.     for ( ; i!=20000; ++i )  
  21.     {  
  22.         for ( j=0; j!=60000; ++j )  
  23.         {  
  24.             flag = detectIntersect(p1, p2, p3, p4);  
  25.         }  
  26.     }  
  27.     time_t seconds2 = time (NULL);  
  28.   
  29.     cout << "Time used in alg 1:" << seconds2-seconds1 << " seconds." << endl;  
  30.   
  31.     // alg 2  
  32.     time_t seconds3 = time (NULL);  
  33.     i=0;  
  34.     j=0;  
  35.     for ( ; i!=20000; ++i )  
  36.     {  
  37.         for ( j=0; j!=60000; ++j )  
  38.         {  
  39.             flag = intersect(p1, p2, p3, p4);  
  40.         }  
  41.     }  
  42.     time_t seconds4 = time (NULL);  
  43.     cout << "Time used in alg 2:" << seconds4-seconds3 << " seconds." << endl;  
  44.   
  45.     // alg 3  
  46.     time_t seconds5 = time (NULL);  
  47.     i=0;  
  48.     j=0;  
  49.     for ( ; i!=20000; ++i )  
  50.     {  
  51.         for ( j=0; j!=60000; ++j )  
  52.         {  
  53.             flag = intersect3(p1, p2, p3, p4);  
  54.         }  
  55.     }  
  56.     time_t seconds6 = time (NULL);  
  57.     cout << "Time used in alg 3:" << seconds6-seconds5 << " seconds." << endl;  
  58.     return 0;  
  59. }  
  

 VS2008编译器环境下测试结果：

Debug模式下： 

alg 1: 315 seconds;

alg 2: 832 seconds;

alg 3: 195 seconds;

 

Release模式下： 

alg 1: 157 seconds;

alg 2: 169 seconds;

alg 3: 122 seconds;

 

 

结论： 使用算法3，时间复杂度最低。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

判断两条线段是否相交（三种算法） 的相关文章

  • windows10共享文件夹挂载到Ubuntu

    程序开发人员一般都会把开发目录放在windows系统下 xff0c 开发环境却是linux 以前我是linux下文件挂载到windows xff0c 有同事前车之鉴 xff0c 万一虚拟机linux挂壁了 xff0c 很难恢复 现在准备把w

  • 闭包函数中use使用

    匿名函数中的use xff0c 其作用就是从父作用域继承变量 下例是最常见的用法 xff0c 如果不使用use xff0c 函数中将找不到变量 msg 1 2 3 4 5 6 7 8 lt php msg 61 1 2 3 func

  • for update秒杀

    Mysql InnoDB 排他锁 用法 xff1a select for update 例如 xff1a select from goods where id 61 1 for update 排他锁的申请前提 xff1a 没有线程对该结果集

  • UNION 和 UNION ALL

    UNION用的比较多union all是直接连接 xff0c 取到得是所有值 xff0c 记录可能有重复 union 是取唯一值 xff0c 记录没有重复 UNION 和 UNION ALL 的语法都是 xff1a SQL 语句 1 UNI

  • php网站压测(ab)

    一般来说核心页面都需要进行压测 xff0c 特别是秒杀页面 xff0c 从而知道网站的承受能力 xff0c 方便暴露一些问题 xff0c 更好的把控网站 压测工具有很多种 xff0c 最简单 方便的可以使用ApacheBench xff0c

  • CSV文件读取 C++版本

    代码 span class token comment 创建结构体 xff0c 把读取数据可以放入结构体成员中 span span class token keyword struct span span class token class

  • 四种常见的 POST 提交数据方式

    HTTP 1 1 协议规定的 HTTP 请求方法有 OPTIONS GET HEAD POST PUT DELETE TRACE CONNECT 这几种 其中 POST 一般用来向服务端提交数据 xff0c 本文主要讨论 POST 提交数据

  • json_decode

    json 61 34 34 errorno 34 0 34 errormsg 34 34 可以 34 34 data 34 34 guid 34 34 5762340 34 34 username 34 34 wiu370468 34 34

  • csv乱码处理

    handle 61 fopen 34 war csv 34 34 r 34 row 61 1 while data 61 fgetcsv handle 1000 34 34 data 61 eval 39 return 39 iconv 3

  • OR和AND关键字一起使用的情况

    OR和AND关键字一起使用的情况 OR关键字和AND关键字 xff0c 可以一起使用 xff0c 需要注意 xff0c AND的优先级高于OR 因此 xff0c 当两者一起使用时 xff0c 应该先运算AND两边的条件表达式 xff0c 再

  • Ubuntu cron 定时执行任务

    cron xff0c 是一个Linux定时执行工具 xff0c 可以在无需人工干预的情况下运行作业 1 关于crontab 在Ubuntu server 下 xff0c cron是被默认安装并启动的 通过 etc crontab文件 xff

  • Linux服务器上监控网络带宽的18个常用命令

    本文介绍了一些可以用来监控网络使用情况的Linux命令行工具 这些工具可以监控通过网络接口传输的数据 xff0c 并测量目前哪些数据所传输的速度 入站流量和出站流量分开来显示 一些命令可以显示单个进程所使用的带宽 这样一来 xff0c 用户

  • Linux系统使用iftop查看带宽占用情况

    Linux系统下如果服务器带宽跑满了 xff0c 查看跟哪个ip通信占用带宽比较多 xff0c 可以通过iftop命令进行查询 xff0c 使用方法如下 xff1a 1 安装方法 软件官网地址 xff1a http www ex parro

  • linux基础命令

    1 curl amp wget 使用curl或wget命令 xff0c 不用离开终端就可以下载文件 如你用curl xff0c 键入curl O后面跟一个文件路径 wget则不需要任何选项 下载的文件在当前目录 代码如下 curl O we

  • find_in_set

    1 in查询相当于多个or条件的叠加 xff0c 例如 xff1a select from user where user id in 1 2 3 等效于 select from user where user id 61 1 or use

  • 集成Cortex-M0内核-- Integration and Implementation Manual手册学习

    根据使用场景 xff0c 配置并集成一个Cortex M0的内核 xff0c 暂时不涉及的实现的部分 目录 阅读手册 Chapter1 Introduction 1 1 About the processor 1 2 About integ

  • 在NVIDIA NX 配置OpenCV多版本冲突和解决的总结

    Nvidia Jetson NX 环境 直接刷JetPack5 1的镜像 xff0c 会得到如下环境 Ubuntu20 04cuda11 4TensorRT8 4cudnn8 4opencv4 5 4 而且这些源一般是从nv xxxx等源下

  • 一款入门级的飞控CC3D（一）

    很多在校的朋友想自己动手做一款旋翼无人机 xff0c 但是零件采购下来要花费不少大洋 xff0c 装配完成后又需要进行软件硬件调试 所以很多想做极客的梦就扼杀在摇篮里 本期我将开始更新一款入门级的飞控CC3D 首先 xff0c 放上CC3D

  • 朱刘算法（Directed Minimum Spanning Tree/Directed MST/Minimum Arborescence/Optimum Branchings）

    概念 最小树形图 xff1a 有向图所分离出的有向生成树 亦称为最小树形图 xff0c 其应满足以下条件 xff1a 1 恰好有一个入度为0的点 xff0c 称为根结点 2 其他结点的入度均为1 3 可以从根结点到达其他结点 既然要找最小生

  • 仿真复现文章推荐

    以下学长推荐的文章 xff1a 人脸识别 xff1a SphereFace Deep Hypersphere Embedding for Face Recognition 手势姿态 xff1a OpenPose 3D人脸建模 xff1a L

随机推荐

  • 查看GPU显存 使用率

    watch n 0 2 nvidia smi 主要关注GPU Util Memory Usage 0 2表示每隔0 2秒刷新一次终端的显示结果 上面的表格中 xff1a 第一栏的Fan xff1a N A是风扇转速 xff0c 从0到100

  • scipy.ndimage.zoom

    最近邻 选择离它所映射到的位置最近的输入像素的灰度值为插值结果 最临近插值 3X3 的256级灰度图 xff0c 也就是高为3个象素 xff0c 宽也是3个象素的图像 xff0c 每个象素的取值可以是 0 xff0d 255 xff0c 代

  • torch.manual_seed()

    torch manual seed args seed 为CPU设置种子用于生成随机数 xff0c 以使得结果是确定的 if args cuda torch cuda manual seed args seed 为当前GPU设置随机种子 x

  • python torch.optim.SGD

    torch optim sgd学习参数 torch入门笔记14 Torch中optim的sgd Stochastic gradient descent 方法的实现细节 pytorch中使用torch optim优化神经网络以及优化器的选择

  • python zero_grad()

    有两种方式直接把模型的参数梯度设成0 xff1a model span class hljs preprocessor zero span grad optimizer span class hljs preprocessor zero s

  • torch.topk

    torch kthvalue input k dim 61 None keepdim 61 False out 61 None gt Tensor LongTensor k xff1a 第k个最小元素 返回第k个最小元素 input k d

  • torch.normal()

    torch normal means std out 61 None 返回一个张量 xff0c 包含从给定参数means std的离散正态分布中抽取随机数 均值means是一个张量 xff0c 包含每个输出元素相关的正态分布的均值 std是

  • 台式机ubuntu18.04 x86_64 简单ROS版本安装及其他库编译

    本教程是用于只安装ros melodic ros base的情况下 xff0c 为了避免安装opencv3 2 xff0c 而只保留一个opencv3 4 10 xff0c 而一步步安装rqt xff0c cv bridge xff0c r

  • ubuntu 当前文件夹 文件个数

    ls l grep 34 34 wc l

  • python [:,::-1]

    In span class hljs number 33 span t 61 np array span class hljs string 1 2 3 4 5 6 7 8 9 span In span class hljs number

  • numpy.floor

    numpy floor x out 61 None where 61 True casting 61 39 same kind 39 order 61 39 K 39 dtype 61 None subok 61 True signatur

  • Perfdog玩转内存泄漏

    背景交代 最近QC同学在跑游戏的过程中发现玩的时间久了游戏会发生闪退 xff0c 经过和开发人员讨论后又搜集了一些信息 xff0c 最后排除了功能性bug的原因 一 判断是否是内存泄露 拿到真机 xff0c USB连接 xff0c 杀掉多余

  • LCD1602知识详解（很详尽的）

    1602液晶知识详解 xff1a 1 1602液晶基础 VSS xff1a 电源地信号引脚 xff1b VDD xff1a 电源信号引脚 xff1b VEE xff1a 液晶对比度调节引脚 xff0c 接0 5V以调节液晶的显示对比度 xf

  • 如何学习嵌入式软件

    什么是嵌入式 xff1f 嵌入式分为广义和狭义两种 广义的嵌入式就是片上系统 system on a chip xff0c 包括单片机 PSOC NIOS Microblaze等 而狭义的嵌入式就是ARM9 cortex A8等特定的跑操作

  • Raspberry Pi 4B 通过 MAVROS 实现从地面站远程连接飞控板

    Raspberry Pi 4B 通过 MAVROS 实现从地面站远程连接飞控板 0x00 为 RPi 刷写系统0x01 启动 Ubuntu0x02 使用 SSH 连接至 RPi0x03 更换软件源0x04 安装桌面环境 xff08 可选 x

  • LeetCode-T97-交错字符串（interleaving-string）

    题目 原题链接 题目描述 xff1a 给定三个字符串 s1 s2 s3 验证 s3 是否是由 s1 和 s2 交错组成的 样例 case1 输入 s1 61 aabcc s2 61 dbbca s3 61 aadbbcbcac 输出 tru

  • LeetCode-T167-两数之和 II - 输入有序数组(two-sum-ii-input-array-is-sorted)

    题目 原题链接 题目描述 xff1a 给定一个已按照升序排列 的有序数组 xff0c 找到两个数使得它们相加之和等于目标数 函数应该返回这两个下标值 index1 和 index2 xff0c 其中 index1 必须小于 index2 说

  • LeetCode-T95-不同的二叉搜索树 II(unique-binary-search-trees-ii)

    题目 题目链接 题目描述 给定一个整数 n xff0c 生成所有由 1 n 为节点所组成的 二叉搜索树 样例 case1 输入 xff1a 3 输出 xff1a 1 null 3 2 3 2 null 1 3 1 null null 2 2

  • 主从机时间同步

    安装 服务器和客户端都安装 sudo apt get install ntpsudo apt get install ntpdate 服务器端 配置文件设置 运行sudo vim etc ntp conf在文件末尾加入如下几行代码 rest

  • 判断两条线段是否相交（三种算法）

    转载于 xff1a http blog csdn net rickliuxiao article details 6259322 算法1 xff1a cpp view plain copy alg 1 struct Point double

热门标签