基于扫描线的线段求交算法 (2013年)

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