论文部分内容阅读
本文对Preparata和Shamos的线段集求交的平面扫描算法进行了改进。新算法能处理原算法不能处理的四种情况:(1)线段集中垂线;(2)多个线段端点或交点的横坐标相等;(3)多条线段交于一点;(4)几条线段共端点或一条线段的端点落在另一条线段上。算法的时间复杂度和空间复杂度分别为0((N+K)logN)和0(N+K),其中N为线段数,K为交点数。