Java实现线段相交判断（从零开始的计算几何入门教程）

核心思路：方向向量与叉积

判断线段相交通常使用计算几何中的“方向法”（Orientation Method），其核心是利用向量叉积来判断点的相对位置。

对于三个点 p、q、r，我们可以定义一个函数 orientation(p, q, r)，它返回：

• 0：三点共线
• 1：顺时针方向（右转）
• 2：逆时针方向（左转）

步骤详解

要判断线段 AB 和 CD 是否相交，需满足以下两个条件之一：

1. (a) 一般情况：A、B 在 CD 的两侧，且 C、D 在 AB 的两侧。
2. (b) 特殊情况：至少有一个端点落在另一条线段上（如共线且重叠）。

Java代码实现

下面是一个完整的 Java 类，用于判断两条线段是否相交：

public class LineSegmentIntersection {    // 定义点类    static class Point {        double x, y;        Point(double x, double y) {            this.x = x;            this.y = y;        }    }    // 计算三点的方向    public static int orientation(Point p, Point q, Point r) {        double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);        if (val == 0) return 0; // 共线        return (val > 0) ? 1 : 2; // 1: 顺时针, 2: 逆时针    }    // 检查点 q 是否在线段 pr 上（仅当三点共线时调用）    public static boolean onSegment(Point p, Point q, Point r) {        return q.x <= Math.max(p.x, r.x) &&               q.x >= Math.min(p.x, r.x) &&               q.y <= Math.max(p.y, r.y) &&               q.y >= Math.min(p.y, r.y);    }    // 判断线段 p1q1 和 p2q2 是否相交    public static boolean doIntersect(Point p1, Point q1, Point p2, Point q2) {        int o1 = orientation(p1, q1, p2);        int o2 = orientation(p1, q1, q2);        int o3 = orientation(p2, q2, p1);        int o4 = orientation(p2, q2, q1);        // 一般情况        if (o1 != o2 && o3 != o4)            return true;        // 特殊情况：共线且重叠        if (o1 == 0 && onSegment(p1, p2, q1)) return true;        if (o2 == 0 && onSegment(p1, q2, q1)) return true;        if (o3 == 0 && onSegment(p2, p1, q2)) return true;        if (o4 == 0 && onSegment(p2, q1, q2)) return true;        return false;    }    // 测试示例    public static void main(String[] args) {        Point p1 = new Point(1, 1);        Point q1 = new Point(10, 1);        Point p2 = new Point(1, 2);        Point q2 = new Point(10, 2);        if (doIntersect(p1, q1, p2, q2))            System.out.println("线段相交");        else            System.out.println("线段不相交");    }}

代码说明

• orientation() 函数通过叉积判断三点方向。
• onSegment() 用于处理共线时的边界情况。
• doIntersect() 是主逻辑，先判断一般情况，再处理特殊情况。

总结

通过本教程，你已经掌握了在 Java 中实现线段交点判断的基本方法。这是计算几何中的经典问题，理解其原理对后续学习路径规划、碰撞检测等高级主题大有裨益。

动手试试修改点的坐标，观察输出结果吧！实践是掌握Java线段相交判断的最佳方式。