基于单调链的Red/Blue扫描线求交算法

Red-Blue Sweep Line Algorithm Based on Monotone Chains for Connected Line Segment Intersection Problems

提出了一种基于单调链的Red/Blue平面扫描线算法。该算法针对GIS中线段之间具有连接关系的特性,将平面连接线段集分解为一组单调链,通过对单调链的粗扫描过滤和对线段的精扫描求交,减少了扫描过程中的冗余计算,提高了线段集求交点的效率。实验证明,该算法对于处理具有连接关系的线段集的求交点问题具有很高的效率。

An improved Red/Blue sweep line algorithm is preserted for connected line segment intersection in GIS. First the algorithm breaks down the connected segments into monotone chains. By filtration for monotone chains, those monotone chains which can not generate intersection points are removed. Then algorithm computes intersection points among rest monotone chains by traditional Red/Blue sweep line algorithm, which is based on isolated line s more egmen efficie Key words ts. Both theoretic analysis and experiments show that our algorithm performs ntly than the traditional Red/Blue sweep line algorithm does.