问题背景
线段交点检测是计算几何中的经典问题：给定平面上 n 条线段，找出所有相交的线段对及其交点。
暴力法需要检查所有 C(n, 2) = O(n²) 对线段，当 n 较大时效率极低。Bentley-Ottmann 算法通过扫描线（Sweep Line）技术，将时间复杂度优化到 O((n + k) log n)，其中 k 是交点数量。
核心思想
算法维护一条垂直的扫描线，从左向右移动。在移动过程中，跟踪与扫描线相交的所有线段，并按交点 y 坐标排序存储在平衡树中。
事件点（Event Points）
扫描线在以下位置停止处理：
1. 线段左端点：新线段进入扫描线
2. 线段右端点：线段离开扫描线
3. 线段交点：相交线段的顺序在状态树中交换
扫描线状态（Status Structure）
一棵平衡二叉搜索树（如 TreeSet），存储当前与扫描线相交的线段，按键值排序（键值为线段在当前扫描线 x 位置的 y 坐标）。
关键观察
两条线段只有在扫描线状态中相邻时，才可能相交。因此只需检查相邻线段的交点，将可能交点加入事件队列。
Java 实现
import java.util.*;
public class BentleyOttmann {
static class Point implements Comparable<Point> {
double x, y;
Point(double x, double y) { this.x = x; this.y = y; }
@Override
public int compareTo(Point other) {
if (Math.abs(this.x - other.x) > 1e-9) {
return Double.compare(this.x, other.x);
}
return Double.compare(this.y, other.y);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return Math.abs(x - p.x) < 1e-9 && Math.abs(y - p.y) < 1e-9;
}
@Override
public int hashCode() {
return Objects.hash((int)(x * 1e9), (int)(y * 1e9));
}
@Override
public String toString() {
return String.format("(%.3f, %.3f)", x, y);
}
}
static class Segment {
Point p1, p2; // p1 是左端点，p2 是右端点
int id;
Segment(Point p1, Point p2, int id) {
if (p1.x > p2.x || (Math.abs(p1.x - p2.x) < 1e-9 && p1.y > p2.y)) {
this.p1 = p2; this.p2 = p1;
} else {
this.p1 = p1; this.p2 = p2;
}
this.id = id;
}
/**
* 计算线段在当前扫描线 x 处的 y 值
*/
double yAt(double x) {
if (Math.abs(p2.x - p1.x) < 1e-9) return p1.y;
return p1.y + (p2.y - p1.y) * (x - p1.x) / (p2.x - p1.x);
}
}
/**
* 计算两条线段的交点
* @return 交点，如果不相交则返回 null
*/
static Point intersect(Segment s1, Segment s2) {
double x1 = s1.p1.x, y1 = s1.p1.y, x2 = s1.p2.x, y2 = s1.p2.y;
double x3 = s2.p1.x, y3 = s2.p1.y, x4 = s2.p2.x, y4 = s2.p2.y;
double denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
if (Math.abs(denom) < 1e-9) return null; // 平行
double px = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / denom;
double py = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / denom;
// 检查交点是否在两线段上
if (px >= Math.min(x1, x2) - 1e-9 && px <= Math.max(x1, x2) + 1e-9 &&
px >= Math.min(x3, x4) - 1e-9 && px <= Math.max(x3, x4) + 1e-9 &&
py >= Math.min(y1, y2) - 1e-9 && py <= Math.max(y1, y2) + 1e-9 &&
py >= Math.min(y3, y4) - 1e-9 && py <= Math.max(y3, y4) + 1e-9) {
return new Point(px, py);
}
return null;
}
static class Event implements Comparable<Event> {
Point point;
int type; // 0: 左端点, 1: 右端点, 2: 交点
Segment seg1, seg2;
Event(Point p, int type, Segment s1, Segment s2) {
this.point = p; this.type = type;
this.seg1 = s1; this.seg2 = s2;
}
@Override
public int compareTo(Event other) {
int cmp = this.point.compareTo(other.point);
if (cmp != 0) return cmp;
// 左端点先于交点，交点先于右端点
return Integer.compare(this.type, other.type);
}
}
static class SweepComparator implements Comparator<Segment> {
double currentX;
SweepComparator(double x) { this.currentX = x; }
@Override
public int compare(Segment s1, Segment s2) {
double y1 = s1.yAt(currentX);
double y2 = s2.yAt(currentX);
if (Math.abs(y1 - y2) > 1e-9) return Double.compare(y1, y2);
return Integer.compare(s1.id, s2.id);
}
}
/**
* Bentley-Ottmann 主算法
*/
public static List<Point> findIntersections(List<Segment> segments) {
List<Point> intersections = new ArrayList<>();
PriorityQueue<Event> eventQueue = new PriorityQueue<>();
TreeSet<Segment> status = new TreeSet<>();
Map<Integer, Segment> idToSeg = new HashMap<>();
// 初始化事件队列
for (Segment seg : segments) {
eventQueue.add(new Event(seg.p1, 0, seg, null));
eventQueue.add(new Event(seg.p2, 1, seg, null));
idToSeg.put(seg.id, seg);
}
double currentX = Double.NEGATIVE_INFINITY;
SweepComparator comparator = new SweepComparator(currentX);
while (!eventQueue.isEmpty()) {
Event event = eventQueue.poll();
currentX = event.point.x;
comparator.currentX = currentX;
if (event.type == 0) { // 左端点：插入线段
Segment seg = event.seg1;
status.add(seg);
Segment above = status.higher(seg);
Segment below = status.lower(seg);
if (above != null) {
Point inter = intersect(seg, above);
if (inter != null && inter.x >= currentX - 1e-9) {
eventQueue.add(new Event(inter, 2, seg, above));
}
}
if (below != null) {
Point inter = intersect(seg, below);
if (inter != null && inter.x >= currentX - 1e-9) {
eventQueue.add(new Event(inter, 2, seg, below));
}
}
} else if (event.type == 1) { // 右端点：删除线段
Segment seg = event.seg1;
Segment above = status.higher(seg);
Segment below = status.lower(seg);
status.remove(seg);
if (above != null && below != null) {
Point inter = intersect(above, below);
if (inter != null && inter.x >= currentX - 1e-9) {
eventQueue.add(new Event(inter, 2, above, below));
}
}
} else { // 交点
Point inter = event.point;
intersections.add(inter);
Segment s1 = event.seg1;
Segment s2 = event.seg2;
// 在状态树中交换两条线段的位置
status.remove(s1);
status.remove(s2);
comparator.currentX = currentX + 1e-6; // 稍微向右移动
status.add(s1);
status.add(s2);
comparator.currentX = currentX;
}
}
return intersections;
}
public static void main(String[] args) {
List<Segment> segments = new ArrayList<>();
segments.add(new Segment(new Point(0, 0), new Point(5, 5), 0));
segments.add(new Segment(new Point(0, 5), new Point(5, 0), 1));
segments.add(new Segment(new Point(2, 0), new Point(2, 6), 2));
segments.add(new Segment(new Point(1, 2), new Point(4, 2), 3));
List<Point> intersections = findIntersections(segments);
System.out.println("找到的交点:");
for (Point p : intersections) {
System.out.println(" " + p);
}
}
}
简化版暴力对比实现
public class BruteForceIntersection {
public static List<BentleyOttmann.Point> bruteForce(
List<BentleyOttmann.Segment> segments) {
List<BentleyOttmann.Point> result = new ArrayList<>();
for (int i = 0; i < segments.size(); i++) {
for (int j = i + 1; j < segments.size(); j++) {
BentleyOttmann.Point p = BentleyOttmann.intersect(
segments.get(i), segments.get(j));
if (p != null) result.add(p);
}
}
return result;
}
}
复杂度分析
| 指标 | 暴力法 | Bentley-Ottmann |
|---|---|---|
| 时间复杂度 | O(n²) | O((n + k) log n) |
| 空间复杂度 | O(1) | O(n + k) |
| 适用场景 | n 小于 100 | n 大于 100 或 k 远小于 n² |
其中 k 是交点数量。当 k = O(n²) 时，两种方法都退化为 O(n²)，但 Bentley-Ottmann 的实际常数因子通常更小。
应用场景
- CAD/CAM 系统：检测设计图纸中的线段冲突
- GIS 地理信息系统：道路网络交叉点分析
- 游戏物理引擎：2D 多边形边碰撞检测
- VLSI 设计：集成电路布线的冲突检测
- 计算机图形学：光线追踪中的线段求交加速
- 模式识别：轮廓线段的交点特征提取
总结
Bentley-Ottmann 算法是计算几何中扫描线技术的典范。通过维护动态有序的状态结构和事件驱动的处理流程，它将看似需要 O(n²) 的交点检测问题优化到近线性时间。理解这一算法有助于掌握计算几何中更复杂的问题求解范式，如多边形布尔运算、Voronoi 图构造和 Delaunay 三角剖分。
