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

摘要

本发明公开了一种基于GPU的任意多边形相交面积计算方法，该方法借助于GPU来实现任意多边形的栅格化，将以顶点坐标表示的多边形转换为以栅格表示的多边形栅格图像，再根据栅格图像的相交情况对所有栅格的位置标示符进行赋值、修正，然后再由CPU或者GPU来统计相交栅格的数目并计算相交面积。该方法不受多边形凹凸性的限制，利用了GPU的并行特性，与借助于CPU的计算方法相比，大大提升了处理速度，并且原理简单，实现方便。实验结果表明，本发明的计算方法适用于任意复杂多边形，很好的避免了传统计算方法所遇到的奇异性问题，从而具有较好的鲁棒性。

主权项

一种基于GPU的任意多边形相交面积计算方法，其特征在于，所述计算方法包括如下步骤：(1)在栅格场中确定一个栅格区域，并对所述该栅格区域初始化，将所述栅格区域内各栅格对应的位置标示符的值均预设为初始值a，a≥0；(2)在所述栅格区域内生成第一个多边形栅格图像，将以顶点坐标表示的第一个多边形对应转换为由GPU处理的以栅格表示的第一个多边形栅格图像，若所述栅格区域内任一栅格位于所述第一个多边形栅格图像的内部或边线上，则将所述栅格对应的位置标示符的值累加b变为a+b，b≥1，否则，若所述栅格区域内任一栅格位于所述第一个多边形栅格图像的外部，则所述栅格对应的位置标示符的值不变；(3)继续生成第2～n个多边形栅格图像，按照步骤(2)所述方法顺次在所述栅格区域内继续生成其余n‑1个多边形栅格图像，n≥2，其中，在生成每一个当前多边形栅格图像时，若所述栅格区域内任一栅格位于所述当前多边形栅格图像的内部或边线上，则将所述栅格对应的位置标示符的值累加b，否则，若所述栅格区域内任一栅格位于所述当前多边形栅格图像的外部，则所述栅格对应的位置标示符的值不变；(4)统计n个多边形栅格图像的相交栅格数count，统计所述栅格区域内位置标示符的值为a+nb的栅格的数目，该数目即为n个多边形栅格图像的相交栅格数count；(5)计算n个多边形的相交面积，将所述的相交栅格数count除以所述栅格区域的分辨率，然后再乘以栅格区域的面积，即得到所述n个多边形的相交面积S。