空間直線與球面相交算法

詳細介紹了空間直線與球面相交的C/C++實作。

目錄

• 1. 原理推導
  • 1.1. 直線公式
  • 1.2. 求交
• 2. 具體實作
• 3. 參考

在嚴格的數學定義中，直線是無線延長，沒有端點的線；射線是一端有端點，另外一段沒有端點無線延長的線。但在具體的計算機幾何實作中，不可能去找到這種無線延長，沒有端點的線，是以這裡直線的定義更加近于線段，如果線段選的夠長，那麼這個線段就可以認為是直線或者射線。

空間直線的數學定義是，已知直線L上一點\(M_0(x_0,y_0,c_0)\)，以及直線L的方向向量\(s(m,n,p)\)，那麼空間直線L的方程為：

\[\frac{x-x_0}{m} = \frac{y-y_0}{n} = \frac{z-z_0}{p}

\]

以上是空間直線的标準式方程（點向式方程）。令上面式子的比值為\(t\)，那麼直線的參數式方程為：

\[\begin{cases}

x = x_0 + m * t\\

y = y_0 + n * t\\

z = z_0 + p * t\\

\end{cases}

這兩個方程是無法直接在實際情況中使用的，畢竟很多時候都是直接給出經過直線的兩個點。我在《已知線段上某點與起點的距離，求該點的坐标》這篇博文中論述過:

對于知道線段的起點\(O\)和終點\(E\)，顯然方向向量為\(D=E−O\)。這時，根據射線的向量方程，線段上某一點P為

\[P=O+tD

很明顯，直線的參數式方程與上篇博文中描述的其實是一個意思，起點\(O\)就是\(M_0(x_0,y_0,c_0)\)，方向向量\(D\)就是\(s(m,n,p)\)：

x = O_x + D_x * t\\

y = O_y + D_y * t\\

z = O_z + D_z * t\\

\end{cases} \tag {1}

并且，采取這種公式描述還有個好處，局勢t的取值範圍為0到1，否則就在直線的兩個端點之外，也就很有可能不是你需要的點。

根據數學定義，已知球心坐标\(C(C_x, C_y, C_z)\)與球的半徑R，球面的公式為：

\[(X-C_x)^2 + (Y-C_y)^2 + (Z-C_z)^2 = R^2 \tag{2}

聯立(1)(2)兩式，最終會得到一個關于t的一進制二次方程：

\[(O_x + D_x * t-C_x)^2 + ( O_y + D_y * t-C_y)^2 + (O_z + D_z * t-C_z)^2 = R^2

一進制二次方程組的有無解，單個解，以及雙解三種可能，這也符合空間直線與球面相交的直覺認識，要麼相切有一個交點，要麼相交有兩個交點，否則的話可能沒有交點。

得到\(t\)後，将其帶入到(1)式中，就得到想要的交點。不過注意t的範圍一般是0到1，這是與直線給的起點位置與終點位置有關的。

推到這裡就會發現原來全部都是高中數學知識，應該還做過題目來着。

具體的C++實作如下：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const double EPSILON = 0.0000000001;

// 3D vector
struct Vector3d
{
public:
	Vector3d()
	{
	}

	~Vector3d()
	{
	}

	Vector3d(double dx, double dy, double dz)
	{
		x = dx;
		y = dy;
		z = dz;
	}

	// 矢量指派
	void set(double dx, double dy, double dz)
	{
		x = dx;
		y = dy;
		z = dz;
	}

	// 矢量相加
	Vector3d operator + (const Vector3d& v) const
	{
		return Vector3d(x + v.x, y + v.y, z + v.z);
	}

	// 矢量相減
	Vector3d operator - (const Vector3d& v) const
	{
		return Vector3d(x - v.x, y - v.y, z - v.z);
	}

	//矢量數乘
	Vector3d Scalar(double c) const
	{
		return Vector3d(c*x, c*y, c*z);
	}

	// 矢量點積
	double Dot(const Vector3d& v) const
	{
		return x * v.x + y * v.y + z * v.z;
	}

	// 矢量叉積
	Vector3d Cross(const Vector3d& v) const
	{
		return Vector3d(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
	}

	bool operator == (const Vector3d& v) const
	{
		if (abs(x - v.x) < EPSILON && abs(y - v.y) < EPSILON && abs(z - v.z) < EPSILON)
		{
			return true;
		}
		return false;
	}

	double x, y, z;
};

//求解一進制二次方程組ax*x + b*x + c = 0
void SolvingQuadratics(double a, double b, double c, vector<double>& t)
{
	double delta = b * b - 4 * a * c;
	if (delta < 0)
	{
		return;
	}

	if (abs(delta) < EPSILON)
	{
		t.push_back(-b / (2 * a));
	}
	else
	{
		t.push_back((-b + sqrt(delta)) / (2 * a));
		t.push_back((-b - sqrt(delta)) / (2 * a));
	}
}

void LineIntersectSphere(Vector3d& O, Vector3d& E, Vector3d& Center, double R, vector<Vector3d>& points)
{
	Vector3d D = E - O;			//線段方向向量

	double a = (D.x * D.x) + (D.y * D.y) + (D.z * D.z);
	double b = (2 * D.x * (O.x - Center.x) + 2 * D.y * (O.y - Center.y) + 2 * D.z* (O.z - Center.z));
	double c = ((O.x - Center.x)*(O.x - Center.x) + (O.y - Center.y) * (O.y - Center.y) + (O.z - Center.z) * (O.z - Center.z)) - R * R;

	vector<double> t;
	SolvingQuadratics(a, b, c, t);

	for (auto it : t)
	{	
		if (it >= 0 && it <= 1)
		{
			points.push_back(O + D.Scalar(it));
		}		
	}
}

int main()
{
	Vector3d O(20, 30, 40);
	Vector3d E(20, 20, 20); 
	Vector3d Center(20, 20, 20);
	double R = 15;

	vector<Vector3d> points;
	LineIntersectSphere(O, E, Center, R, points);

	cout<<"該直線(線段)與球面有"<< points.size() <<"個交點"<<endl;
	for (auto it : points)
	{
		printf("%lf\t%lf\t%lf\n", it.x, it.y, it.z);
	}	
}
           

最終運作的結果:

再次注意，我這裡是把線段當成直線判斷的，如果希望判斷整個直線與球面的交點，應該略去最後的關于\(t\)是否在0到1之間的判斷，此時應該會有兩個交點。

1. 空間直線同球體交點求解