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

这篇具有很好参考价值的文章主要介绍了【计算几何】判断一条线段和一段圆弧是否相交 & C++代码实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、前言

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

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

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$

根据线段的两个点（假设为 $p_1$ 和 $p_2$ ，且 $p_1.x\le p_2.x$ ）信息，我们可以很轻易求出 $k$ 和 $c$ 的取值

将 $p_1$ 和 $p_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}$

$(1) - (2)$ 可得：

$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)$

将 $(3)$ 代入 $(1)$ 可得：

$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)$

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

$(x-a)^2+(y-b)^2=r^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \left( 5 \right)$

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

$\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)$

根据韦达定理判断一元二次方程 $(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}$

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

如果式 $(6)$ 存在实数根，则可以解出直线与圆的两个交点的 $X$ 方向坐标 $x_1$ 和 $x_2$ ：

$x_1=\frac{-(2kd-2a)+\sqrt{\varDelta}}{2(1+k^2)} \ 和 \ x_2=\frac{-(2kd-2a)-\sqrt{\varDelta}}{2(1+k^2)}$

将 $x_1$ 和 $x_2$ 分别代入直线方程 $y = k x + c$ 可得两个交点的 $Y$ 方向坐标 $y_1$ 和 $y_2$ ：

$y_1=kx_1+c \ 和\ y_2=kx_2+c$

需要注意的是：上面我们令直线方程为 $y = k x + c$ ，但当直线垂直时， $k$ 其实是不存在的，上面的公式也就不再适用了。幸运的是，在这种情况下，直线方程会变得更加简单，即 $x = c$ ， $c$ 为一个常数。要求这个直线与圆的交点，只需要将 $x = c$ 代入圆的方程中即可，如下所示：
$\begin{cases} x=c \\ (x-a)^2+(y-b)^2=r^2 \\ \end{cases} \\ \Downarrow \\ (c-a)^2+(y-b)^2=r^2\\ \Downarrow \\ (y-b)^2 = r^2 - (c-a)^2\\$
显然，当且仅当 $r^2 - (c-a)^2\ge0$ 时，直线与圆存在交点，且交点的横坐标相同，即 $x_1=x_2=c$ ；纵坐标分别为：
$y_1=b+\sqrt{r^2 - (c-a)^2} \ 和\ y_2=b-\sqrt{r^2 - (c-a)^2}$

如果直线和圆存在交点，则进行下一步判断

3.2 第二步

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

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

详细地说，我们已经知道线段的X轴方向的区间为 $p_1.x\ ,\ p_2.x]$

如果 $x_1$ 不在 $p_1.x\ ,\ p_2.x]$ 区间内，则点 $x_1,y_1)$ 不在线段上，也就不可能是线段和圆弧的交点

同理，如果 $x_2$ 不在 $p_1.x\ ,\ p_2.x]$ 区间内，则点 $x_2,y_2)$ 也不可能是线段和圆弧的交点

如果点 $x_1,y_1)$ 和点 $x_2,y_2)$ 都不是线段和圆弧的交点，则说明线段和圆弧必然不相交

否则进行下一步判断

3.3 第三步

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

在这一步中，需要使用圆的参数方程，为了方便表示，假设圆弧的起始角度和终止角度分别为 $\theta_1$ 和 $\theta_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_1,y_1)$ 代入式 $(7)$ 和式 $(8)$ 中：

$\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$

$(10)$ ➗ $(9)$ 可得：

$\frac{y_1-b}{x_1-a}=tan\theta \\ \Downarrow \\ \theta = arctan(\frac{y_1-b}{x_1-a})$

如果解出的 $\theta$ 不在区间 $[\theta_1,\theta_2]$ 内，则说明点 $x_1,y_1)$ 不在圆弧上

否则，点 $x_1,y_1)$ 在圆弧上，并且是线段和圆弧的一个交点

至此，证毕！

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

四、完整代码

// 圆周率
#define PI acos(-1)

// lineIsIntersectArc 的辅助函数：接着第二步判断（这个函数可能存在浮点数误差问题，导致判断结果有偏差）
bool lineIsIntersectArcAuxiliaryFunction(const DL_VertexData& p1, const DL_VertexData& 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)
		double theta = atan((y1 - b) / (x1 - a)) * 180.0 / PI;
		if (theta1 > theta2) {
			if (theta2 >= 0) {
				theta1 -= 360;
			}
			else {
				theta2 += 360;
			}
		}
		if (theta1 < 0 && theta2 < 0) {
			theta1 += 360;
			theta2 += 360;
		}
		// 修正 tan 的角度
		if (x1 < a) {
			theta += 180;
		}
		if (theta < 0) {
			theta += 360;
		}
		// 判断是否在边界，在边界其实就不算相交
		if (abs(theta1 - theta) <= 1e-12 || abs(theta2 - theta) <= 1e-12) {
			return false;
		}
		// 判断 theta 是否在圆弧范围内，如果在则(x1,y1)是线段和圆弧的交点，否则不是
		return theta1 < theta && theta < theta2;
	}
	return false;
}

// 判断一个线段是否和圆弧相交
bool lineIsIntersectArc(Point p1, Point p2, Arc arc){
		// 确保 p1.x < p2.x
	if (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;
	// 开始判断
	if (abs(p1.x - p2.x) < 1e-12) {
		// 特殊处理 p1.x = p2.x 的情况
		double c = p1.x;
		double temp = r * r - (c - a) * (c - a);
		if (temp >= -1e-12) {
			// 第二步：判断直线和圆的两个交点是否在线段上，如果不在，说明线段和圆弧必然不相交，否则进行下一步判断
			// 2.1 计算两个交点的坐标(x1,y1)和(x2,y2)
			double x1 = c;
			double x2 = c;
			double y1 = b + sqrt(temp);
			double y2 = b - sqrt(temp);
			// 2.2 判断两个交点是否相等3
			if (abs(y1 - y2) < 1e-12) {
				// 两个交点相等，只需要对其中任意一个点进行判断即可
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1);
			}
			else {
				// 两个交点不相等，分别进行判断，只要其中一个是线段和圆弧的交点就返回 true
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1) || lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x2, y2);
			}
		}
	}
	else {
		// 第一步（粗略判断）：将线段当成直线，将圆弧当成圆，如果直线和圆不相交，则线段和圆弧必然不相交，否则进行下一步判断
		// 1.1 根据公式，计算直线方程 y=kx+c 中的 k 和 c
		double 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 >= -1e-12) {
			// 第二步：判断直线和圆的两个交点是否在线段上，如果不在，说明线段和圆弧必然不相交，否则进行下一步判断
			// 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 < 1e-12) {
				// 两个交点相等，只需要对其中任意一个点进行判断即可
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1);
			}
			else {
				// 两个交点不相等，分别进行判断，只要其中一个是线段和圆弧的交点就返回 true
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1) || lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x2, y2);
			}
		}
	}
	return false;
}