A parallel algorithm for line segment intersection

The algorithm of line segment intersection is the core algorithm for vector map overlay. The traditional method is based on the plane-sweep process to find the intersections of two groups of lines. Although such method proves to be efficient in serial system, the basic data structure of this kind of algorithm needs to maintain a tree structure, which has the data-lock in multi-core system. In addition, with the development of data volume and the enhancement of user requirement, a parallel algorithm is needed in order to compute the line segment intersections correctly and efficiently. In this paper, we present a parallel algorithm for line segment intersection to process the large and complex spatial data, which is efficient in multi-core system and cluster environment. In the experiment results, our algorithm leads to an accurate result compared with ArcGIS. And in the test of large spatial data, our algorithm demonstrates a good performance of speed-up with the increasing of cores.