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

1 概述

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

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

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

2 理論基礎

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

多邊形數(shù)據(jù)類型應用較廣泛，其基礎組織結(jié)構、拓撲關系、計算方法等已有較多研究。為了后續(xù)闡述方便，首先給出 3 個概念的描述與說明：

(1)節(jié)點(Vertex)：即坐標點，一般由二維(或多維)坐標值構成，表示平面(或多維空間)中的一個相對位置，是弧段的基本組成元素。

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

(3)多邊形(Polygon)：由邊界弧段構成的面狀地理實體的表達，只由一條弧段構成的被稱作簡單多邊形，由多條弧段構成的被稱作復雜多邊形(或復合多邊形)。

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