当前位置：首页 > Rust > 正文

Rust线段相交算法详解（从零开始掌握Rust几何计算）

主机测评网
Rust
2025-12-06
111

在计算机图形学、游戏开发和地理信息系统（GIS）中，判断两条线段是否相交是一个基础而重要的问题。使用 Rust 这门内存安全且高性能的系统编程语言来实现线段相交算法，不仅能提升程序效率，还能避免常见的内存错误。本教程将手把手教你用 Rust 实现一个高效可靠的 Rust线段相交算法，即使你是编程小白也能轻松上手！

Rust线段相交算法详解（从零开始掌握Rust几何计算） Rust线段相交算法 Rust几何计算 Rust编程教程线段交叉检测第1张

什么是线段相交？

在二维平面中，一条线段由两个端点定义（例如 A(x₁, y₁) 和 B(x₂, y₂)）。当我们有两条线段 AB 和 CD 时，如果它们在某一点“交叉”或“接触”，我们就说这两条线段相交。

注意：仅仅延长后相交不算！必须是线段本身（包括端点）存在公共点才算相交。

数学原理：方向与叉积

判断线段是否相交通常使用向量叉积（Cross Product）的方法。核心思想是：如果线段 AB 的两个端点分别位于线段 CD 的两侧，且线段 CD 的两个端点也分别位于线段 AB 的两侧，那么这两条线段就相交。

我们通过计算三个点构成的“方向”来判断相对位置。给定三点 P、Q、R，我们可以计算向量 PQ × PR 的叉积：

direction(P, Q, R) = (Q.x - P.x) * (R.y - P.y) - (Q.y - P.y) * (R.x - P.x)

若结果 > 0：R 在 PQ 的左侧（逆时针方向）
若结果 < 0：R 在 PQ 的右侧（顺时针方向）
若结果 = 0：三点共线

Rust 实现步骤

现在，让我们用 Rust 编写完整的线段相交检测函数。我们将涵盖所有边界情况，包括共线、端点重合等。

1. 定义点结构体

#[derive(Debug, Clone, Copy)]struct Point {    x: f64,    y: f64,}

2. 计算方向函数

fn direction(p: Point, q: Point, r: Point) -> f64 {    (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)}

3. 判断点是否在线段上（用于共线情况）

fn on_segment(p: Point, q: Point, r: Point) -> bool {    q.x <= f64::max(p.x, r.x) &&    q.x >= f64::min(p.x, r.x) &&    q.y <= f64::max(p.y, r.y) &&    q.y >= f64::min(p.y, r.y)}

4. 主函数：判断两条线段是否相交

fn segments_intersect(a: Point, b: Point, c: Point, d: Point) -> bool {    let d1 = direction(c, d, a);    let d2 = direction(c, d, b);    let d3 = direction(a, b, c);    let d4 = direction(a, b, d);    // 一般情况：四个方向符号相反    if ((d1 > 0.0) != (d2 > 0.0)) && ((d3 > 0.0) != (d4 > 0.0)) {        return true;    }    // 特殊情况：共线且点在线段上    if d1 == 0.0 && on_segment(c, a, d) { return true; }    if d2 == 0.0 && on_segment(c, b, d) { return true; }    if d3 == 0.0 && on_segment(a, c, b) { return true; }    if d4 == 0.0 && on_segment(a, d, b) { return true; }    false}

5. 测试示例

fn main() {    let p1 = Point { x: 0.0, y: 0.0 };    let p2 = Point { x: 2.0, y: 2.0 };    let p3 = Point { x: 0.0, y: 2.0 };    let p4 = Point { x: 2.0, y: 0.0 };    println!("线段相交吗？{}", segments_intersect(p1, p2, p3, p4)); // 输出 true}