杨静静 马骏

摘  要： 为了有效地解决遥感应用中感兴趣区域内有效遥感影像面积统计效率的问题，提出一种基于MPI（Message Passing Interface）的并行计算环境，采用经典数学定理鞋带公式（Shoelace Formula）及计算机图形学中向量积法计算多边形面积。使用三角分割法对多边形进行切割并行，判断多边形之间拓扑关系，获取交集顶点表，使用鞋带公式并行计算交多边形面积。以1.96407的加速比有效提高遥感影像有效面积统计效率，加快网页加载速度，提高用户体验度。

关键词： 遥感影像; 交多边形面积; MPI; 并行计算; 鞋带公式; 向量积

中图分类号：TP312          文献标识码：A     文章编号：1006-8228（2020）06-08-05

Abstract： In order to effectively solve the problem of statistical efficiency of effective remote sensing image area in the region of interest in remote sensing applications， this paper proposes a parallel computing environment based on MPI （Message Passing Interface）， which uses the classic mathematical theorem Shoelace Formula and Cross Product Algorithm in computer graphics to calculate the polygon area. Triangular segmentation is used to cut the polygons in parallel， determine the topological relationship between the polygons， obtain the intersection vertex data， and Shoelace Formula is used to calculate the area of the intersection polygons in parallel. With an acceleration ratio of 1.96407， it effectively improves the statistical efficiency of the effective area of remote sensing images， speeds up the loading of web pages， and improves user experience.

Key words： remote sensing image; intersection polygon area; MPI; parallel computing; Shoelace Formula; Cross Product

0 引言

隨着卫星遥感技术的迅速发展，采集的卫星遥感影像爆炸式幂指数增加。面对巨量的遥感影像，满足大范围检索条件要求的数据趋于上万条，对判断遥感影像间拓扑关系及计算遥感影像交并面积的计算效率提出挑战。

每一个遥感影像都有专属的坐标位置属性信息，故将计算多个遥感影像交并面积问题转换为计算多个简单多边形交并面积问题。计算多边形交并面积，首先需要获取多边形交并集顶点。判断任意多边形间拓扑关系不仅是计算几何与计算机图形学中的基本问题，也是GIS叠加分析的理论基础。因此，对这一问题的研究无论是在理论上，还是在实践上都有重要意义[4]。国内外针对多边形交并判断及交并面积计算问题，分别提出各类针对不同应用环境的多个多边形拓扑关系判断算法。如……