当前位置：服务支持 > 软件文章 > Bentley-Ottmann算法：N条线段交点求解方法

Bentley-Ottmann算法：N条线段交点求解方法

阅读数 3

Bentley-Ottmann算法：求N条线段的交点

Bentley-Ottmann算法
算法复杂度 1. 使用暴力求解，遍历每一条线段 i ，固定 i 遍历 j 与 i 是否存在交点： 2. 此时我们可以稍微优化一点算法复杂度，判断过 i, j 是否相交以后，j, i 就不用再判断了： 3. Bentley-Ottmann算法算法案例（流程） 1. 问题描述 2. 名词介绍（1）Event Queue（事件队列）：后续用Q表示（2）Sweep Status（扫描线）：后续用L表示（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 排序的队列中； 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 ) ) }

𝑆=𝑠0,𝑠1,...,𝑠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))} 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 ) ) } 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=()，结束