Bentley-Ottmann算法：求N条线段的交点
使用Bentley-Ottmann算法，求N条线段的交点，Bentley-Ottmann算法案例，Bentley-Ottmann算法例子，Bentley-Ottmann算法流程
Bentley-Ottmann算法：求N条线段的交点
- Bentley-Ottmann算法
- 算法复杂度
- 算法案例（流程）
- 1. 问题描述
- 2. 名词介绍
- 3. 案例讲解
- （1）排序： 将所有端点按照 y y y 坐标大小进行排序，存在 Q Q Q 中，得到第 "-" 行。案例按照 y y y 从大到小排序
- （2）3个原子操作：
- a. 当扫描线扫描到线段初始点时，进行出队操作，取出队顶元素，判断相邻线段与当前线段是否相交。相交时将交点入队，将其插入到按 y y y 排序的队列中；
- b. 当扫描线扫描到线段交点时，将交点 x i j x_{ij} xij 进行出队操作，并且将 L L L 中对应的 i , j i,j i,j 交换位置，在重新判断 i , j i,j i,j 与各自相邻线段是否相交，相交时，将其插入到按 y y y 排序的队列中；
- c. 当扫描线扫描到线段末尾点时，将右端点进行出队操作，从 L L L 中将 s i s_i si 去除。此时判断与 s i s_i si 相邻的两个线段是否相交，相交时，将其插入到按 y y y 排序的队列中。
- （3）按照表格左侧 Event 来解析每一步的含义
- 最后
Bentley-Ottmann算法
如果说你想知道这个方法的历史，那么推荐几篇远古论文：
- 来自Michael Ian Shamos和Dan Hoey在1976年发表的：
M. I. Shamos and D. Hoey, “Geometric intersection problems,” 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), 1976, pp. 208-215, doi: 10.1109/SFCS.1976.16.
上链接：
http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf - 作者Bentley和Ottmann改进了上面的方法：
Bentley and Ottmann, “Algorithms for Reporting and Counting Geometric Intersections,” in IEEE Transactions on Computers, vol. C-28, no. 9, pp. 643-647, Sept. 1979, doi: 10.1109/TC.1979.1675432.
上链接：http://www.itseng.org/research/papers/topics/VLSI_Physical_Design_Automation/Physical_Verification/DRC/Geometric_Intersection_Problems/1979-Bentley.pdf
算法复杂度
我们求N条线段中任意两条线段的交点的个数：
1. 使用暴力求解，遍历每一条线段 i ，固定 i 遍历 j 与 i 是否存在交点：
// 暴力求解
for(int i = 0; i < segment.size(); i++)
{
for(int j = 0; j < segment.size(); j++)
{
//判断是否相交
}
}
算法时间复杂度为：
O
(
n
2
)
O(n^{2})
O(n2)
T
(
n
)
=
(
n
+
n
+
n
+
.
.
.
+
n
)
=
n
2
T(n) = (n+n+n+...+n)=n^{2}
T(n)=(n+n+n+...+n)=n2
2. 此时我们可以稍微优化一点算法复杂度，判断过 i, j 是否相交以后，j, i 就不用再判断了：
// 优化
for(int i = 0; i < segment.size(); i++)
{
for(int j = i; j < segment.size(); j++)
{
//判断是否相交
}
}
算法时间复杂度为：
O
(
n
2
)
O(n^{2})
O(n2)
T
(
n
)
=
(
1
+
2
+
3
+
.
.
.
+
n
)
=
n
2
+
n
2
T(n) = (1+2+3+...+n)=\frac{n^{2}+{n}}{2}
T(n)=(1+2+3+...+n)=2n2+n
3. Bentley-Ottmann算法
排序算法时间复杂度为：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
使用平衡二叉树进行插入、删除操作，时间复杂度为：
O
(
l
o
g
n
)
O(logn)
O(logn)
事件队列最多存储
2
∗
n
+
x
2*n+x
2∗n+x个点
（事件队列是什么意思？在算法案例中将讲解）
所以Bentley-Ottmann算法时间复杂度最大为：
O
(
(
2
n
+
i
)
l
o
g
n
)
=
O
(
n
l
o
g
n
)
O((2n+i)logn)=O(nlogn)
O((2n+i)logn)=O(nlogn)
算法案例（流程）
我们通过讲解下面这个案例来理解算法：如果想直接看论文转下
论文案例链接：
http://www.ams.sunysb.edu/~jsbm/courses/345/13/bentley-ottmann.pdf
1. 问题描述
给定7条线段，用
S
S
S表示
S
=
s
0
,
s
1
,
.
.
.
,
s
6
=
{
(
(
15
,
17
)
,
(
7
,
3
)
)
,
(
(
3
,
16
)
,
(
6
,
10
)
)
,
(
(
2
,
15
)
,
(
12
,
8
)
)
,
(
(
7
,
14
)
,
(
11
,
6
)
)
,
(
(
10
,
13
)
,
(
2
,
4
)
)
,
(
(
1
,
12
)
,
(
9
,
5
)
)
,
(
(
−
3
,
11
)
,
(
5
,
2
)
)
}
\begin{aligned} S&={s_{0},s_{1},...,s_{6}} \\ &={\{((15,17),(7,3)), ((3,16),(6,10)),((2,15),(12,8)), ((7,14),(11,6)), }\\ & {((10,13),(2,4)), ((1,12),(9,5)), ((-3,11),(5,2))\}} \\ \end{aligned}
S=s0,s1,...,s6={((15,17),(7,3)),((3,16),(6,10)),((2,15),(12,8)),((7,14),(11,6)),((10,13),(2,4)),((1,12),(9,5)),((−3,11),(5,2))}
每条线段用
s
i
=
(
a
i
,
b
i
)
s_i=(a_i, b_i)
si=(ai,bi)表示，
a
i
a_i
ai表示起始点，
b
i
b_i
bi表示末尾点。
如图：Joe Mitchell的例子
2. 名词介绍
（1）Event Queue（事件队列）：后续用Q表示
该算法通过维护一个队列的入队、出队来求所有的交点，而该队列称为事件队列。
（2）Sweep Status（扫描线）：后续用L表示
使用一条平行于
x
x
x 轴或者平行于
y
y
y 轴的直线遍历所有线段的端点以及交点，有图有真相：
（3） 交点：用 x i j x_{ij} xij 表示， i , j i, j i,j 表示相交的两条线段的下标
3. 案例讲解
（1）排序： 将所有端点按照 y y y 坐标大小进行排序，存在 Q Q Q 中，得到第 “-” 行。案例按照 y y y 从大到小排序
（2）3个原子操作：
a. 当扫描线扫描到线段初始点时，进行出队操作，取出队顶元素，判断相邻线段与当前线段是否相交。相交时将交点入队，将其插入到按 y y y 排序的队列中；
假如当前 L = ( s 2 , s 1 , s 3 , s 0 ) L=(s_{2},s_{1},s_{3},s_{0}) L=(s2,s1,s3,s0)，判断 s 1 s_1 s1 与相邻线段 s 2 、 s 3 s_{2}、s{3} s2、s3 是否相交。
b. 当扫描线扫描到线段交点时，将交点 x i j x_{ij} xij 进行出队操作，并且将 L L L 中对应的 i , j i,j i,j 交换位置，在重新判断 i , j i,j i,j 与各自相邻线段是否相交，相交时，将其插入到按 y y y 排序的队列中；
c. 当扫描线扫描到线段末尾点时，将右端点进行出队操作，从 L L L 中将 s i s_i si 去除。此时判断与 s i s_i si 相邻的两个线段是否相交，相交时，将其插入到按 y y y 排序的队列中。
（3）按照表格左侧 Event 来解析每一步的含义
-
扫描线扫描到 a 0 a_0 a0，从队列 Q Q Q 中出队，将 a 0 a_0 a0 所对应的线段 s 0 s_0 s0 添加到 L L L 中， L L L 中只有一条线段，无需判断是否相交；
-
扫描线扫描到 a 1 a_1 a1，从队列 Q Q Q 中出队，将 a 1 a_1 a1 所对应的线段 s 1 s_1 s1 添加到 L L L 中， L L L 中有两条线段，判断是否相交，结果不相交，进行下一步；
注意：此时问题来了，将 s 1 s_1 s1 添加到 s 0 s_0 s0 的前面还是后面呢？
答：按照扫描线的 x x x 的大小，从小到大排序。
现在 L L L 经过了 s 0 , s 1 s_0,s_1 s0,s1 将扫描线与 s 0 , s 1 s_0,s_1 s0,s1 的交点按照 x x x 从小到大排序。将 s 1 s_1 s1 放在 s 0 s_0 s0 前面。
-
扫描线扫描到 a 2 a_2 a2，从队列 Q Q Q 中出队，将 a 2 a_2 a2 所对应的线段 s 2 s_2 s2 添加到 L L L 中（按照 x x x 升序添加： L = ( s 2 , s 1 , s 0 ) L=(s_2,s_1,s_0) L=(s2,s1,s0)）， L L L 中有三条线段，判断 s 2 s_2 s2 与相邻线段 s 1 s_1 s1 是否相交（注意，此时 s 2 s_2 s2 在 L L L 中相邻的线段只有 s 1 s_1 s1， 而没有 s 5 s_5 s5 ），结果相交，将交点 x 12 x_{12} x12插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到 a 3 a_3 a3，从队列 Q Q Q 中出队，将 a 3 a_3 a3 所对应的线段 s 3 s_3 s3 添加到 L L L 中（按照 x x x 升序添加： L = ( s 2 , s 1 , s 3 , s 0 ) L=(s_2,s_1,s_3,s_0) L=(s2,s1,s3,s0)）， L L L 中有四条线段，判断 s 3 s_3 s3 与相邻线段 s 1 、 s 0 s_1、s_0 s1、s0 是否相交，结果 s 3 s_3 s3 与 s 0 s_0 s0 相交，将交点 x 03 x_{03} x03插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到交点 x 12 x_{12} x12，从队列 Q Q Q 中出队，交换 L = ( s 2 , s 1 , s 3 , s 0 ) L=(s_2,s_1,s_3,s_0) L=(s2,s1,s3,s0) 中交点所对应的线段 s 1 , s 2 s_1,s_2 s1,s2 的位置： L = ( s 1 , s 2 , s 3 , s 0 ) L=(s_1,s_2,s_3,s_0) L=(s1,s2,s3,s0)，重新判断 s 1 , s 2 s_1,s_2 s1,s2 与各自的相邻线段是否存在交点，此时 s 2 s_2 s2 与相邻线段 s 3 s_3 s3 相交，将交点 x 23 x_{23} x23 插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到 a 4 a_4 a4，从队列 Q Q Q 中出队，将 a 4 a_4 a4 所对应的线段 s 4 s_4 s4 添加到 L L L 中（按照 x x x 升序添加： L = ( s 1 , s 2 , s 3 , s 4 , s 0 ) L=(s_1,s_2,s_3,s_4,s_0) L=(s1,s2,s3,s4,s0)， L L L 中有五条线段，判断 s 4 s_4 s4 与相邻线段 s 3 、 s 0 s_3、s_0 s3、s0 是否相交，结果 s 4 s_4 s4 与 s 3 s_3 s3 相交，将交点 x 34 x_{34} x34插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到 a 5 a_5 a5，从队列 Q Q Q 中出队，将 a 5 a_5 a5 所对应的线段 s 5 s_5 s5 添加到 L L L 中（按照 x x x 升序添加： L = ( s 5 , s 1 , s 2 , s 3 , s 4 , s 0 ) L=(s_5,s_1,s_2,s_3,s_4,s_0) L=(s5,s1,s2,s3,s4,s0)， L L L 中有六条线段，判断 s 5 s_5 s5 与相邻线段 s 1 s_1 s1 是否相交，结果 s 5 s_5 s5 与 s 1 s_1 s1 不相交，转下一步；
-
扫描线扫描到交点 x 34 x_{34} x34，从队列 Q Q Q 中出队，交换 L = ( s 5 , s 1 , s 2 , s 3 , s 4 , s 0 ) L=(s_5,s_1,s_2,s_3,s_4,s_0) L=(s5,s1,s2,s3,s4,s0)） 中交点所对应的线段 s 3 , s 4 s_3,s_4 s3,s4 的位置： L = ( s 5 , s 1 , s 2 , s 4 , s 3 , s 0 ) L=(s_5,s_1,s_2,s_4,s_3,s_0) L=(s5,s1,s2,s4,s3,s0)，重新判断 s 3 , s 4 s_3,s_4 s3,s4 与各自的相邻线段是否存在交点
此时 s 3 s_3 s3 与相邻线段 s 0 s_0 s0 相交，但是 x 03 x_{03} x03 已经存在于队列 Q Q Q 中了，所以不用重新加入；
s 4 s_4 s4 与相邻线段 s 2 s_2 s2 相交，将交点 x 24 x_{24} x24 插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到 a 6 a_6 a6，从队列 Q Q Q 中出队，将 a 6 a_6 a6 所对应的线段 s 6 s_6 s6 添加到 L L L 中（按照 x x x 升序添加： L = ( s 6 , s 5 , s 1 , s 2 , s 4 , s 3 , s 0 ) L=(s_6,s_5,s_1,s_2,s_4,s_3,s_0) L=(s6,s5,s1,s2,s4,s3,s0)， L L L 中有七条线段，判断 s 6 s_6 s6 与相邻线段 s 5 s_5 s5 是否相交，结果 s 5 s_5 s5 与 s 1 s_1 s1 不相交，转下一步；
-
扫描线扫描到交点 x 24 x_{24} x24，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 5 , s 1 , s 2 , s 4 , s 3 , s 0 ) L=(s_6,s_5,s_1,s_2,s_4,s_3,s_0) L=(s6,s5,s1,s2,s4,s3,s0) 中交点所对应的线段 s 2 , s 4 s_2,s_4 s2,s4 的位置： L = ( s 6 , s 5 , s 1 , s 4 , s 2 , s 3 , s 0 ) L=(s_6,s_5,s_1,s_4,s_2,s_3,s_0) L=(s6,s5,s1,s4,s2,s3,s0)，重新判断 s 2 , s 4 s_2,s_4 s2,s4 与各自的相邻线段是否存在交点
此时 s 2 s_2 s2 与相邻线段 s 3 s_3 s3 相交，但是 x 23 x_{23} x23 已经存在于队列 Q Q Q 中了，所以不用重新加入；
s 4 s_4 s4 与相邻线段 s 1 s_1 s1 不相交，转下一步；
-
扫描线扫描到交点 x 23 x_{23} x23，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 5 , s 1 , s 4 , s 2 , s 3 , s 0 ) L=(s_6,s_5,s_1,s_4,s_2,s_3,s_0) L=(s6,s5,s1,s4,s2,s3,s0) 中交点所对应的线段 s 2 , s 4 s_2,s_4 s2,s4 的位置： L = ( s 6 , s 5 , s 1 , s 4 , s 3 , s 2 , s 0 ) L=(s_6,s_5,s_1,s_4,s_3,s_2,s_0) L=(s6,s5,s1,s4,s3,s2,s0)，重新判断 s 2 , s 3 s_2,s_3 s2,s3 与各自的相邻线段是否存在交点
此时 s 2 s_2 s2 与相邻线段 s 0 s_0 s0 相交，但是 x 02 x_{02} x02 已经存在于队列 Q Q Q 中了，所以不用重新加入；
s 3 s_3 s3 与相邻线段 s 1 s_1 s1 不相交，转下一步；
-
扫描线扫描到末尾端点 b 1 b_{1} b1，从队列 Q Q Q 中出队，删除 L L L 中的 s 1 s_1 s1， L = ( s 6 , s 5 , s 4 , s 3 , s 2 , s 0 ) L=(s_6,s_5,s_4,s_3,s_2,s_0) L=(s6,s5,s4,s3,s2,s0)，判断与 s 1 s_1 s1 相邻的线段 s 5 , s 4 s_5,s_4 s5,s4 是否相交，结果 s 5 s_5 s5 与 s 4 s_4 s4 相交，将交点 x 45 x_{45} x45 插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到交点 x 02 x_{02} x02，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 5 , s 4 , s 3 , s 2 , s 0 ) L=(s_6,s_5,s_4,s_3,s_2,s_0) L=(s6,s5,s4,s3,s2,s0) 中交点所对应的线段 s 2 , s 0 s_2,s_0 s2,s0 的位置： L = ( s 6 , s 5 , s 4 , s 3 , s 0 , s 2 ) L=(s_6,s_5,s_4,s_3,s_0,s_2) L=(s6,s5,s4,s3,s0,s2)，重新判断 s 2 , s 0 s_2,s_0 s2,s0 与各自的相邻线段是否存在交点
此时 s 3 s_3 s3 与相邻线段 s 0 s_0 s0 相交，但是 x 03 x_{03} x03 已经存在于队列 Q Q Q 中了，所以不用重新加入；
-
扫描线扫描到交点 x 03 x_{03} x03，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 5 , s 4 , s 3 , s 0 , s 2 ) L=(s_6,s_5,s_4,s_3,s_0,s_2) L=(s6,s5,s4,s3,s0,s2) 中交点所对应的线段 s 0 , s 3 s_0,s_3 s0,s3 的位置： L = ( s 6 , s 5 , s 4 , s 0 , s 3 , s 2 ) L=(s_6,s_5,s_4,s_0,s_3,s_2) L=(s6,s5,s4,s0,s3,s2)，重新判断 s 0 , s 3 s_0,s_3 s0,s3 与各自的相邻线段是否存在交点
此时 s 3 s_3 s3 与相邻线段 s 2 s_2 s2 相交，但是 x 23 x_{23} x23 已经遍历过了，所以不用重新加入；
s 0 s_0 s0 与相邻线段 s 4 s_4 s4 不相交，转下一步；
-
扫描线扫描到交点 x 45 x_{45} x45，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 5 , s 4 , s 0 , s 3 , s 2 ) L=(s_6,s_5,s_4,s_0,s_3,s_2) L=(s6,s5,s4,s0,s3,s2)） 中交点所对应的线段 s 4 , s 5 s_4,s_5 s4,s5 的位置： L = ( s 6 , s 4 , s 5 , s 0 , s 3 , s 2 ) L=(s_6,s_4,s_5,s_0,s_3,s_2) L=(s6,s4,s5,s0,s3,s2)，重新判断 s 4 , s 5 s_4,s_5 s4,s5 与各自的相邻线段是否存在交点
结果 s 4 s_4 s4 与 s 6 s_6 s6 相交，将交点 x 46 x_{46} x46 插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
s 5 s_5 s5 与 s 0 s_0 s0 相交，将交点 x 05 x_{05} x05 插入队列 Q Q Q 中（按 y y y 大小排序的位置中）；
-
扫描线扫描到末尾端点 b 2 b_2 b2，从队列 Q Q Q 中出队，删除 L L L 中的 s 2 s_2 s2， L = ( s 6 , s 4 , s 5 , s 0 , s 3 ) L=(s_6,s_4,s_5,s_0,s_3) L=(s6,s4,s5,s0,s3)， s 2 s_2 s2 只与 s 3 s_3 s3 相邻，所以不做任何操作；
-
扫描线扫描到末尾端点 b 3 b_3 b3，从队列 Q Q Q 中出队，删除 L L L 中的 s 3 s_3 s3， L = ( s 6 , s 4 , s 5 , s 0 ) L=(s_6,s_4,s_5,s_0) L=(s6,s4,s5,s0)， s 3 s_3 s3 只与 s 0 s_0 s0 相邻，所以不做任何操作；
-
扫描线扫描到交点 x 05 x_{05} x05，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 4 , s 5 , s 0 ) L=(s_6,s_4,s_5,s_0) L=(s6,s4,s5,s0) 中交点所对应的线段 s 5 , s 0 s_5,s_0 s5,s0 的位置： L = ( s 6 , s 4 , s 0 , s 5 ) L=(s_6,s_4,s_0,s_5) L=(s6,s4,s0,s5)，重新判断 s 5 , s 0 s_5,s_0 s5,s0 与各自的相邻线段是否存在交点， s 0 s_0 s0 与相邻线段 s 4 s_4 s4 不相交，转下一步；
-
扫描线扫描到末尾端点 b 5 b_5 b5，从队列 Q Q Q 中出队，删除 L L L 中的 s 5 s_5 s5， L = ( s 6 , s 4 , s 0 ) L=(s_6,s_4,s_0) L=(s6,s4,s0)， s 0 s_0 s0 与相邻线段 s 4 s_4 s4 不相交，转下一步；
-
扫描线扫描到交点 x 46 x_{46} x46，从队列 Q Q Q 中出队，交换 L = ( s 6 , s 4 , s 0 ) L=(s_6,s_4,s_0) L=(s6,s4,s0) 中交点所对应的线段 s 6 , s 0 s_6,s_0 s6,s0 的位置： L = ( s 4 , s 6 , s 0 ) L=(s_4,s_6,s_0) L=(s4,s6,s0)，重新判断 s 6 , s 0 s_6,s_0 s6,s0 与各自的相邻线段是否存在交点， s 0 s_0 s0 与相邻线段 s 6 s_6 s6 不相交，转下一步；
-
扫描线扫描到末尾端点 b 4 b_4 b4，从队列 Q Q Q 中出队，删除 L L L 中的 s 4 s_4 s4， L = ( s 6 , s 0 ) L=(s_6,s_0) L=(s6,s0)， s 6 s_6 s6 与相邻线段 s 0 s_0 s0 不相交，转下一步；
-
扫描线扫描到末尾端点 b 0 b_0 b0，从队列 Q Q Q 中出队，删除 L L L 中的 s 0 s_0 s0， L = ( s 6 ) L=(s_6) L=(s6)，不做任何操作
-
扫描线扫描到末尾端点 b 6 b_6 b6，从队列 Q Q Q 中出队，删除 L L L 中的 s 6 s_6 s6， L = ( ) L=() L=()，结束
最后
附上另一个案例的链接，供大家自行学习
https://tildesites.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-segmintersect.pdf
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
18
0- 0
已为社区贡献1条内容
所有评论(0)