A Parallel Line Segment Intersection Strategy Based on Uniform Grids

Introduction

Reporting of segments set intersections is one of the fundamental problems of computational geome-try. Line segment intersection detection and reporting algorithm is useful in GIS, such as map overlay, spa-tial join in spatial databases, Boolean operations, and so on. It is an operation of great computational com-plexity and has been extensively studied to accelerate the computing process.

However, sometimes, it cannot satisfy the GIS ap-plications, especially when dealing with the ev-er-increasing size of dataset. With the development of computer hardware, personal computers equipped with multiple cores or multiple CPUs become more and more popular. Furthermore, GIS applications are often distributed on servers with high CPU capabili-ties. Such computers provide a strong basis for faster parallel data processing. In many fields, researchers have applied parallel computing technology to prac-tical problems and made considerable achievements. On the other hand, in GIS, especially in GIS plat-form software, traditional algorithms in a serial en-vironment are still the main stream and cannot make full use of these compute resources. Therefore, re-search on parallel strategy of these problems is in-dispensable.

Given this situation, we are motivated to study on the parallel strategy to make full use of the compute resources to accelerate the computing process. Based on uniform grid algorithm [1], we focus on the 258 Geo-spatial Information Science 12(4):257-264

shared memory parallel environment, in order to make applications perform well on the most popular computers that are equipped with multiple cores or multiple CPUs. The paper proposes a regular grid- based line intersection algorithm, which is parallel-ized after the domain decomposition of the study area.