基于扫描线的线段求交算法

本文以基于扫描线算法求线段的交点,首先设有一条扫描线l,从高于所有线段的位置起,自上而下地扫描整个平面,与当前扫描线相交的线段构成一个扫描线状态结构,在扫描线从上个事件点移到下个事件点时,要根据事件点的不同来更新扫描线的状态结构。该算法能避免盲目求交时大量无效求交测试。