平时做技术实践时，很多问题不是概念不会，而是细节没串起来。拿“Java实现方法批量线段相交检测的完整步骤与避坑指南”来说，它看着像小点，放到项目里常会牵出环境、配置、兼容性和维护成本。下面按实际采用顺序，把思路、关键写法和容易踩坑的地方讲清楚，便于大家直接对照操作。
一、问题背景与算法简介
从实现思路看，批量线段相交检测是计算几何中的常用问题：给定平面上 n 条线段，找出其中所有相交的线段对。它在电路布线检查、地图路网冲突检测、CAD 图形碰撞判断、图形编辑器连线校验等场景中都有直接应用。
结合项目来看，最直观的做法是两两枚举，复杂度 O(n²)，实现轻松但线段数量一大就不可接受。更高效的做法是扫描线（Sweep Line）：把所有线段端点按 x 坐标排序，用一条竖直扫描线自左向右扫过，只对"当前横坐标上纵向相邻"的线段做相交判断，从而把需比较的线段对大幅减少。
本文实现了两个版本：朴素两两枚举版本（作为正确性基准）和基于 TreeSet 的扫描线版本，同时内置了一套完整的几何基础工具：用叉积判断线段相交、区分"不相交 / 交于一点 / 部分重叠"三种情况。需特别说明的是，实测发现本文的扫描线版本在包含竖直线段的用例上存在漏检，第八、九节将完整给出定位过程与修复方案。
二、基础几何判定
三个基础函数构成了整个相交判定的地基：
- 实际处理时，cross(a,b,c)：计算向量 ab 与 ac 的叉积，符号表示点 c 在直线 ab 的哪一侧，为0表示共线
- sign(v)：带 EPS=1e-9 容差的符号函数，把叉积结果规整为 -1/0/1，避免浮点误差导致误判
- 在这个场景下，onSegment(a,b,p)：在共线的前提下，判断点 p 是否落在以 a、b 为对角的矩形范围内，即是否真的落在线段上
实际处理时，基于这三个函数，相交判定分两步：先用四个叉积判断两条线段是否"跨立"（互相在对方直线两侧），这是规范相交；若不满足跨立，则逐条检查四个端点是否落在对方线段上，用来覆盖共线重叠、端点相触等退化情况。结果用 Result 类表达，分为 NONE（不相交）、POINT（交于一点）、OVERLAP（共线重叠，得到重叠段的两个端点）三种类型。
三、两种批量检测方案
3.1 朴素两两枚举
allPairsNaive 对所有 i 在这个场景下，allPairsSweep 为每条线段生成左、右两个端点事件，按 x 排序后依次处理。用 TreeSet 维护当前处于扫描线位置的所有线段，比较器按"该线段在当前 x 处的 y 值"排序。插入新线段时，只与它的左右邻居判交；删除线段时，只检查因它移除而新成为邻居的那一对。这一思路来自 Bentley-Ottmann 算法的简化版，理想情况下能把比较量降到接近 O((n+k)log n)。 结合项目来看，SegmentIntersectBatch 类分为五层：Geometry 提供点、叉积、容差符号与在线段判断；Result 表达三种相交结果；intersect 是单对线段的完整判定与求交；Seg 是批量场景的线段对象，构造时统一把端点调整为左小右大，同时提供 minX、maxX、yAt 三个辅助方法；allPairsNaive 与 allPairsSweep 分别实现两种批量策略；main 用 5 条线段做对比测试并打印耗时。 在这个场景下，Point 用 final 的 x、y 保存坐标，equals 采用 EPS 容差比较而非精确相等，这是几何题的基本功。cross 用 (b-a)×(c-a) 计算叉积，是判断方向的核心；onSegment 用包围盒判定点是否在线段范围内；sign 把带容差的浮点值规整为整数符号。 intersect 先算四个叉积 d1~d4 同时取符号。若 s1*s2<0 且 s3*s4<0，说明两条线段严格跨立，此时用参数方程求交点：把 p1p2 表示为 p1 + t*(p2-p1)，联立解出 t 后回代得到交点坐标。否则收集落在对方线段上的端点，去重后若只有一个唯一交点返回 POINT，若有多个则取距离最远的两点作为重叠段端点返回 OVERLAP。 落到代码里，Seg 在构造时把端点统一成 x 小在前，这样 minX/maxX 与 yAt 的实现都很轻松。yAt(x) 按线性插值算出该线段在横坐标 x 处的 y 值，是扫描线排序的依据；当 x1==x2（竖直线段）时直接得到 y1。basicIntersect 把两个 Seg 拆成四个 Point 后调用 intersect，只关心结果是否为 NONE。 落到代码里，事件用 double[]{x, type, id} 表示，type 为0是左端点（插入）、1是右端点（删除），排序时先按 x、再按 type，保证同一 x 上先插入后删除。TreeSet 的比较器读取外部静态变量 currentX 来比较两条线段当前的 y 值，y 相同时用 id 保证全序。 结合项目来看，插入时用 active.lower(id)、active.higher(id) 取左右邻居，分别判交；删除时先取 lower 与 higher，若两者都存在则判交这一对新邻居，随后把线段移出集合。这正是扫描线"只检查相邻关系"的核心剪枝逻辑。 从实现思路看，main 构造 5 条线段：两条对角线、一条水平线、一条孤立短斜线、一条竖直线，先跑朴素法再跑扫描线法，用 System.nanoTime 分别统计耗时，最后用 format 方法把结果按字符串排序后输出，便于人工比对。 以下是完整的可运行代码，可直接复制编译运行。 在本机 JDK 11 环境实际编译运行，输出如下所示： 结合项目来看，先看几何事实。5 条线段的实际位置是：线段0是从(0,0)到(4,4)的对角线，线段1是从(0,4)到(4,0)的反向对角线，线段2是 y=1 的水平线，线段3是远离图形的孤立，线段4是 x=2 的竖直线。手工推演可知：线段0 与 1 交于(2,2)，线段0 与 2 交于(1,1)，线段1 与 2 交于(3,1)，线段4 依次与 0、1、2 交于(2,2)、(2,2)、(2,1)，线段3 不与任何线段相交。所以正确的相交对共 6 对：(0,1)、(0,2)、(0,4)、(1,2)、(1,4)、(2,4)。 实际处理时，朴素法输出恰好是这 6 对，与手工推演完全一致，可作为正确性基准。而扫描线法只输出了 4 对，漏掉了 (1,4) 与 (2,4)。这说明本文的扫描线实现存在缺陷，不能直接用来含竖直线段的场景。下面的第八节给出完整的定位过程。 理解这一步时，为便于排除"是否是 TreeSet 比较器写错"的可能，先把 TreeSet 换成按当前 x 的 y 值排序的普通 ArrayList，其他逻辑保持"插入查左右邻居、删除查新邻居对"不变，重新实测：插入线段4（竖线）时 yAt 得到 -1，被直接排到 active 最前端，所以只能与紧邻的线段0判交，线段1 与线段2 虽然也与它相交，却因不在相邻位置而被跳过。替换后结果仍只有 4 对，说明问题不在 TreeSet 本身。 综合实测与推演，本实现存在两个层次的问题： 在这个场景下，此外还需指出，即便是修正了上述两点，这个"只查相邻关系"的简化扫描线本身也不是完整的 Bentley-Ottmann：完整算法还需在两条线段真正相交时把它们的顺序交换，同时处理多线段共点等退化情形。简化版只在"任意两条线段最多相交一次、且无竖直退化线段"的假设下才成立。 理解这一步时，针对上述两个根因，修复思路是：用 ArrayList 按当前 x 的 y 值定位插入位置，彻底摆脱比较器依赖可变状态的问题；对竖直线段单独处理，在其 y 区间内与所有仍在 active 中的线段判交，且竖线不进入 active 集合。修复后的扫描线方法如下所示： 从实现思路看，用同一组 5 条线段实测，修复版扫描线输出 6 对，与朴素法逐项比对完全一致，校验借助： 两个版本的复杂度与适用范围对比见下表： 版本 时间复杂度 额外空间 适用场景 朴素两两枚举 O(n²) O(1) 线段数少，或作为校验基准 扫描线（原始） O((n+k)log n) 理想情况 O(n) 无竖直退化线段、无共点的通用场景 扫描线（修复） 近似 O((n+k)log n)，竖线退化为O(n²) O(n) 含少量竖直线段、需可靠结果的场景 实际处理时，需强调的是，原始扫描线在本测试用例上不仅漏检，耗时（1751 μs）还高于朴素法（1417 μs）。这在小规模数据上是正常的：TreeSet 的比较器每次比较都要调用两次 yAt，插入和删除还有红黑树调整开销，常数远大于两两枚举的轻松叉积计算。扫描线的优势要到 n 较大且相交对稀疏时才能体现。 下表汇总了本实现涉及的核心要点： 要点 说明 叉积定向 cross(a,b,c) 的符号表示点c在直线ab的哪一侧 跨立判定 s1*s2<0 且 s3*s4<0 即严格相交，可求精确交点 退化情形 共线重叠、端点相触需用 onSegment 逐一兜底 EPS容差 所有浮点比较必须带1e-9级容差，避免精度误判 交点求解 参数方程 p1+t*(p2-p1) 联立，t回代得坐标 扫描线剪枝 只检查当前x上纵向相邻的线段对 竖线退化坑 yAt恒得到y1导致排序极端化，只查邻居必漏检 比较器一致性 TreeSet比较器不得依赖外部可变状态 若要把它做成可用来生产的几何工具，能够沿以下方向继续完善： 从实现思路看，总的来说，Java批量线段相交检测适合结合实际项目边做边理解。先抓住核心思路，再逐步补上细节和边界处理，最后效果会更稳定，也更容易复用。3.2 扫描线邻接检测
四、代码整体架构
五、核心代码逐段解析
5.1 Geometry 工具与 Point
5.2 Result 与 intersect
5.3 Seg 与 basicIntersect
5.4 事件排序与 TreeSet 维护
5.5 插入与删除时的邻居检查
5.6 main 测试
六、完整源代码
import java.util.*;
public class SegmentIntersectBatch {
// ==================== 1. 内置基础几何工具 ====================
public static class Geometry {
public static final double EPS = 1e-9;
public static class Point {
public final double x, y;
public Point(double x, double y) { this.x = x; this.y = y; }
@Override public String toString() { return String.format("(%.4f, %.4f)", x, y); }
public boolean equals(Point o) {
return Math.abs(x - o.x) < EPS && Math.abs(y - o.y) < EPS;
}
}
public static double cross(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
public static boolean onSegment(Point a, Point b, Point p) {
return Math.min(a.x, b.x) - EPS <= p.x && p.x <= Math.max(a.x, b.x) + EPS
&& Math.min(a.y, b.y) - EPS <= p.y && p.y <= Math.max(a.y, b.y) + EPS;
}
public static int sign(double v) {
if (v > EPS) return 1;
if (v < -EPS) return -1;
return 0;
}
}
// ==================== 2. 内置交点求解结果类 ====================
public static class Result {
public enum Type { NONE, POINT, OVERLAP }
public final Type type;
public final Geometry.Point point;
public final Geometry.Point[] seg;
private Result(Type type, Geometry.Point point, Geometry.Point[] seg) {
this.type = type; this.point = point; this.seg = seg;
}
public static Result none() { return new Result(Type.NONE, null, null); }
public static Result point(Geometry.Point p) { return new Result(Type.POINT, p, null); }
public static Result overlap(Geometry.Point a, Geometry.Point b) { return new Result(Type.OVERLAP, null, new Geometry.Point[]{a, b}); }
}
// ==================== 3. 内置交点算法 ====================
public static Result intersect(Geometry.Point p1, Geometry.Point p2, Geometry.Point p3, Geometry.Point p4) {
double d1 = Geometry.cross(p3, p4, p1);
double d2 = Geometry.cross(p3, p4, p2);
double d3 = Geometry.cross(p1, p2, p3);
double d4 = Geometry.cross(p1, p2, p4);
int s1 = Geometry.sign(d1), s2 = Geometry.sign(d2);
int s3 = Geometry.sign(d3), s4 = Geometry.sign(d4);
if (s1 * s2 < 0 && s3 * s4 < 0) {
double dx1 = p2.x - p1.x, dy1 = p2.y - p1.y;
double dx2 = p4.x - p3.x, dy2 = p4.y - p3.y;
double denom = dx1 * dy2 - dy1 * dx2;
double t = ((p3.x - p1.x) * dy2 - (p3.y - p1.y) * dx2) / denom;
return Result.point(new Geometry.Point(p1.x + t * dx1, p1.y + t * dy1));
}
List<Geometry.Point> contacts = new ArrayList<>();
if (s1 == 0 && Geometry.onSegment(p3, p4, p1)) contacts.add(p1);
if (s2 == 0 && Geometry.onSegment(p3, p4, p2)) contacts.add(p2);
if (s3 == 0 && Geometry.onSegment(p1, p2, p3)) contacts.add(p3);
if (s4 == 0 && Geometry.onSegment(p1, p2, p4)) contacts.add(p4);
if (contacts.isEmpty()) return Result.none();
List<Geometry.Point> uniq = new ArrayList<>();
for (Geometry.Point p : contacts) {
boolean dup = false;
for (Geometry.Point q : uniq) if (p.equals(q)) { dup = true; break; }
if (!dup) uniq.add(p);
}
if (uniq.size() == 1) return Result.point(uniq.get(0));
Geometry.Point a = uniq.get(0), b = uniq.get(1);
double maxDist = dist2(a, b);
for (int i = 0; i < uniq.size(); i++) {
for (int j = i + 1; j < uniq.size(); j++) {
double d = dist2(uniq.get(i), uniq.get(j));
if (d > maxDist) { maxDist = d; a = uniq.get(i); b = uniq.get(j); }
}
}
return Result.overlap(a, b);
}
private static double dist2(Geometry.Point a, Geometry.Point b) {
double dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
private static boolean basicIntersect(Seg a, Seg b) {
Geometry.Point p1 = new Geometry.Point(a.x1, a.y1);
Geometry.Point p2 = new Geometry.Point(a.x2, a.y2);
Geometry.Point p3 = new Geometry.Point(b.x1, b.y1);
Geometry.Point p4 = new Geometry.Point(b.x2, b.y2);
return intersect(p1, p2, p3, p4).type != Result.Type.NONE;
}
// ==================== 4. 批量线段相关类和方法 ====================
public static class Seg {
public final double x1, y1, x2, y2;
public final int id;
public Seg(double x1, double y1, double x2, double y2, int id) {
if (x1 > x2) { this.x1 = x2; this.y1 = y2; this.x2 = x1; this.y2 = y1; }
else { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; }
this.id = id;
}
public double minX() { return Math.min(x1, x2); }
public double maxX() { return Math.max(x1, x2); }
public double yAt(double x) {
if (Math.abs(x2 - x1) < 1e-9) return y1;
return y1 + (y2 - y1) * (x - x1) / (x2 - x1);
}
}
public static List<int[]> allPairsNaive(List<Seg> segs) {
List<int[]> res = new ArrayList<>();
for (int i = 0; i < segs.size(); i++)
for (int j = i + 1; j < segs.size(); j++)
if (basicIntersect(segs.get(i), segs.get(j))) res.add(new int[]{i, j});
return res;
}
private static double currentX = 0;
public static List<int[]> allPairsSweep(List<Seg> segs) {
List<int[]> res = new ArrayList<>();
List<double[]> events = new ArrayList<>();
for (int i = 0; i < segs.size(); i++) {
events.add(new double[]{segs.get(i).minX(), 0, i});
events.add(new double[]{segs.get(i).maxX(), 1, i});
}
events.sort((a, b) -> {
if (Math.abs(a[0] - b[0]) > 1e-9) return Double.compare(a[0], b[0]);
return Double.compare(a[1], b[1]);
});
TreeSet<Integer> active = new TreeSet<>((i1, i2) -> {
double y1 = segs.get(i1).yAt(currentX), y2 = segs.get(i2).yAt(currentX);
if (Math.abs(y1 - y2) > 1e-9) return Double.compare(y1, y2);
return Integer.compare(i1, i2);
});
for (double[] e : events) {
currentX = e[0];
int id = (int) e[2];
Seg s = segs.get(id);
if (e[1] == 0) {
Integer lower = active.lower(id);
Integer higher = active.higher(id);
if (lower != null && basicIntersect(s, segs.get(lower))) res.add(new int[]{id, lower});
if (higher != null && basicIntersect(s, segs.get(higher))) res.add(new int[]{id, higher});
active.add(id);
} else {
Integer lower = active.lower(id);
Integer higher = active.higher(id);
if (lower != null && higher != null && basicIntersect(segs.get(lower), segs.get(higher))) {
res.add(new int[]{lower, higher});
}
active.remove(id);
}
}
return res;
}
// ==================== 5. 测试 Main 方法 ====================
public static void main(String[] args) {
List<Seg> segs = new ArrayList<>();
segs.add(new Seg(0, 0, 4, 4, 0));
segs.add(new Seg(0, 4, 4, 0, 1));
segs.add(new Seg(0, 1, 4, 1, 2));
segs.add(new Seg(5, 0, 6, 1, 3)); // 孤立
segs.add(new Seg(2, -1, 2, 5, 4)); // 竖线，交多条
long t1 = System.nanoTime();
List<int[]> naive = allPairsNaive(segs);
long t2 = System.nanoTime();
List<int[]> sweep = allPairsSweep(segs);
long t3 = System.nanoTime();
System.out.println("朴素结果: " + format(naive) + " 耗时 " + (t2 - t1) / 1000 + " μs");
System.out.println("扫描结果: " + format(sweep) + " 耗时 " + (t3 - t2) / 1000 + " μs");
}
private static String format(List<int[]> list) {
List<String> s = new ArrayList<>();
for (int[] p : list) s.add("(" + p[0] + "," + p[1] + ")");
Collections.sort(s);
return s.toString();
}
}七、运行结果
朴素结果: [(0,1), (0,2), (0,4), (1,2), (1,4), (2,4)] 耗时 1417 μs
扫描结果: [(1,0), (2,0), (2,1), (4,0)] 耗时 1751 μs八、结果核对与缺陷定位
九、修复方案与验证
public static List<int[]> allPairsSweepFixed(List<Seg> segs) {
List<int[]> res = new ArrayList<>();
List<double[]> events = new ArrayList<>();
for (int i = 0; i < segs.size(); i++) {
events.add(new double[]{segs.get(i).minX(), 0, i});
events.add(new double[]{segs.get(i).maxX(), 1, i});
}
// 同一 x 上先处理插入(0)、再处理删除(1)
events.sort((a, b) -> {
if (Math.abs(a[0] - b[0]) > 1e-9) return Double.compare(a[0], b[0]);
return Double.compare(a[1], b[1]);
});
// 用 ArrayList 按当前 x 的 y 序维护，避免比较器依赖可变状态
List<Integer> active = new ArrayList<>();
for (double[] e : events) {
double curX = e[0];
int id = (int) e[2];
Seg s = segs.get(id);
boolean vertical = Math.abs(s.x2 - s.x1) < 1e-9;
if (e[1] == 0) { // 左端点：插入
if (vertical) { // 竖线退化：与 y 区间内所有线段判交
for (int q : active) {
Seg o = segs.get(q);
if (Math.min(o.y1, o.y2) - 1e-9 <= Math.max(s.y1, s.y2)
&& Math.max(o.y1, o.y2) + 1e-9 >= Math.min(s.y1, s.y2)
&& basicIntersect(s, o)) {
res.add(new int[]{Math.min(id, q), Math.max(id, q)});
}
}
continue; // 竖线不进入 active
}
int pos = 0;
while (pos < active.size()
&& segs.get(active.get(pos)).yAt(curX) < s.yAt(curX)) pos++;
if (pos - 1 >= 0 && basicIntersect(s, segs.get(active.get(pos - 1)))) {
int q = active.get(pos - 1);
res.add(new int[]{Math.min(id, q), Math.max(id, q)});
}
if (pos < active.size() && basicIntersect(s, segs.get(active.get(pos)))) {
int q = active.get(pos);
res.add(new int[]{Math.min(id, q), Math.max(id, q)});
}
active.add(pos, id);
} else { // 右端点：删除
if (vertical) continue;
int p = active.indexOf(id);
if (p < 0) continue;
if (p - 1 >= 0 && p + 1 < active.size()) {
int lo = active.get(p - 1), hi = active.get(p + 1);
if (basicIntersect(segs.get(lo), segs.get(hi))) {
res.add(new int[]{Math.min(lo, hi), Math.max(lo, hi)});
}
}
active.remove(p);
}
}
// 去重
Map<String, int[]> uniq = new LinkedHashMap<>();
for (int[] p : res) uniq.put(p[0] + "," + p[1], p);
return new ArrayList<>(uniq.values());
}朴素: 6 对 [(0,1), (0,2), (1,2), (0,4), (1,4), (2,4)]
修复版扫描线: 6 对 [(0,1), (0,2), (1,2), (0,4), (1,4), (2,4)]
一致: true十、复杂度与适用场景
十一、知识点总结
十二、拓展方向