一种改进的多边形数据内点自动生成算法

1 概述

在地理信息系统中，多边形数据经常被用来表达面状分布的地理要素，如行政区划图、土壤分布图、湖泊、土地利用图等。在面状空间实体拓扑关系中，有学者指出闭合边界包含关系的确定是一个重要步骤[1]。而闭合边界包含关系的确定是一个比较复杂和耗时的过程，主要应用图形学的闭合边界包含关系判定准则[2]，即对于任意多边形 P1 和 P2，如果 P1 上有任意一点位于 P2 的内部，则 P1 被 P2 所包含，将多边形关系判定转变为多边形内点关系判定，因此，多边形数据内点的自动生成具有重要意义。

目前在进行多边形数据内点的自动生成时，主要应用基于最小外切矩形 (Minimum Bounding Rectangle, MBR)[3]的内点自动生成算法[1]。该算法思路清晰，且可以用于简单和复杂多边形的处理，但在一些奇异情况下容易导致算法失效。

本文提出一种有效的改进多边形数据内点自动生成算法，通过采用不确定性区间和相交区间的处理方法对奇异情况进行统一修正，并对算法健壮性进行分析和实验验证。

2 理论基础

2.1 多边形数据模型

多边形数据类型应用较广泛，其基础组织结构、拓扑关系、计算方法等已有较多研究。为了后续阐述方便，首先给出 3 个概念的描述与说明：

(1)节点(Vertex)：即坐标点，一般由二维(或多维)坐标值构成，表示平面(或多维空间)中的一个相对位置，是弧段的基本组成元素。

(2)弧段(Arc)：由多个节点顺次连接而成的有向线段，线段方向即通过节点连接顺序表达，是多边形边界的重要组成。

(3)多边形(Polygon)：由边界弧段构成的面状地理实体的表达，只由一条弧段构成的被称作简单多边形，由多条弧段构成的被称作复杂多边形(或复合多边形)。

更多内容请查看pdf