线段相交问题的平面扫描型改进算法

摘要

本文对计算平面上n个线段所有交点的平面扫描算法及数据结构做了改进.若设这n个线段的交点总数为k,这n个线段中与垂直扫描线相交的最多个数为m,则改进后的算法的计算时间为O(nlogm+klogm),占用存储空间为O(m).