基于GPU的任意多边形相交面积计算方法

高 艺,罗健欣,裘杭萍,唐 斌,吴 波

(1.解放军理工大学 指挥信息系统学院，江苏 南京 210007； 2.解放军61175部队，江苏 南京 210049)

引用著录：高艺,罗健欣,裘杭萍，等.基于GPU的任意多边形相交面积计算方法[J].测绘工程，2017，26(12)：55-59.

DOI:10.19349/j.cnki.issn1006-7949.2017.12.011

基于GPU的任意多边形相交面积计算方法

高 艺1,2,罗健欣1,裘杭萍1,唐 斌1,吴 波1

(1.解放军理工大学 指挥信息系统学院，江苏 南京 210007； 2.解放军61175部队，江苏 南京 210049)

一直以来，任意多边形相交面积的高效计算都是地理信息系统中空间分析算法研究的重点。文中提出了一种基于GPU的栅格化多边形相交面积算法GPURAS，在此基础上，分别采用蒙特卡罗方法和遮挡查询技术进一步提出GPURASMC算法和GPURASQ算法，并证明了上述算法的正确性。实验对简单多边形、任意复杂多边形及大数据量多边形进行了测试对比，结果表明：GPURAS算法精度高，通用性较好但效率受CPU与GPU通信延迟的影响；GPURASMC算法效率较高但牺牲了部分精度；GPURASQ算法精度高、效率高但局限于特定运行环境。与基于CPU的传统算法相比，文中所提3种算法效率更高，在处理包含大量顶点的多边形时，效率提升尤为明显。

多边形; 相交面积计算; GPU; 栅格化; 蒙特卡罗

多边形指同一平面上不同的点首尾顺次连结，任一个顶点都在边上，且任意不相邻的两条边不相交。求任意多边形的相交面积是计算几何学、流体力学、计算机图形学的基本问题。在全国国土资源“一张图”基础数据服务系统中，经常涉及大量的多边形套合相交计算。因此，对这一问题的研究具有重要的理论意义和应用价值。……