【文件属性】：
文件名称：当处理线-python读取mat文件并转为csv文件的实例
文件大小：9.75MB
文件格式：PDF
更新时间：2021-06-10 00:01:05
算法
定扫描线上，存储在 SL 中的线段是有序的，而且 SL 中的线段是动态变化的：（1）当处理线
段的左端点时，需要把该线段加入 SL 中；（2）当处理线段的右端点时，需要把该线段从 SL
中删除；（3）还需要查询与指定线段相邻且位于其上方或者下方的线段。可以考虑采用平衡
二叉树来设计 SL ，这样线段的插入、删除、查询操作可以在 (log )O n 时间内完成，对 SL 的
操作有:
i. .insert( )SL L ，把线段 L 插入 SL 中；
ii. .delete( )SL L ，把线段 L 从 SL 中删除；
iii. .above( )SL L ，返回与线段 L 相邻且位于其上方的一条线段；
iv. .below( )SL L ，返回与线段 L 相邻且位于其下方的一条线段；
Shamos-Hoey 算法的伪码如下所示：
设输入是一个线段集合 { },0 i
i
S L n ，判断线段集中是否存在相交
SHAMOS_HOEY( )S
return ({TRUE , FALSE})
1. 对线段集 S 中的端点按照 x,y 的字典序进行排序，使得
0
P 表示最左方的点，
2 1n
P
表示
最右方的点。
2. SL ;
3. for( i=0 ; i<2n-1; i++ )