摘要
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.
线片断交叉问题是在计算几何学的基本问题之一并且广泛地在地理信息系统(GIS ) 在空间分析被使用了。大量传统的算法在连续环境学习这个问题。在 GIS，然而，一个空间目标是更复杂的并且被认为总是由线片断连接的多重线片断，和片断组成在它的端点的另一个线片断。与在计算机硬件献殷勤的一起，在另一方面，越来越多的个人计算机把多重核心或中央处理器装备。因此，充分利用增加的计算资源，平行技术作为最可得到的方法之一被使用。显然，传统的算法应该被改进利用技术。在这些情形下面，基于修改一致格子算法，它被使适应在 GIS 处理空间目标，这篇论文在分享的存储器体系结构建议平行策略。另外，试验性的结果在这篇论文的最后的部分被给表明这策略带的效率。
