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

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 segments.Both theoretic analysis and experiments show that our algorithm performs more efficiently than the traditional Red/Blue sweep line algorithm does.