计算机图形学：线段的交点计算及代码实现
文章目录
原理推导过程
代码实现Python代码C++代码应用示例
在计算机图形学、几何计算和工程领域中，经常需要计算两条线段的交点。本文将详细介绍线段交点计算的原理、公式推导过程以及代码实现。
原理
要计算两条线段的交点，我们首先需要确定这两条线段是否相交。线段可以由两个端点定义，设线段
A
B
AB
AB的端点为
A
(
x
1
,
y
1
)
A(x_1, y_1)
A(x1,y1)和
B
(
x
2
,
y
2
)
B(x_2, y_2)
B(x2,y2)，线段
C
D
CD
CD的端点为
C
(
x
3
,
y
3
)
C(x_3, y_3)
C(x3,y3)和
D
(
x
4
,
y
4
)
D(x_4, y_4)
D(x4,y4)。
推导过程
确定线段的方程：线段(AB)和(CD)可以表示为参数方程：
A
B
:
{
x
=
x
1
+
t
(
x
2
−
x
1
)
y
=
y
1
+
t
(
y
2
−
y
1
)
(
0
≤
t
≤
1
)
AB: \begin{cases} x = x_1 + t(x_2 - x_1) \\ y = y_1 + t(y_2 - y_1) \end{cases} \quad (0 \leq t \leq 1)
AB:{x=x1+t(x2−x1)y=y1+t(y2−y1)(0≤t≤1)
C
D
:
{
x
=
x
3
+
s
(
x
4
−
x
3
)
y
=
y
3
+
s
(
y
4
−
y
3
)
(
0
≤
s
≤
1
)
CD: \begin{cases} x = x_3 + s(x_4 - x_3) \\ y = y_3 + s(y_4 - y_3) \end{cases} \quad (0 \leq s \leq 1)
CD:{x=x3+s(x4−x3)y=y3+s(y4−y3)(0≤s≤1)
设置交点条件：如果线段相交，那么存在
t
t
t和
s
s
s使得：
x
1
+
t
(
x
2
−
x
1
)
=
x
3
+
s
(
x
4
−
x
3
)
x_1 + t(x_2 - x_1) = x_3 + s(x_4 - x_3)
x1+t(x2−x1)=x3+s(x4−x3)
y
1
+
t
(
y
2
−
y
1
)
=
y
3
+
s
(
y
4
−
y
3
)
y_1 + t(y_2 - y_1) = y_3 + s(y_4 - y_3)
y1+t(y2−y1)=y3+s(y4−y3)
解方程组：解这个方程组得到
t
t
t和
s
s
s。
t
=
(
x
3
−
x
1
)
(
y
4
−
y
3
)
−
(
y
3
−
y
1
)
(
x
4
−
x
3
)
(
x
2
−
x
1
)
(
y
4
−
y
3
)
−
(
y
2
−
y
1
)
(
x
4
−
x
3
)
t = \frac{(x3 - x1)(y4 - y3) - (y3 - y1)(x4 - x3)}{(x2 - x1)(y4 - y3) - (y2 - y1)(x4 - x3)}
t=(x2−x1)(y4−y3)−(y2−y1)(x4−x3)(x3−x1)(y4−y3)−(y3−y1)(x4−x3)
s
=
(
x
3
−
x
1
)
(
y
2
−
y
1
)
−
(
y
3
−
y
1
)
(
x
2
−
x
1
)
(
x
2
−
x
1
)
(
y
4
−
y
3
)
−
(
y
2
−
y
1
)
(
x
4
−
x
3
)
s = \frac{(x3 - x1)(y2 - y1) - (y3 - y1)(x2 - x1)}{(x2 - x1)(y4 - y3) - (y2 - y1)(x4 - x3)}
s=(x2−x1)(y4−y3)−(y2−y1)(x4−x3)(x3−x1)(y2−y1)−(y3−y1)(x2−x1) 如果
t
t
t和
s
s
s都在
[
0
,
1
]
[0, 1]
[0,1]区间内，那么线段相交。
计算交点：交点的坐标为：
P
(
x
1
+
t
(
x
2
−
x
1
)
,
y
1
+
t
(
y
2
−
y
1
)
)
P\left(x_1 + t(x_2 - x_1), y_1 + t(y_2 - y_1)\right)
P(x1+t(x2−x1),y1+t(y2−y1))
代码实现
Python代码
def line_intersection(A, B, C, D):
x1, y1 = A
x2, y2 = B
x3, y3 = C
x4, y4 = D
# 计算分母
denominator = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)
if denominator == 0:
return None # 线段平行或重合
# 计算t和s
t = ((x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3)) / denominator
s = ((x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1)) / denominator
# 检查t和s是否在[0, 1]区间内
if 0 <= t <= 1 and 0 <= s <= 1:
return (x1 + t * (x2 - x1), y1 + t * (y2 - y1))
else:
return None # 线段不相交
C++代码
#include
struct Point {
double x, y;
};
Point line_intersection(Point A, Point B, Point C, Point D) {
double x1 = A.x, y1 = A.y;
double x2 = B.x, y2 = B.y;
double x3 = C.x, y3 = C.y;
double x4 = D.x, y4 = D.y;
// 计算分母
double denominator = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);
if (denominator == 0) {
return {0, 0}; // 线段平行或重合
}
// 计算t和s
double t = ((x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3)) / denominator;
double s = ((x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1)) / denominator;
// 检查t和s是否在[0, 1]区间内
if (0 <= t && t <= 1 && 0 <= s && s <= 1) {
return {x1 + t * (x2 - x1), y1 + t * (y2 - y1)};
} else {
return {0, 0}; // 线段不相交
}
}
应用示例
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.animation import FuncAnimation
def line_intersection(A, B, C, D):
x1, y1 = A
x2, y2 = B
x3, y3 = C
x4, y4 = D
# 计算分母
denominator = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)
if denominator == 0:
return None # 线段平行或重合
# 计算t和s
t = ((x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3)) / denominator
s = ((x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1)) / denominator
# 检查t和s是否在[0, 1]区间内
if 0 <= t <= 1 and 0 <= s <= 1:
return (x1 + t * (x2 - x1), y1 + t * (y2 - y1))
else:
return None # 线段不相交
# 手动定义线段
segments = [
((0.3, 0.3), (0.8, 0.8), (0.2, 0.8), (0.8, 0.2)),
((0.2, 0.2), (0.8, 0.2), (0.5, 0.5), (0.8, 0.5)),
((0.1, 0.1), (0.7, 0.7), (0.6, 0.22), (0.8, 0.2)),
((0.3, 0.3), (0.7, 0.7), (0.4, 0.84), (0.8, 0.2)),
((0.2, 0.5), (0.8, 0.4), (0.6, 0.8), (0.7, 0.2)),
((0.2, 0.3), (0.8, 0.8), (0.5, 0.2), (0.8, 0.2))
]
fig, ax = plt.subplots()
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
ax.set_aspect('equal')
# 初始化绘图
line1, = ax.plot([], [], 'b-', animated=True)
line2, = ax.plot([], [], 'b-', animated=True)
point, = ax.plot([], [], 'ro', animated=True)
text = ax.text(0.5, 0.9, '', transform=ax.transAxes, ha='center')
def init():
line1.set_data([], [])
line2.set_data([], [])
point.set_data([], [])
text.set_text('')
return line1, line2, point, text
def animate(i):
A, B, C, D = segments[i]
intersection = line_intersection(A, B, C, D)
line1.set_data([A[0], B[0]], [A[1], B[1]])
line2.set_data([C[0], D[0]], [C[1], D[1]])
if intersection:
line1.set_color('r')
line2.set_color('r')
point.set_data([intersection[0]], [intersection[1]])
text.set_text(f'Intersection: ({intersection[0]:.2f}, {intersection[1]:.2f})')
else:
line1.set_color('b')
line2.set_color('b')
point.set_data([], []) # 修改这里
text.set_text('No Intersection')
return line1, line2, point, text
ani = FuncAnimation(fig, animate, init_func=init, frames=len(segments), interval=500, blit=True)
# 保存动图
ani.save('line_segments.gif', writer='pillow', fps=1)
plt.show()
运行效果如下