本文主要是介绍清华计算几何-线段求交与BO算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
单轴线段求交
给定单边轴下, N定线段，检查出相交的线段.
解法一: 暴力求解
遍历所有线段对，进行相交判断, 算法复杂度为O(n2)
解法二: LR扫描
把每条线段的头尾认定为L和R。对所有点进行排序，如果每两个点满足LL或者RR，则对应的线段相交。如果为LR，则对应的线段无相交，算法复杂度为O(nlog(n))
多轴线段求交 - BO算法(line sweep)
上面强调是单个坐标轴的线段求交，扩展到XY轴甚至更多轴.
比较常用的算法有 bentley–ottmann algorithm, 简称BO算法。
利用扫描线进行求交的算法.
算法复杂度: O((n + I) * logn)
空间: O(n + I)
N为线段总数, I为线段交点.
扫描线相交线的垂直排序(从上到下)
扫描线为垂直线, 自左向右扫描, 在x = t时刻, 扫描线与多条线段相交, 按照相交点的高度从上往下排序, 在最上面交点所在的线段顺序最高，然后依次往下降低。
事件点和扫描线移动导致垂直排序变化(从左到右)
随着扫描线的移动，假设原来线段A的顺序高于线段B，但是经过某些关键点变化，他们的相对顺序会颠倒。这些点成为事件(Event)
扫描线移动的时候导致垂直排序发生改变的三个关键时间点:
[1]线段左端点
[2]两条线段相交点
[3]线段右端点
BO算法使用的数据结构
前面说到BO算法由扫描线从左向右扫描, 扫描线时刻会和某部分线段产生相交事件(左右端点 + 相交事件), 而多条线段之间又存在高度之间的顺序排列以及顺序变化。
EventQueue
从左到右经过线段的左右端点和相交点都为事件点。
优先队列
Status Struct
和扫描线X = t正在相交的线段，进行上下维度的高度排序
平衡二叉树
扫描线从左到右扫描线段的三种情况
扫描线进行扫描的EventQueue案例
扫描线相交线段上下维度的StatusStruct变化的案例
(线段左端点，右端点，和相交事件)三种事件下StatusStruct都会产生变化，BBST(平衡二叉树)实现其中的删减和重新排序
BO算法中判断线段相交是前面线段三类事件决定的结果--案例
其中f和e相交就是线段P右端点引发的事件后果.(三类事件中的第二类事件)
BO算法特殊情况下效率低下--重复测试
参考资料
[1]清华计算几何 P66 - P82
这篇关于清华计算几何-线段求交与BO算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
