【计算几何】判断一条线段和一段圆弧是否相交 C++代码实现

news/2024/10/18 18:16:08/

文章目录

  • 一、前言
  • 二、线段与圆弧的代码表示
    • 2.1 线段代码表示
    • 2.2 圆弧代码表示
  • 三、实现思路及数学推导
    • 3.1 第一步(粗略判断)
    • 3.2 第二步
    • 3.3 第三步
  • 四、完整代码
  • 五、效果展示


一、前言

最近做项目,需要判断一条线段是否和一段圆弧相交,网上也没找到很好的解答(最主要是没有直接可以搬来用的代码,或者思路写得太过高深,我看不懂),于是决定自己想一个方法,写一个博客,将实现思路和完整代码都分享出来


二、线段与圆弧的代码表示

2.1 线段代码表示

线段可用两个点表示,点的对象如下所示,包含x和y坐标信息:

class Point {
public:Point(double px=0.0, double py=0.0) {x = px;y = py;}double x;double y;
};

2.2 圆弧代码表示

圆弧由圆心坐标、半径、起始和终止角度组成:

class Arc
{
public:Point centerpoint; // 圆心double radius; // 圆弧半径double bangle; // 起点角度double eangle; // 终点角度
};

三、实现思路及数学推导

3.1 第一步(粗略判断)

第一步(粗略判断):将线段当成直线,将圆弧当成圆,如果直线和圆不相交,则线段和圆弧必然不相交,否则进行下一步判断

首先,将线段扩展成一条直线,它的方程为: y = k x + c y=kx+c y=kx+c

根据线段的两个点(假设为 p 1 p_1 p1 p 2 p_2 p2,且 p 1 . x ≤ p 2 . x p_1.x\le p_2.x p1.xp2.x)信息,我们可以很轻易求出 k k k c c c 的取值

p 1 p_1 p1 p 2 p_2 p2 代入直线方程:

{ p 1 . y = k p 1 . x + c ( 1 ) p 2 . y = k p 2 . x + c ( 2 ) \begin{cases} p_1.y=kp_1.x+c\,\, \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 1 \right)\\ p_2.y=kp_2.x+c\,\, \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 2 \right) \end{cases} {p1.y=kp1.x+c             (1)p2.y=kp2.x+c             (2)

( 1 ) − ( 2 ) (1)-(2) (1)(2) 可得:

p 1 . y − p 2 . y = ( p 1 . x − p 2 . x ) k ⇒ k = p 1 . y − p 2 . y p 1 . x − p 2 . x ( 3 ) p_1.y-p_2.y=\left( p_1.x-p_2.x \right) k \\ \Rightarrow k=\frac{p_1.y-p_2.y}{p_1.x-p_2.x} \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 3 \right) p1.yp2.y=(p1.xp2.x)kk=p1.xp2.xp1.yp2.y             (3)

( 3 ) (3) (3) 代入 ( 1 ) (1) (1) 可得:

p 1 . y = p 1 . y − p 2 . y p 1 . x − p 2 . x p 1 . x + c ⇒ c = p 1 . y − p 1 . y − p 2 . y p 1 . x − p 2 . x p 1 . x ( 4 ) p_1.y=\frac{p_1.y-p_2.y}{p_1.x-p_2.x}p_1.x+c \\ \Rightarrow c=p_1.y-\frac{p_1.y-p_2.y}{p_1.x-p_2.x}p_1.x \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 4 \right) p1.y=p1.xp2.xp1.yp2.yp1.x+cc=p1.yp1.xp2.xp1.yp2.yp1.x             (4)

假设圆心坐标为 ( a , b ) (a,b) (a,b) ,半径为 r r r ,容易写出圆弧扩展而成的圆的方程如下所示:

( x − a ) 2 + ( y − b ) 2 = r 2 ( 5 ) (x-a)^2+(y-b)^2=r^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 5 \right) (xa)2+(yb)2=r2             (5)

要判断直线和圆是否相交,需要将直线方程和圆方程进行联立得:

{ y = k x + c ( x − a ) 2 + ( y − b ) 2 = r 2 ⇓ ( x − a ) 2 + ( k x + c − b ) 2 = r 2 , 令 d = c − b ⇓ x 2 + a 2 − 2 a x + k 2 x 2 + d 2 + 2 k d x = r 2 ⇓ ( 1 + k 2 ) x 2 + ( 2 k d − 2 a ) x + a 2 + d 2 − r 2 = 0 ( 6 ) \begin{cases} y=kx+c \\ (x-a)^2+(y-b)^2=r^2 \\ \end{cases} \\ \Downarrow \\ (x-a)^2+(kx+c-b)^2=r^2,令d=c-b \\ \Downarrow \\ x^2+a^2-2ax+k^2x^2+d^2+2kdx=r^2 \\ \Downarrow \\ (1+k^2)x^2+(2kd-2a)x+a^2+d^2-r^2=0 \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 6 \right) {y=kx+c(xa)2+(yb)2=r2(xa)2+(kx+cb)2=r2,d=cbx2+a22ax+k2x2+d2+2kdx=r2(1+k2)x2+(2kd2a)x+a2+d2r2=0             (6)

根据韦达定理判断一元二次方程 ( 6 ) (6) (6) 是否存在实数根:

Δ = ( 2 k d − 2 a ) 2 − 4 ( 1 + k 2 ) ( a 2 + d 2 − r 2 ) ⇒ { Δ < 0 : 式 ( 6 ) 不存在实数根 Δ ≥ 0 : 式 ( 6 ) 存在实数根 \varDelta=(2kd-2a)^2-4(1+k^2)(a^2+d^2-r^2) \Rightarrow \begin{cases} \varDelta<0: 式 (6) 不存在实数根 \\ \varDelta\ge0:式 (6) 存在实数根 \end{cases} Δ=(2kd2a)24(1+k2)(a2+d2r2){Δ<0:(6)不存在实数根Δ0:(6)存在实数根

如果式 ( 6 ) (6) (6) 不存在实数根,意味着直线和圆没有交点,此时线段和圆弧必然也没有交点,程序结束。

如果式 ( 6 ) (6) (6) 存在实数根,则可以解出直线与圆的两个交点的 X X X 方向坐标 x 1 x_1 x1 x 2 x_2 x2

x 1 = − ( 2 k d − 2 a ) + Δ 2 ( 1 + k 2 ) 和  x 2 = − ( 2 k d − 2 a ) − Δ 2 ( 1 + k 2 ) x_1=\frac{-(2kd-2a)+\sqrt{\varDelta}}{2(1+k^2)} \ 和 \ x_2=\frac{-(2kd-2a)-\sqrt{\varDelta}}{2(1+k^2)} x1=2(1+k2)(2kd2a)+Δ   x2=2(1+k2)(2kd2a)Δ

x 1 x_1 x1 x 2 x_2 x2 分别代入直线方程 y = k x + c y=kx+c y=kx+c 可得两个交点的 Y Y Y 方向坐标 y 1 y_1 y1 y 2 y_2 y2

y 1 = k x 1 + c 和  y 2 = k x 2 + c y_1=kx_1+c \ 和\ y_2=kx_2+c y1=kx1+c  y2=kx2+c

然后进行下一步判断

3.2 第二步

第二步:判断直线和圆的两个交点是否在线段上,如果不在,说明线段和圆弧必然不相交,否则进行下一步判断

线段是连续的,所以可以通过区间判断两个交点是否在线段上

详细地说,我们已经知道线段的X轴方向的区间为 [ p 1 . x , p 2 . x ] [p_1.x\ ,\ p_2.x] [p1.x , p2.x]

如果 x 1 x_1 x1 不在 [ p 1 . x , p 2 . x ] [p_1.x\ ,\ p_2.x] [p1.x , p2.x] 区间内,则点 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 不在线段上,也就不可能是线段和圆弧的交点

同理,如果 x 2 x_2 x2 不在 [ p 1 . x , p 2 . x ] [p_1.x\ ,\ p_2.x] [p1.x , p2.x] 区间内,则点 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 也不可能是线段和圆弧的交点

如果点 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和点 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 都不是线段和圆弧的交点,则说明线段和圆弧必然不相交

否则进行下一步判断

3.3 第三步

第三步:根据前面的推导,假设已知直线和圆的一个在线段上的交点为 ( x 1 , y 1 ) (x_1,y_1) (x1,y1),在这一步中,需要判断该点是否在圆弧上,如果在,则说明线段和圆弧相交,且交点为 ( x 1 , y 1 ) (x_1,y_1) (x1,y1)

在这一步中,需要使用圆的参数方程,为了方便表示,假设圆弧的起始角度和终止角度分别为 θ 1 \theta_1 θ1 θ 2 \theta_2 θ2,则圆弧的参数方程为:

{ x = a + r c o s θ ( 7 ) y = b + r s i n θ ( 8 ) , θ 1 ≤ θ ≤ θ 2 \begin{cases} x=a+rcos\theta \ \ \ \ \left( 7 \right) \\ y=b+rsin\theta \ \ \ \ \left( 8 \right) \\ \end{cases} \ \ \ \ ,\theta_1\le\theta\le\theta_2 {x=a+rcosθ    (7)y=b+rsinθ    (8)    ,θ1θθ2

( x 1 , y 1 ) (x_1,y_1) (x1,y1) 代入式 ( 7 ) (7) (7) 和式 ( 8 ) (8) (8) 中:

{ x 1 = a + r c o s θ y 1 = b + r s i n θ , θ 1 ≤ θ ≤ θ 2 ⇓ { x 1 − a = r c o s θ ( 9 ) y 1 − b = r s i n θ ( 10 ) , θ 1 ≤ θ ≤ θ 2 \begin{cases} x_1=a+rcos\theta \\ y_1=b+rsin\theta \\ \end{cases} \ \ \ \ ,\theta_1\le\theta\le\theta_2 \\ \Downarrow \\ \begin{cases} x_1-a=rcos\theta \ \ \ \ \left( 9 \right) \\ y_1-b=rsin\theta \ \ \ \ \left( 10 \right) \\ \end{cases} \ \ \ \ ,\theta_1\le\theta\le\theta_2 {x1=a+rcosθy1=b+rsinθ    ,θ1θθ2{x1a=rcosθ    (9)y1b=rsinθ    (10)    ,θ1θθ2

( 10 ) (10) (10) ( 9 ) (9) (9) 可得:

y 1 − b x 1 − a = t a n θ ⇓ θ = a r c t a n ( y 1 − b x 1 − a ) \frac{y_1-b}{x_1-a}=tan\theta \\ \Downarrow \\ \theta = arctan(\frac{y_1-b}{x_1-a}) x1ay1b=tanθθ=arctan(x1ay1b)

如果解出的 θ \theta θ 不在区间 [ θ 1 , θ 2 ] [\theta_1,\theta_2] [θ1,θ2] 内,则说明点 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 不在圆弧上

否则,点 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 在圆弧上,并且是线段和圆弧的一个交点

至此,证毕!

注意:使用 a t a n atan atan 函数计算反正切值时,返回值的取值范围是 [ − π 2 , π 2 ] [-\frac{\pi}{2},\frac{\pi}{2}] [2π,2π],而 θ \theta θ 的取值是 [ 0 , 2 π ] [0,2\pi] [0,2π],所以在实际代码中需要对角度进行转换


四、完整代码

// 圆周率
#define PI acos(-1)
// 浮点型数据精度
#define ERROR 0.0000001// lineIsIntersectArc 的辅助函数:接着第二步判断
bool lineIsIntersectArcAuxiliaryFunction(Point p1, Point p2, double a, double b, double theta1, double theta2, double x1, double y1){// 2.3 判断交点是否在线段上if (p1.x <= x1 && x1 <= p2.x){// 第三步:交点(x1,y1)在线段上,再判断该点是否在圆弧上,如果在,则说明线段和圆弧相交,且交点为(x1,y1)// 3,1 计算 theta ,并转化为角度值double theta = atan((y1 - b) / (x1 - a)) / PI * 180.0;// 3.2 修正角度值,确保 theta1 <= theta2if (theta1 > theta2){if (theta2 >= 0){theta1 -= 360;}else{theta2 += 360;}			}if (theta1 < 0 && theta2 < 0){theta1 += 360;theta2 += 360;}// 3.3 修正 tan 的角度if (x1 < a){theta += 180;}// 3.4 在端点时,由于精度误差,有时可能会出现判断出错 (即出现 10.000000001 > 10 的情况),故以极小的误差接受(x1,y1)为圆弧的某个端点if (abs(theta1 - theta) < ERROR || abs(theta2 - theta) < ERROR){return true;}// 3.5 判断 theta 是否在圆弧范围内,如果在则(x1,y1)是线段和圆弧的交点,否则不是return theta1 <= theta && theta <= theta2;}return false;
}// 判断一个线段是否和圆弧相交
bool lineIsIntersectArc(Point p1, Point p2, Arc arc){// 确保 p1.x <= p2.xif (p1.x > p2.x){DL_VertexData temp = p1;p1 = p2;p2 = temp;}// 简化圆弧的相关变量表示double a = arc.centerpoint.x;double b = arc.centerpoint.y;double r = arc.radius;double theta1 = arc.bangle;double theta2 = arc.eangle;// 第一步(粗略判断):将线段当成直线,将圆弧当成圆,如果直线和圆不相交,则线段和圆弧必然不相交,否则进行下一步判断// 1.1 根据公式,计算直线方程 y=kx+c 中的 k 和 cdouble k = (p1.y - p2.y) / (p1.x - p2.x);double c = p1.y - (p1.y - p2.y) / (p1.x - p2.x)*p1.x;// 1.2 根据韦达定理判断式(6)是否存在实数根double d = c - b;double varDelta = pow(2 * k*d-2*a, 2) - 4 * (1 + k*k)*(a*a + d*d - r*r);if (varDelta >= 0){// 第二步:判断直线和圆的两个交点是否在线段上,如果不在,说明线段和圆弧必然不相交,否则进行下一步判断// 2.1 计算两个交点的坐标(x1,y1)和(x2,y2)double x1 = (2 * a - 2 * k*d + sqrt(varDelta)) / (2 * (1 + k*k));double x2 = (2 * a - 2 * k*d - sqrt(varDelta)) / (2 * (1 + k*k));double y1 = k*x1 + c;double y2 = k*x2 + c;// 2.2 判断两个交点是否相等if (varDelta == 0){// 两个交点相等,只需要判断一个就好return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1);}else{// 两个交点不相等,分别进行判断,只要其中一个是线段和圆弧的交点就返回 truereturn lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1) || lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x2, y2);}}return false;
}

五、效果展示

有了判断一条线段和一段圆弧是否相交的函数之后,就可以用来判断圆弧是否和一个多边形相交了。最简单的思路就是用圆弧和多边形的每个边依次做判断,如果多边形的任意一条边和圆弧都不相交,则圆弧与多边形必然不相交。

交叉判断前,从下图可以看到,黄色部分就是圆弧和多边形出现了交叉重叠的情况

在这里插入图片描述

交叉判断后,圆弧与多边形的交叉情况完全消失~

在这里插入图片描述


http://www.ppmy.cn/news/58044.html

相关文章

MySQL库和表

MySQL库操作 创建数据库 语法 CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [,create_specification] ...] create_specification: [DEFAULT] CHARACTER SET charset_name [DEFAULT] COLLATE collation_name说明: 大写的表示关键字[ ]是可选项CHARACTER…

win10远程桌面控制Ubuntu服务器 - 内网穿透实现公网远程

文章目录 前言视频教程1. ubuntu安装XRDP2.局域网测试连接3. Ubuntu安装cpolar内网穿透4.cpolar公网地址测试访问5.固定域名公网地址 转载自远程穿透文章&#xff1a;Windows通过RDP异地远程桌面Ubuntu【内网穿透】 前言 XRDP是一种开源工具&#xff0c;它允许用户通过Windows…

linux下安装mysql-8.0.30超级详细

一、下载方式一: MySQL :: Download MySQL Community Server 或者到我的百度网盘中下载---- 链接&#xff1a;https://pan.baidu.com/s/1hZvfZw4S4TqF7XOFu_2ekg?pwdziuu 提取码&#xff1a;ziuu --来自百度网盘超级会员V6的分享 下载方式2---或者使用 -- wget 命令下…

Android9.0 系统Framework发送通知流程分析

1.前言 在android 9.0的系统rom定制化开发中,在systemui中一个重要的内容就是系统通知的展示,在状态栏展示系统发送通知的图标,而在 系统下拉通知栏中展示接收到的系统发送过来的通知,所以说对系统framework中发送通知的流程分析很重要,接下来就来分析下系统 通知从frame…

黑客如何在攻击中使用生成式人工智能以及我们能做些什么?

生成式人工智能 (AI) 最近备受关注。AI 驱动的聊天机器人 ChatGPT 和 VALL-E 等其他支持自然语言处理的系统已将生成 AI 带给了公众&#xff0c;并释放了它的好处和坏处。 关于生成式 AI 的核心担忧之一是它可用于升级恶意攻击并提出更复杂的网络攻击。 那么&#xff0c;黑客…

Ae:画笔工具

画笔工具 Brush Tool 快捷键&#xff1a;Ctrl B 画笔工具 Brush Tool仅能工作在图层 Layer面板上。 双击纯色图层、像素图层等可打开图层面板。 在 Ae 中的每次画笔绘制都将新建一条路径&#xff0c;然后通过对路径的描边来显示绘制结果&#xff0c;故又称为“绘画描边”或“…

4.30学习周报

文章目录 前言文献阅读摘要简介数据源和预处理理论基础与模型构建结果和讨论结论和未来工作 时间序列预测总结 前言 本周阅读文献《Water Quality Prediction Based on LSTM and Attention Mechanism: A Case Study of the Burnett River, Australia》&#xff0c;文献主要提出…

SPSS如何进行均值比较和T检验之案例实训?

文章目录 0.引言1.均值过程2.单样本T检验3.独立样本T检验4.成对样本T检验 0.引言 因科研等多场景需要进行绘图处理&#xff0c;笔者对SPSS进行了学习&#xff0c;本文通过《SPSS统计分析从入门到精通》及其配套素材结合网上相关资料进行学习笔记总结&#xff0c;本文对均值比较…