一、前言

最近做項(xiàng)目，需要判斷一條線段是否和一段圓弧相交，網(wǎng)上也沒找到很好的解答（最主要是沒有直接可以搬來用的代碼，或者思路寫得太過高深，我看不懂），于是決定自己想一個(gè)方法，寫一個(gè)博客，將實(shí)現(xiàn)思路和完整代碼都分享出來

二、線段與圓弧的代碼表示

2.1 線段代碼表示

線段可用兩個(gè)點(diǎn)表示，點(diǎn)的對象如下所示，包含x和y坐標(biāo)信息：

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

2.2 圓弧代碼表示

圓弧由圓心坐標(biāo)、半徑、起始和終止角度組成：

class Arc
{
public:
	Point centerpoint; // 圓心
	double radius; // 圓弧半徑
	double bangle; // 起點(diǎn)角度
	double eangle; // 終點(diǎn)角度
};

三、實(shí)現(xiàn)思路及數(shù)學(xué)推導(dǎo)

3.1 第一步（粗略判斷）

第一步（粗略判斷）：將線段當(dāng)成直線，將圓弧當(dāng)成圓，如果直線和圓不相交，則線段和圓弧必然不相交，否則進(jìn)行下一步判斷

首先，將線段擴(kuò)展成一條直線，它的方程為：$y=kx+c$

根據(jù)線段的兩個(gè)點(diǎn)（假設(shè)為 $p_1$ 和 $p_2$，且 $p_1.x\le p_2.x$）信息，我們可以很輕易求出 $k$ 和 $c$ 的取值

將$p_1$ 和 $p_2$ 代入直線方程：

$$\{\begin{array}{l}{p}_1.y=k{p}_1.x+c\left(1\right)\\ p_2.y=k{p}_2.x+c\left(2\right)\end{array}$$

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

$$\begin{gathered} p_1.y?p_2.y=\left(p_1.x?p_2.x\right)k \\ ?k=\frac{p_1.y?p_2.y}{p_1.x?p_2.x}\left(3\right) \end{gathered}$$

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

$$\begin{gathered} p_1.y=\frac{p_1.y?p_2.y}{p_1.x?p_2.x}{p}_1.x+c \\ ?c=p_1.y?\frac{p_1.y?p_2.y}{p_1.x?p_2.x}{p}_1.x\left(4\right) \end{gathered}$$

假設(shè)圓心坐標(biāo)為 $(a,b)$ ，半徑為 $r$ ，容易寫出圓弧擴(kuò)展而成的圓的方程如下所示：

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

要判斷直線和圓是否相交，需要將直線方程和圓方程進(jìn)行聯(lián)立得：

$$\begin{gathered} \{\begin{array}{l}y=kx+c\\ (x?a{)}^2+(y?b{)}^2=r^2\end{array} \\ ? \\ (x?a{)}^2+(kx+c?b{)}^2=r^2,令d=c?b \\ ? \\ {x}^2+a^2?2ax+k^2{x}^2+d^2+2kdx=r^2 \\ ? \\ (1+k^2)x^2+(2kd?2a)x+a^2+d^2?r^2=0\left(6\right) \end{gathered}$$

根據(jù)韋達(dá)定理判斷一元二次方程 $(6)$ 是否存在實(shí)數(shù)根：

$$\Delta =(2kd?2a{)}^2?4(1+k^2)(a^2+d^2?r^2)?\{\begin{array}{l}\Delta <0:式(6)不存在實(shí)數(shù)根\\ \Delta \ge 0:式(6)存在實(shí)數(shù)根\end{array}$$

如果式 $(6)$ 不存在實(shí)數(shù)根，意味著直線和圓沒有交點(diǎn)，此時(shí)線段和圓弧必然也沒有交點(diǎn)，程序結(jié)束。

如果式 $(6)$ 存在實(shí)數(shù)根，則可以解出直線與圓的兩個(gè)交點(diǎn)的 $X$ 方向坐標(biāo) $x_1$ 和 $x_2$：

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

將 $x_1$ 和 $x_2$ 分別代入直線方程 $y=kx+c$ 可得兩個(gè)交點(diǎn)的 $Y$ 方向坐標(biāo) $y_1$ 和 $y_2$：

$$y_1=k{x}_1+c和y_2=k{x}_2+c$$

需要注意的是：上面我們令直線方程為 $y=kx+c$，但當(dāng)直線垂直時(shí)，$k$ 其實(shí)是不存在的，上面的公式也就不再適用了。幸運(yùn)的是，在這種情況下，直線方程會(huì)變得更加簡單，即 $x=c$，$c$ 為一個(gè)常數(shù)。要求這個(gè)直線與圓的交點(diǎn)，只需要將 $x=c$ 代入圓的方程中即可，如下所示：
$$\begin{gathered} \{\begin{array}{l}x=c\\ (x?a{)}^2+(y?b{)}^2=r^2\end{array} \\ ? \\ (c?a{)}^2+(y?b{)}^2=r^2 \\ ? \\ (y?b{)}^2=r^2?(c?a{)}^2 \end{gathered}$$
顯然，當(dāng)且僅當(dāng) $r^2?(c?a{)}^2\ge 0$ 時(shí)，直線與圓存在交點(diǎn)，且交點(diǎn)的橫坐標(biāo)相同，即 $x_1=x_2=c$；縱坐標(biāo)分別為：
$$y_1=b+\sqrt{r^2?(c?a{)}^2}和y_2=b?\sqrt{r^2?(c?a{)}^2}$$

如果直線和圓存在交點(diǎn)，則進(jìn)行下一步判斷

3.2 第二步

第二步：判斷直線和圓的兩個(gè)交點(diǎn)是否在線段上，如果不在，說明線段和圓弧必然不相交，否則進(jìn)行下一步判斷

線段是連續(xù)的，所以可以通過區(qū)間判斷兩個(gè)交點(diǎn)是否在線段上

詳細(xì)地說，我們已經(jīng)知道線段的X軸方向的區(qū)間為 $[p_1.x,p_2.x]$

如果 $x_1$ 不在 $[p_1.x,p_2.x]$ 區(qū)間內(nèi)，則點(diǎn) $(x_1,y_1)$ 不在線段上，也就不可能是線段和圓弧的交點(diǎn)

同理，如果 $x_2$ 不在 $[p_1.x,p_2.x]$ 區(qū)間內(nèi)，則點(diǎn) $(x_2,y_2)$ 也不可能是線段和圓弧的交點(diǎn)

如果點(diǎn) $(x_1,y_1)$ 和點(diǎn) $(x_2,y_2)$ 都不是線段和圓弧的交點(diǎn)，則說明線段和圓弧必然不相交

否則進(jìn)行下一步判斷

3.3 第三步

第三步：根據(jù)前面的推導(dǎo)，假設(shè)已知直線和圓的一個(gè)在線段上的交點(diǎn)為 $(x_1,y_1)$，在這一步中，需要判斷該點(diǎn)是否在圓弧上，如果在，則說明線段和圓弧相交，且交點(diǎn)為 $(x_1,y_1)$

在這一步中，需要使用圓的參數(shù)方程，為了方便表示，假設(shè)圓弧的起始角度和終止角度分別為 ${\theta }_1$ 和 ${\theta }_2$，則圓弧的參數(shù)方程為：

$$\{\begin{array}{l}x=a+rcos\theta \left(7\right)\\ y=b+rsin\theta \left(8\right)\end{array},{\theta }_1\le \theta \le {\theta }_2$$

將 $(x_1,y_1)$ 代入式 $(7)$ 和式 $(8)$ 中：

$$\begin{gathered} \{\begin{array}{l}{x}_1=a+rcos\theta \\ y_1=b+rsin\theta \end{array},{\theta }_1\le \theta \le {\theta }_2 \\ ? \\ \{\begin{array}{l}{x}_1?a=rcos\theta \left(9\right)\\ y_1?b=rsin\theta \left(10\right)\end{array},{\theta }_1\le \theta \le {\theta }_2 \end{gathered}$$

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

$$\begin{gathered} \frac{y_1?b}{x_1?a}=tan\theta \\ ? \\ \theta =arctan(\frac{y_1?b}{x_1?a}) \end{gathered}$$

如果解出的 $\theta$ 不在區(qū)間 $[{\theta }_1,{\theta }_2]$ 內(nèi)，則說明點(diǎn) $(x_1,y_1)$ 不在圓弧上

否則，點(diǎn) $(x_1,y_1)$ 在圓弧上，并且是線段和圓弧的一個(gè)交點(diǎn)

至此，證畢！

注意：使用 $atan$ 函數(shù)計(jì)算反正切值時(shí)，返回值的取值范圍是 $[?\frac{\pi }{2},\frac{\pi }{2}]$，而 $\theta$ 的取值是 $[0,2\pi ]$，所以在實(shí)際代碼中需要對角度進(jìn)行轉(zhuǎn)換

四、完整代碼

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

// lineIsIntersectArc 的輔助函數(shù)：接著第二步判斷（這個(gè)函數(shù)可能存在浮點(diǎn)數(shù)誤差問題，導(dǎo)致判斷結(jié)果有偏差）
bool lineIsIntersectArcAuxiliaryFunction(const DL_VertexData& p1, const DL_VertexData& p2, double a, double b, double theta1, double theta2, double x1, double y1) {
	// 2.3 判斷交點(diǎn)是否在線段上
	if (p1.x <= x1 && x1 <= p2.x) {
		// 第三步：交點(diǎn)(x1,y1)在線段上，再判斷該點(diǎn)是否在圓弧上，如果在，則說明線段和圓弧相交，且交點(diǎn)為(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;
		}
		// 判斷是否在邊界，在邊界其實(shí)就不算相交
		if (abs(theta1 - theta) <= 1e-12 || abs(theta2 - theta) <= 1e-12) {
			return false;
		}
		// 判斷 theta 是否在圓弧范圍內(nèi)，如果在則(x1,y1)是線段和圓弧的交點(diǎn)，否則不是
		return theta1 < theta && theta < theta2;
	}
	return false;
}

// 判斷一個(gè)線段是否和圓弧相交
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;
	}
	// 簡化圓弧的相關(guān)變量表示
	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) {
			// 第二步：判斷直線和圓的兩個(gè)交點(diǎn)是否在線段上，如果不在，說明線段和圓弧必然不相交，否則進(jìn)行下一步判斷
			// 2.1 計(jì)算兩個(gè)交點(diǎn)的坐標(biāo)(x1,y1)和(x2,y2)
			double x1 = c;
			double x2 = c;
			double y1 = b + sqrt(temp);
			double y2 = b - sqrt(temp);
			// 2.2 判斷兩個(gè)交點(diǎn)是否相等3
			if (abs(y1 - y2) < 1e-12) {
				// 兩個(gè)交點(diǎn)相等，只需要對其中任意一個(gè)點(diǎn)進(jìn)行判斷即可
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1);
			}
			else {
				// 兩個(gè)交點(diǎn)不相等，分別進(jìn)行判斷，只要其中一個(gè)是線段和圓弧的交點(diǎn)就返回 true
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1) || lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x2, y2);
			}
		}
	}
	else {
		// 第一步（粗略判斷）：將線段當(dāng)成直線，將圓弧當(dāng)成圓，如果直線和圓不相交，則線段和圓弧必然不相交，否則進(jìn)行下一步判斷
		// 1.1 根據(jù)公式，計(jì)算直線方程 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 根據(jù)韋達(dá)定理判斷式（6）是否存在實(shí)數(shù)根
		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) {
			// 第二步：判斷直線和圓的兩個(gè)交點(diǎn)是否在線段上，如果不在，說明線段和圓弧必然不相交，否則進(jìn)行下一步判斷
			// 2.1 計(jì)算兩個(gè)交點(diǎn)的坐標(biāo)(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 判斷兩個(gè)交點(diǎn)是否相等
			if (varDelta < 1e-12) {
				// 兩個(gè)交點(diǎn)相等，只需要對其中任意一個(gè)點(diǎn)進(jìn)行判斷即可
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1);
			}
			else {
				// 兩個(gè)交點(diǎn)不相等，分別進(jìn)行判斷，只要其中一個(gè)是線段和圓弧的交點(diǎn)就返回 true
				return lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x1, y1) || lineIsIntersectArcAuxiliaryFunction(p1, p2, a, b, theta1, theta2, x2, y2);
			}
		}
	}
	return false;
}

五、效果展示

有了判斷一條線段和一段圓弧是否相交的函數(shù)之后，就可以用來判斷圓弧是否和一個(gè)多邊形相交了。最簡單的思路就是用圓弧和多邊形的每個(gè)邊依次做判斷，如果多邊形的任意一條邊和圓弧都不相交，則圓弧與多邊形必然不相交。

交叉判斷前，從下圖可以看到，黃色部分就是圓弧和多邊形出現(xiàn)了交叉重疊的情況

交叉判斷后，圓弧與多邊形的交叉情況完全消失~

文章來源地址http://www.zghlxwxcb.cn/news/detail-429840.html

到了這里，關(guān)于【計(jì)算幾何】判斷一條線段和一段圓弧是否相交 & C++代碼實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！