基于辛普森面积的多边形凹凸性识别算法

陈亚婷,严泰来,朱德海

(中国农业大学信息与电气工程学院,北京 100083）

基于辛普森面积的多边形凹凸性识别算法

陈亚婷,严泰来,朱德海

(中国农业大学信息与电气工程学院,北京 100083）

多边形顶点的凹凸性是其重要的形状特征,常被应用于制图综合、模式识别等方面。该文利用多边形特有的面积属性,将辛普森面积计算公式引入多边形顶点的凹凸性识别算法中,通过计算多边形中待判断顶点与其相邻两顶点所构成三角形的辛普森面积与整个多边形的辛普森面积的符号异同来判断顶点凹凸性。经推算证明,该算法对于复杂多边形的顶点凹凸性识别同样有效。

辛普森面积计算公式;顶点凹凸性;复杂多边形;多边形方向

为了详细了解各种地物的信息,常采用大比例尺进行调查成图;但在不同领域使用地图时,对地图详细度的要求不一致。例如,在分析一个地区的总体地域特征时,需要大范围浏览地物,以把握整体特性;通常的做法是以大比例尺数据作为数据源,过滤掉冗余信息,保留地物特征,形成概要的小比例尺地图。在该过程中,对多边形进行特征提取是最关键的步骤。凹凸性是多边形的重要形状特征,如能预先确定多边形的凹凸性,可使问题简化。

现有的多边形顶点凹凸性识别法有角度法、叉积法、拓扑映射法以及基于边向量斜率比较的方法等[1-6]。其中最基本的算法是角度法,但其计算效率低,且易出现奇异值。另一典型算法是叉积法,即在判别多边形方向的前提下,利用多边形相邻3点Pi-1、Pi、Pi+1的坐标组成的行列式值与零的关系来确定 Pi与有向线段 Pi-1Pi+1之间的位置关系,从而得到顶点 Pi的凹凸性。该算法正确率高,但计算量较大,且不适用于复杂多边形。本文利用多边形特有的面积属性,提出了基于辛普森面积的多边形顶点凹凸性识别算法,利用多边形3个连续顶点构成三角形的辛普森面积与整个多边形的辛普森面积符号的异同来识别简单多边形的凹凸性。

1 相关定义

(1）简单多边形:若多边形由平面上 n个不同点P1,P2,…,Pn首尾相连构成,且满足任意两条不相邻边都不相交,任意相邻的三点都不共线,称该多边形为简单多边形,其中 P1,P2,…,Pn为其顶点。

(2）复杂多边形:若一多边形由多个简单多边形组成,且满足任意两个简单多边形边界不相交,则称该多边形为复杂多边形,所有组成该复杂多边形的简单多边形的顶点称为该复杂多边形顶点。

(3）多边形的方向:使用辛普森公式计算多边形面积,若所得辛普森面积为正,则称该多边形方向为正方向;否则,称其方向为负方向。

(4）顶点的凹凸性:对于多边形某个顶点,若交于该顶点的相邻两边所形成的内角(即该多边形所围成有界区域内所形成的角）小于180°,称该顶点为凸点;若大于180°,称其为凹点;若等于180°,则称该顶点不具有凹凸性。

(5）结点:GIS中线的终点、起点和交点称为结点。

(6）弧段:GIS中两个结点之间的线段称为弧段。

2 凹凸性识别算法原理

凹凸性识别算法建立在GIS的图形存储数据结构基础上。基于该数据结构,将辛普森面积计算公式应用于多边形和待判断顶点所在三角形,即可判定顶点的凹凸性。

2.1 存储数据结构[7]

GIS中多边形的存储使用多边形-弧线拓扑结构定义,即数据结构中不直接存储多边形顶点坐标信息,而是存储组成该多边形的弧段。一个简单多边形由一系列组成其边界的弧线规定,复杂多边形则由多组弧线构成,其中每组弧线定义一个构成该复杂多边形的简单多边形。

为了定义多边形间的拓扑邻接性,每个弧段从起始结点到终止结点方向的左侧的多边形称为左多边形,右侧的多边形称为右多边形。对于复杂多边形,在遍历弧段时要求该多边形区域是所有组成其弧段的同侧多边形,这就要求构成“洞”的弧段方向与外边界的弧段方向相反。如图1所示,多边形区域同是构成其两个弧段的右多边形,“洞”弧段的方向与外边界弧段的方向相反。

图1 多边形弧段方向示意Fig.1 The arc direction of polygon

2.2 辛普森(Simpson）面积公式[7,8]

辛普森面积计算公式的基本思想是:按照多边形的顶点顺序依次求出多边形所有边与 X轴或者Y轴组成的梯形面积,然后求其代数和(图2）。一个由n个顶点组成的多边形的辛普森面积为:

由文献[8]可知,当多边形顶点呈顺时针方向排列时所得辛普森面积为正值,逆时针方向排列时辛普森面积为负值,而多边形几何面积为其辛普森面积的绝对值。

图2 辛普森面积计算原理示意Fig.2 The illustration of Simpson formula

2.3 基于简单多边形的凹凸性识别算法

通过论证可得到如下推理:无论多边形方向的正负性如何,其顶点与前后两顶点构成三角形的辛普森面积与多边形的辛普森面积符号相同时,该顶点必为凸点;反之,则该顶点必为凹点。

推理的证明过程如下:

多边形 p1p2…pn的辛普森面积为:

当2≤i≤n-1时,三角形 pi-1pipi+1的辛普森面积为:

去除目标顶点 pi后的多边形 p1 p2…pi-1 pi+1…pn的辛普森面积为:

当i=1或i=n时,令 p0=pn,pn+1=p1,易证上述结论仍成立,即有:

即多边形 p1p2…pn的几何面积为多边形 p1p2…pi-1pi+1…pn与三角形 pi-1pipi+1的几何面积之和,如图3a所示,则目标顶点 pi为凸点。

即多边形 p1p2…pn的几何面积为多边形 p1p2…pi-1pi+1…pn与三角形 pi-1pipi+1的几何面积之差,如图3b所示,则目标顶点 pi为凹点。

图3 顶点凹凸性面积原理示意Fig.3 The relationship between convex-concave feature and area

根据该推理,多边形顶点的凹凸性可通过判断多边形与顶点三角形的辛普森面积符号是否一致得出。以简单多边形 p1p2…pn为例,令 p0=pn,pn+1=p1。基于辛普森面积的顶点凹凸性识别算法的实现步骤为:1）按照多边形顶点存储顺序遍历该多边形所有顶点,根据辛普森面积公式求出多边形辛普森面积的两倍(2S）。2）从起始顶点开始遍历,获取目标顶点 pi的坐标值,并获取其前一顶点 pi-1和后一顶点 pi+1的坐标;利用辛普森面积公式计算三角形 pi-1pipi+1辛普森面积的两倍(2Si）。3）判断2S与2Si的符号:若2S与2Si同号,即2S＊2Si＞0,则目标顶点 pi为凸点;若2S与2Si异号,即2S＊2Si＜0,则目标顶点 pi为凹点。4）获取下一个目标顶点,转至步骤2。当所有顶点已遍历结束,退出程序。

在上述过程中,通过判断多边形辛普森面积 S的符号得到多边形的方向。考虑到多边形的方向对顶点的凹凸性并无影响,因此算法中省略多边形方向的判断,直接使用2S与2Si的乘积符号得到顶点的凹凸性。这就避免了由于坐标系不一致(如 X坐标轴与 Y坐标轴换位）或初始多边形的方向不同带来的预处理过程,增强了算法的适应性。

2.4 复杂多边形中算法有效性验证

区别于现有的典型识别算法,基于辛普森面积的顶点凹凸性识别算法对复杂多边形同样有效,其理论验证过程如下。

首先,将辛普森面积计算公式推广到复杂多边形的面积计算中。按照辛普森面积公式的定义,复杂多边形的辛普森面积应表示为组成多边形的所有边界弧段上顶点与 X轴或 Y轴组成的梯形面积的代数和。则图4中复杂多边形的辛普森面积为:

由2.1节可知,复杂多边形中“洞”弧段的存储方向与外部多边形的弧段方向相反。因此,“洞”弧段构成的简单多边形的辛普森面积与外部简单多边形的辛普森面积符号不一致,即有 S(papbpc）×S (p1p2…pn）＜0,则:

即该复杂多边形的面积为外部多边形的几何面积扣除“洞”的几何面积。因此,辛普森公式对复杂多边形成立。

图4 复杂多边形辛普森面积示意Fig.4 An example of complex polygon

设一复杂多边形的辛普森面积为 S,其内部“洞”弧段对应的简单多边形的辛普森面积为 S洞。由于复杂多边形内部的“洞”弧段与外边界弧段的方向相反,而外边界弧段的方向决定了该复杂多边形的辛普森面积正负性,则 S＊S洞＜0。若 Sk为“洞”弧段对应的简单多边形上的凸顶点,则 Sk＊S洞＞0。由上面两式得Sk＊S＜0,即“洞”弧段对应的简单多边形的凸顶点为该复杂多边形的凹顶点。同理可得,“洞”弧段对应的简单多边形的凹顶点为该复杂多边形的凸顶点。

综上可知,该算法对复杂多边形的顶点凹凸性识别同样有效。

3 结语

本文提出了基于辛普森面积的多边形顶点凹凸性识别算法,利用多边形中待判断顶点与其相邻两顶点所构成三角形的辛普森面积与整个多边形的辛普森面积的符号异同来判断顶点凹凸性,避免了对多边形自身方向的判断,从而避免了由于坐标系统不一致(如 X轴、Y轴位置交换）和多边形方向变化带来的预处理过程,增强了算法的适应性。该算法时间复杂度为O(n）,计算效率相对较高,可为图斑化简、点线空间位置判断等方面[9,10]的应用提供参考。该算法对复杂多边形的凹凸性识别同样有效。

[1] 刘晓平,吴磊.简单多边形方向及顶点凹凸性的快速判定[J].工程图学学报,2005,26(4）:124-129.

[2] 赵军,张桂梅,曲仕茹.利用极点顺序的多边形顶点凹凸性判别算法[J].工程图学学报,2007,28(1）:55-59.

[3] FEITO F R,TORRESJ C,URENA A.Orientation,simp licity, and inclusion test for planar polygons[J].Computers&Graphics,1995,19(4）:595-600.

[4] 汪学明.多边形顶点凸凹性识别算法的研究与实现[J].计算机应用,2005,25(8）:1787-1788.

[5] 庞明勇,卢章平.基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法[J].工程图学学报,2004(3）:73-77.

[6] 刘润涛.任意多边形顶点凸、凹性判别的简捷算法[J].软件学报,2002,13(7）:1309-1312.

[7] 朱德海,严泰来,杨永侠.土地管理信息系统[M].北京:中国农业大学出版社,2000.

[8] 李建林.面积平衡约束下的土地利用数据综合方法研究[D].中国农业大学,2008.

[9] 宋晓眉,张晓东,李健林.一种高准确度的约束Delaunay三角网生成算法研究[J].地理与地理信息科学,2009,25(1）:99-102.

[10] 李健林,朱德海,宋晓眉,等.一种基于面积平衡的图斑化简算法[J].地理与地理信息科学,2009,25(1）:103-106.

An Algor ithm for Identifying Convex-Concave Vertices of Polygon Based on Simpson Formula

CHEN Ya-ting,YAN Tai-lai,ZHU De-hai
(College of Inform ation and Electrical Engineering,China A griculture University,Beijing 100083,China）

The convex-concave quality of vertices is an important character of polygon,w hich isw ildly used in cartographic generalization,pattern recognition and so on.To identify convex-concave verticesof polygon,an algorithm is p roposed in this paper w hich makes use of Simpson fo rmula.Compared w ith o ther similar algo rithm s,it can identify convex-concave vertices efficiently w ith better app lication adap tability.Furthermo re,it is p roved to be effective in identifying convex-concave vertices of comp lex polygons as well.

Simpson formula;convexity-concavity of vertices;complex polygon;direction of polygon

TP301.6

A

1672-0504(2010）06-0028-03

2010-03-16;

2010-06-01

北京市第二次土地调查技术实施细则编写项目

陈亚婷(1986-）,女,博士研究生,研究方向为GIS技术在国土资源管理方面的应用。E-mail:comeon_cyt@126.com