陳亞婷,嚴(yán)泰來(lái),朱德海

(中國(guó)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院,北京 100083）

基于辛普森面積的多邊形凹凸性識(shí)別算法

陳亞婷,嚴(yán)泰來(lái),朱德海

(中國(guó)農(nóng)業(yè)大學(xué)信息與電氣工程學(xué)院,北京 100083）

多邊形頂點(diǎn)的凹凸性是其重要的形狀特征,常被應(yīng)用于制圖綜合、模式識(shí)別等方面。該文利用多邊形特有的面積屬性,將辛普森面積計(jì)算公式引入多邊形頂點(diǎn)的凹凸性識(shí)別算法中,通過(guò)計(jì)算多邊形中待判斷頂點(diǎn)與其相鄰兩頂點(diǎn)所構(gòu)成三角形的辛普森面積與整個(gè)多邊形的辛普森面積的符號(hào)異同來(lái)判斷頂點(diǎn)凹凸性。經(jīng)推算證明,該算法對(duì)于復(fù)雜多邊形的頂點(diǎn)凹凸性識(shí)別同樣有效。

辛普森面積計(jì)算公式;頂點(diǎn)凹凸性;復(fù)雜多邊形;多邊形方向

為了詳細(xì)了解各種地物的信息,常采用大比例尺進(jìn)行調(diào)查成圖;但在不同領(lǐng)域使用地圖時(shí),對(duì)地圖詳細(xì)度的要求不一致。例如,在分析一個(gè)地區(qū)的總體地域特征時(shí),需要大范圍瀏覽地物,以把握整體特性;通常的做法是以大比例尺數(shù)據(jù)作為數(shù)據(jù)源,過(guò)濾掉冗余信息,保留地物特征,形成概要的小比例尺地圖。在該過(guò)程中,對(duì)多邊形進(jìn)行特征提取是最關(guān)鍵的步驟。凹凸性是多邊形的重要形狀特征,如能預(yù)先確定多邊形的凹凸性,可使問(wèn)題簡(jiǎn)化。

現(xiàn)有的多邊形頂點(diǎn)凹凸性識(shí)別法有角度法、叉積法、拓?fù)溆成浞ㄒ约盎谶呄蛄啃甭时容^的方法等[1-6]。其中最基本的算法是角度法,但其計(jì)算效率低,且易出現(xiàn)奇異值。另一典型算法是叉積法,即在判別多邊形方向的前提下,利用多邊形相鄰3點(diǎn)Pi-1、Pi、Pi+1的坐標(biāo)組成的行列式值與零的關(guān)系來(lái)確定 Pi與有向線段 Pi-1Pi+1之間的位置關(guān)系,從而得到頂點(diǎn) Pi的凹凸性。該算法正確率高,但計(jì)算量較大,且不適用于復(fù)雜多邊形。本文利用多邊形特有的面積屬性,提出了基于辛普森面積的多邊形頂點(diǎn)凹凸性識(shí)別算法,利用多邊形3個(gè)連續(xù)頂點(diǎn)構(gòu)成三角形的辛普森面積與整個(gè)多邊形的辛普森面積符號(hào)的異同來(lái)識(shí)別簡(jiǎn)單多邊形的凹凸性。

1 相關(guān)定義

(1）簡(jiǎn)單多邊形:若多邊形由平面上 n個(gè)不同點(diǎn)P1,P2,…,Pn首尾相連構(gòu)成,且滿足任意兩條不相鄰邊都不相交,任意相鄰的三點(diǎn)都不共線,稱該多邊形為簡(jiǎn)單多邊形,其中 P1,P2,…,Pn為其頂點(diǎn)。

(2）復(fù)雜多邊形:若一多邊形由多個(gè)簡(jiǎn)單多邊形組成,且滿足任意兩個(gè)簡(jiǎn)單多邊形邊界不相交,則稱該多邊形為復(fù)雜多邊形,所有組成該復(fù)雜多邊形的簡(jiǎn)單多邊形的頂點(diǎn)稱為該復(fù)雜多邊形頂點(diǎn)。

(3）多邊形的方向:使用辛普森公式計(jì)算多邊形面積,若所得辛普森面積為正,則稱該多邊形方向?yàn)檎较?否則,稱其方向?yàn)樨?fù)方向。

(4）頂點(diǎn)的凹凸性:對(duì)于多邊形某個(gè)頂點(diǎn),若交于該頂點(diǎn)的相鄰兩邊所形成的內(nèi)角(即該多邊形所圍成有界區(qū)域內(nèi)所形成的角）小于180°,稱該頂點(diǎn)為凸點(diǎn);若大于180°,稱其為凹點(diǎn);若等于180°,則稱該頂點(diǎn)不具有凹凸性。

(5）結(jié)點(diǎn):GIS中線的終點(diǎn)、起點(diǎn)和交點(diǎn)稱為結(jié)點(diǎn)。

(6）弧段:GIS中兩個(gè)結(jié)點(diǎn)之間的線段稱為弧段。

2 凹凸性識(shí)別算法原理

凹凸性識(shí)別算法建立在GIS的圖形存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上。基于該數(shù)據(jù)結(jié)構(gòu),將辛普森面積計(jì)算公式應(yīng)用于多邊形和待判斷頂點(diǎn)所在三角形,即可判定頂點(diǎn)的凹凸性。

2.1 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)[7]

GIS中多邊形的存儲(chǔ)使用多邊形-弧線拓?fù)浣Y(jié)構(gòu)定義,即數(shù)據(jù)結(jié)構(gòu)中不直接存儲(chǔ)多邊形頂點(diǎn)坐標(biāo)信息,而是存儲(chǔ)組成該多邊形的弧段。一個(gè)簡(jiǎn)單多邊形由一系列組成其邊界的弧線規(guī)定,復(fù)雜多邊形則由多組弧線構(gòu)成,其中每組弧線定義一個(gè)構(gòu)成該復(fù)雜多邊形的簡(jiǎn)單多邊形。

為了定義多邊形間的拓?fù)溧徑有?每個(gè)弧段從起始結(jié)點(diǎn)到終止結(jié)點(diǎn)方向的左側(cè)的多邊形稱為左多邊形,右側(cè)的多邊形稱為右多邊形。對(duì)于復(fù)雜多邊形,在遍歷弧段時(shí)要求該多邊形區(qū)域是所有組成其弧段的同側(cè)多邊形,這就要求構(gòu)成“洞”的弧段方向與外邊界的弧段方向相反。如圖1所示,多邊形區(qū)域同是構(gòu)成其兩個(gè)弧段的右多邊形,“洞”弧段的方向與外邊界弧段的方向相反。

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

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

辛普森面積計(jì)算公式的基本思想是:按照多邊形的頂點(diǎn)順序依次求出多邊形所有邊與 X軸或者Y軸組成的梯形面積,然后求其代數(shù)和(圖2）。一個(gè)由n個(gè)頂點(diǎn)組成的多邊形的辛普森面積為:

由文獻(xiàn)[8]可知,當(dāng)多邊形頂點(diǎn)呈順時(shí)針?lè)较蚺帕袝r(shí)所得辛普森面積為正值,逆時(shí)針?lè)较蚺帕袝r(shí)辛普森面積為負(fù)值,而多邊形幾何面積為其辛普森面積的絕對(duì)值。

圖2 辛普森面積計(jì)算原理示意Fig.2 The illustration of Simpson formula

2.3 基于簡(jiǎn)單多邊形的凹凸性識(shí)別算法

通過(guò)論證可得到如下推理:無(wú)論多邊形方向的正負(fù)性如何,其頂點(diǎn)與前后兩頂點(diǎn)構(gòu)成三角形的辛普森面積與多邊形的辛普森面積符號(hào)相同時(shí),該頂點(diǎn)必為凸點(diǎn);反之,則該頂點(diǎn)必為凹點(diǎn)。

推理的證明過(guò)程如下:

多邊形 p1p2…pn的辛普森面積為:

當(dāng)2≤i≤n-1時(shí),三角形 pi-1pipi+1的辛普森面積為:

去除目標(biāo)頂點(diǎn) pi后的多邊形 p1 p2…pi-1 pi+1…pn的辛普森面積為:

當(dāng)i=1或i=n時(shí),令 p0=pn,pn+1=p1,易證上述結(jié)論仍成立,即有:

即多邊形 p1p2…pn的幾何面積為多邊形 p1p2…pi-1pi+1…pn與三角形 pi-1pipi+1的幾何面積之和,如圖3a所示,則目標(biāo)頂點(diǎn) pi為凸點(diǎn)。

即多邊形 p1p2…pn的幾何面積為多邊形 p1p2…pi-1pi+1…pn與三角形 pi-1pipi+1的幾何面積之差,如圖3b所示,則目標(biāo)頂點(diǎn) pi為凹點(diǎn)。

圖3 頂點(diǎn)凹凸性面積原理示意Fig.3 The relationship between convex-concave feature and area

根據(jù)該推理,多邊形頂點(diǎn)的凹凸性可通過(guò)判斷多邊形與頂點(diǎn)三角形的辛普森面積符號(hào)是否一致得出。以簡(jiǎn)單多邊形 p1p2…pn為例,令 p0=pn,pn+1=p1。基于辛普森面積的頂點(diǎn)凹凸性識(shí)別算法的實(shí)現(xiàn)步驟為:1）按照多邊形頂點(diǎn)存儲(chǔ)順序遍歷該多邊形所有頂點(diǎn),根據(jù)辛普森面積公式求出多邊形辛普森面積的兩倍(2S）。2）從起始頂點(diǎn)開(kāi)始遍歷,獲取目標(biāo)頂點(diǎn) pi的坐標(biāo)值,并獲取其前一頂點(diǎn) pi-1和后一頂點(diǎn) pi+1的坐標(biāo);利用辛普森面積公式計(jì)算三角形 pi-1pipi+1辛普森面積的兩倍(2Si）。3）判斷2S與2Si的符號(hào):若2S與2Si同號(hào),即2S＊2Si＞0,則目標(biāo)頂點(diǎn) pi為凸點(diǎn);若2S與2Si異號(hào),即2S＊2Si＜0,則目標(biāo)頂點(diǎn) pi為凹點(diǎn)。4）獲取下一個(gè)目標(biāo)頂點(diǎn),轉(zhuǎn)至步驟2。當(dāng)所有頂點(diǎn)已遍歷結(jié)束,退出程序。

在上述過(guò)程中,通過(guò)判斷多邊形辛普森面積 S的符號(hào)得到多邊形的方向?？紤]到多邊形的方向?qū)旤c(diǎn)的凹凸性并無(wú)影響,因此算法中省略多邊形方向的判斷,直接使用2S與2Si的乘積符號(hào)得到頂點(diǎn)的凹凸性。這就避免了由于坐標(biāo)系不一致(如 X坐標(biāo)軸與 Y坐標(biāo)軸換位）或初始多邊形的方向不同帶來(lái)的預(yù)處理過(guò)程,增強(qiáng)了算法的適應(yīng)性。

2.4 復(fù)雜多邊形中算法有效性驗(yàn)證

區(qū)別于現(xiàn)有的典型識(shí)別算法,基于辛普森面積的頂點(diǎn)凹凸性識(shí)別算法對(duì)復(fù)雜多邊形同樣有效,其理論驗(yàn)證過(guò)程如下。

首先,將辛普森面積計(jì)算公式推廣到復(fù)雜多邊形的面積計(jì)算中。按照辛普森面積公式的定義,復(fù)雜多邊形的辛普森面積應(yīng)表示為組成多邊形的所有邊界弧段上頂點(diǎn)與 X軸或 Y軸組成的梯形面積的代數(shù)和。則圖4中復(fù)雜多邊形的辛普森面積為:

由2.1節(jié)可知,復(fù)雜多邊形中“洞”弧段的存儲(chǔ)方向與外部多邊形的弧段方向相反。因此,“洞”弧段構(gòu)成的簡(jiǎn)單多邊形的辛普森面積與外部簡(jiǎn)單多邊形的辛普森面積符號(hào)不一致,即有 S(papbpc）×S (p1p2…pn）＜0,則:

即該復(fù)雜多邊形的面積為外部多邊形的幾何面積扣除“洞”的幾何面積。因此,辛普森公式對(duì)復(fù)雜多邊形成立。

圖4 復(fù)雜多邊形辛普森面積示意Fig.4 An example of complex polygon

設(shè)一復(fù)雜多邊形的辛普森面積為 S,其內(nèi)部“洞”弧段對(duì)應(yīng)的簡(jiǎn)單多邊形的辛普森面積為 S洞。由于復(fù)雜多邊形內(nèi)部的“洞”弧段與外邊界弧段的方向相反,而外邊界弧段的方向決定了該復(fù)雜多邊形的辛普森面積正負(fù)性,則 S＊S洞＜0。若 Sk為“洞”弧段對(duì)應(yīng)的簡(jiǎn)單多邊形上的凸頂點(diǎn),則 Sk＊S洞＞0。由上面兩式得Sk＊S＜0,即“洞”弧段對(duì)應(yīng)的簡(jiǎn)單多邊形的凸頂點(diǎn)為該復(fù)雜多邊形的凹頂點(diǎn)。同理可得,“洞”弧段對(duì)應(yīng)的簡(jiǎn)單多邊形的凹頂點(diǎn)為該復(fù)雜多邊形的凸頂點(diǎn)。

綜上可知,該算法對(duì)復(fù)雜多邊形的頂點(diǎn)凹凸性識(shí)別同樣有效。

3 結(jié)語(yǔ)

本文提出了基于辛普森面積的多邊形頂點(diǎn)凹凸性識(shí)別算法,利用多邊形中待判斷頂點(diǎn)與其相鄰兩頂點(diǎn)所構(gòu)成三角形的辛普森面積與整個(gè)多邊形的辛普森面積的符號(hào)異同來(lái)判斷頂點(diǎn)凹凸性,避免了對(duì)多邊形自身方向的判斷,從而避免了由于坐標(biāo)系統(tǒng)不一致(如 X軸、Y軸位置交換）和多邊形方向變化帶來(lái)的預(yù)處理過(guò)程,增強(qiáng)了算法的適應(yīng)性。該算法時(shí)間復(fù)雜度為O(n）,計(jì)算效率相對(duì)較高,可為圖斑化簡(jiǎn)、點(diǎn)線空間位置判斷等方面[9,10]的應(yīng)用提供參考。該算法對(duì)復(fù)雜多邊形的凹凸性識(shí)別同樣有效。

[1] 劉曉平,吳磊.簡(jiǎn)單多邊形方向及頂點(diǎn)凹凸性的快速判定[J].工程圖學(xué)學(xué)報(bào),2005,26(4）:124-129.

[2] 趙軍,張桂梅,曲仕茹.利用極點(diǎn)順序的多邊形頂點(diǎn)凹凸性判別算法[J].工程圖學(xué)學(xué)報(bào),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] 汪學(xué)明.多邊形頂點(diǎn)凸凹性識(shí)別算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2005,25(8）:1787-1788.

[5] 龐明勇,盧章平.基于邊向量斜率比較的簡(jiǎn)單多邊形頂點(diǎn)凸凹性快速判別算法[J].工程圖學(xué)學(xué)報(bào),2004(3）:73-77.

[6] 劉潤(rùn)濤.任意多邊形頂點(diǎn)凸、凹性判別的簡(jiǎn)捷算法[J].軟件學(xué)報(bào),2002,13(7）:1309-1312.

[7] 朱德海,嚴(yán)泰來(lái),楊永俠.土地管理信息系統(tǒng)[M].北京:中國(guó)農(nóng)業(yè)大學(xué)出版社,2000.

[8] 李建林.面積平衡約束下的土地利用數(shù)據(jù)綜合方法研究[D].中國(guó)農(nóng)業(yè)大學(xué),2008.

[9] 宋曉眉,張曉東,李健林.一種高準(zhǔn)確度的約束Delaunay三角網(wǎng)生成算法研究[J].地理與地理信息科學(xué),2009,25(1）:99-102.

[10] 李健林,朱德海,宋曉眉,等.一種基于面積平衡的圖斑化簡(jiǎn)算法[J].地理與地理信息科學(xué),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

北京市第二次土地調(diào)查技術(shù)實(shí)施細(xì)則編寫(xiě)項(xiàng)目

陳亞婷(1986-）,女,博士研究生,研究方向?yàn)镚IS技術(shù)在國(guó)土資源管理方面的應(yīng)用。E-mail:comeon_cyt@126.com