The line segment intersection problem is one of the basic problems in computational geometry and has been widely used in spatial analysis in Geographic Information Systems （GIS）. Lots of traditional algorithms study...The line segment intersection problem is one of the basic problems in computational geometry and has been widely used in spatial analysis in Geographic Information Systems （GIS）. Lots of traditional algorithms study the problem in a serial environment. However, in GIS, a spatial object is much more complicated and is considered to be always composed of multiple line segments, and one line segment connects another line segment at its endpoint. On the other hand, along with the advances made in computer hardware, more and more personal computers have multiple cores or CPUs equipped. Thus, to make full use of the increasing computing resources, parallel technique is applied as one of the most available methods. Apparently, the traditional algorithms should be improved to take advantage of the technologies. Under these circumstances, based on the modified uniform grid algorithm, which is adapted to dealing with spatial objects in GIS, this paper proposes a parallel strategy in a shared memory architecture. Also, experimental results are given in the final part of this paper to demonstrate the efficiency this strategy brings.展开更多
文摘The line segment intersection problem is one of the basic problems in computational geometry and has been widely used in spatial analysis in Geographic Information Systems （GIS）. Lots of traditional algorithms study the problem in a serial environment. However, in GIS, a spatial object is much more complicated and is considered to be always composed of multiple line segments, and one line segment connects another line segment at its endpoint. On the other hand, along with the advances made in computer hardware, more and more personal computers have multiple cores or CPUs equipped. Thus, to make full use of the increasing computing resources, parallel technique is applied as one of the most available methods. Apparently, the traditional algorithms should be improved to take advantage of the technologies. Under these circumstances, based on the modified uniform grid algorithm, which is adapted to dealing with spatial objects in GIS, this paper proposes a parallel strategy in a shared memory architecture. Also, experimental results are given in the final part of this paper to demonstrate the efficiency this strategy brings.
