一種改進(jìn)的多邊形數(shù)據(jù)內(nèi)點(diǎn)自動(dòng)生成算法

1 概述

在地理信息系統(tǒng)中，多邊形數(shù)據(jù)經(jīng)常被用來表達(dá)面狀分布的地理要素，如行政區(qū)劃圖、土壤分布圖、湖泊、土地利用圖等。在面狀空間實(shí)體拓?fù)潢P(guān)系中，有學(xué)者指出閉合邊界包含關(guān)系的確定是一個(gè)重要步驟[1]。而閉合邊界包含關(guān)系的確定是一個(gè)比較復(fù)雜和耗時(shí)的過程，主要應(yīng)用圖形學(xué)的閉合邊界包含關(guān)系判定準(zhǔn)則[2]，即對(duì)于任意多邊形 P1 和 P2，如果 P1 上有任意一點(diǎn)位于 P2 的內(nèi)部，則 P1 被 P2 所包含，將多邊形關(guān)系判定轉(zhuǎn)變?yōu)槎噙呅蝺?nèi)點(diǎn)關(guān)系判定，因此，多邊形數(shù)據(jù)內(nèi)點(diǎn)的自動(dòng)生成具有重要意義。

目前在進(jìn)行多邊形數(shù)據(jù)內(nèi)點(diǎn)的自動(dòng)生成時(shí)，主要應(yīng)用基于最小外切矩形 (Minimum Bounding Rectangle, MBR)[3]的內(nèi)點(diǎn)自動(dòng)生成算法[1]。該算法思路清晰，且可以用于簡(jiǎn)單和復(fù)雜多邊形的處理，但在一些奇異情況下容易導(dǎo)致算法失效。

本文提出一種有效的改進(jìn)多邊形數(shù)據(jù)內(nèi)點(diǎn)自動(dòng)生成算法，通過采用不確定性區(qū)間和相交區(qū)間的處理方法對(duì)奇異情況進(jìn)行統(tǒng)一修正，并對(duì)算法健壯性進(jìn)行分析和實(shí)驗(yàn)驗(yàn)證。

2 理論基礎(chǔ)

2.1 多邊形數(shù)據(jù)模型

多邊形數(shù)據(jù)類型應(yīng)用較廣泛，其基礎(chǔ)組織結(jié)構(gòu)、拓?fù)潢P(guān)系、計(jì)算方法等已有較多研究。為了后續(xù)闡述方便，首先給出 3 個(gè)概念的描述與說明：

(1)節(jié)點(diǎn)(Vertex)：即坐標(biāo)點(diǎn)，一般由二維(或多維)坐標(biāo)值構(gòu)成，表示平面(或多維空間)中的一個(gè)相對(duì)位置，是弧段的基本組成元素。

(2)弧段(Arc)：由多個(gè)節(jié)點(diǎn)順次連接而成的有向線段，線段方向即通過節(jié)點(diǎn)連接順序表達(dá)，是多邊形邊界的重要組成。

(3)多邊形(Polygon)：由邊界弧段構(gòu)成的面狀地理實(shí)體的表達(dá)，只由一條弧段構(gòu)成的被稱作簡(jiǎn)單多邊形，由多條弧段構(gòu)成的被稱作復(fù)雜多邊形(或復(fù)合多邊形)。

更多內(nèi)容請(qǐng)查看pdf