一種基于柵格方法的空間謂詞判斷方法及其系統(tǒng)

1、一種基于柵格方法的空間謂詞判斷方法及其系統(tǒng) 董 慧* * ，程振林*，方金云*， 趙紅超* （* 中國科學(xué)院計算技術(shù)研究所 北京市海淀區(qū)科學(xué)院南路 6 號 ） （* 中國科學(xué)院研究生院 北京市石景山區(qū)玉泉路 19 號（甲） ） 摘要：地理信息獲得了越來越廣泛與深入的應(yīng)用?？臻g分析是地理信息系統(tǒng)平臺最核 心的計算之一。矢量方法是面向物體的描述，物體間的幾何關(guān)系隱含，關(guān)系判斷需要基于 計算幾何算法定位、分析和檢索，時間與空間復(fù)雜度較高。為避免其缺點，本文提出了基 于柵格的空間謂詞算法實現(xiàn)框架。此算法基于亞像素精度，可以較準(zhǔn)確記錄邊界柵格的覆 蓋面積，通過判斷兩個圖層相應(yīng)柵格的覆蓋面積，即可得出空間

2、關(guān)系。此方法的正確率大 大高于四色柵格簽名（4CRS）。同時，柵格索引中保存了要素屬性信息等，可以為空間謂 詞判斷提供更有用的結(jié)果信息。 關(guān)鍵詞：空間謂詞，柵格化方法，4CRS（four color raster signature），亞像素精度 一介紹 隨著 GIS 自身的發(fā)展和經(jīng)濟與社會的信息化，GIS 開始融入信息技術(shù)的主流。由于GIS 技術(shù)能較好地解決基于時空框架的數(shù)據(jù)建模問題，填補了傳統(tǒng)信息技術(shù)在這方面的空白， 逐步成為信息技術(shù)的核心支撐技術(shù)1。 基于 Web 的地圖應(yīng)用使得 GIS 的用戶從專業(yè)人士迅速擴大到公眾。以Web 編程接口的 形式提供空間信息服務(wù)成為GIS 與其他的業(yè)務(wù)信

3、息系統(tǒng)進(jìn)行應(yīng)用整合的重要途徑，這為GIS 應(yīng)用開辟了更廣闊的應(yīng)用范圍和場景。但是，基于Internet 的 GIS 的體系結(jié)構(gòu)決定了大量 的業(yè)務(wù)邏輯集中在服務(wù)器端。滿足眾多用戶（包括Web 服務(wù)客戶端）的訪問并保證服務(wù)質(zhì) 量，給后端服務(wù)器的性能、可擴展性提出了更高的要求。 空間謂詞是比較兩個空間對象并返回一個布爾變量值作為結(jié)果，它表明了存在于兩個 空間對象之間特殊的關(guān)系。如：是否相交、是否相互包含等?？臻g謂詞是 GIS 的核心，是 GIS 區(qū)別于一般的信息系統(tǒng)、CAD（計算設(shè)計輔助設(shè)計）或者電子地圖系統(tǒng)的主要標(biāo)志之一。 OGC(Open Geospatial Consortium，開放地理信息

4、聯(lián)盟)的 web 要素服務(wù)（Web Feature Service）規(guī)范中的空間過濾器是通過空間謂詞方式獲取要素數(shù)據(jù)的有力方式，規(guī)范中提出 了 Disjoint/ Intersect、Equals、Within/Contains、Overlaps、BBOX 等多種空間謂詞過 濾器。 空間謂詞，配合空間數(shù)據(jù)的屬性信息，能提供強大、豐富的空間數(shù)據(jù)查詢功能?？臻g 謂詞以及空間分析功能具有算法復(fù)雜、計算密集等特點，如何在Web 上提供空間謂詞的功 能，在學(xué)術(shù)研究與工程實踐上，都具有重要的意義，能促進(jìn)GIS 應(yīng)用的 Web 遷移并促進(jìn) GIS 應(yīng)用與其他應(yīng)用的融合。隨著網(wǎng)絡(luò)地圖服務(wù)的流行，如何在網(wǎng)絡(luò)地圖

5、服務(wù)器上提供空間謂 詞功能成為需要解決的問題。 一種常見的空間謂詞判斷方法是利用計算幾何來實現(xiàn)。作為計算機科學(xué)的一個分支， 計算幾何主要研究解決幾何問題的算法。常見的做法是針對兩個多邊形進(jìn)行，在大量的多 邊形計算面前無能為力。如果采用“暴力”算法，通過反復(fù)調(diào)用兩個多邊形空間謂詞的算 法來完成，則算法實現(xiàn)計算復(fù)雜度高，實用性差。如基于出入點判別的空間謂詞實現(xiàn)方法， 如何確定交點的進(jìn)點、出點屬性在實際的圖形中會遇到眾多的特殊情況。特別是在發(fā)生了 線段與線段交在端點、線段與線段重疊的情況下，如何區(qū)分交點的出點、入點情況非常復(fù) 雜導(dǎo)致效率降低。這類做法中采用的線段求交算法一般是采用平面掃描算法，優(yōu)點是

6、結(jié)果 比較精確，缺點是由于要進(jìn)行頻繁的坐標(biāo)排序、角度計算等操作，計算量大2。 為解決上述問題，本文提供了一種基于柵格方法的空間謂詞判斷方法及其系統(tǒng)，能夠 減少計算量，提高計算效率。 四色柵格簽名（four color raster signature -4CRS)34可以實現(xiàn)空間關(guān)系的判斷，但 是 4CRS 結(jié)果不夠精確，只能以四種柵格屬性區(qū)分柵格面積-空、滿、強（一半以上） 、弱 （一半以下） ，只能判斷出強*強是確定相交的，而強*弱、弱*強、弱*弱則都是不確定的結(jié) 果，還需要精確計算。在計算近似面積、置信度區(qū)間等都是用數(shù)學(xué)期望和概率等公式來估 計，而真實數(shù)據(jù)可能并不符合這種規(guī)律。 本文使用

7、的基于亞像素精度的方法能準(zhǔn)確記錄邊界格子的面積，因此可以根據(jù)兩個對 象占用的單元格的面積來確定是否相交。如同一個位置的柵格，第一個圖層占有此柵格為 49%，第二個圖層為 52%，相加100%,所以確定相交，而 4CRS 則不能確定。而且，4CRS 只能實現(xiàn)兩個多邊形的判斷，而不能處理多個多邊形的圖層。而本文采用的方法不但能精 確記錄柵格面積百分比，提高結(jié)果的準(zhǔn)確性，并能把百分比和圖層屬性信息等都保存下來， 給用戶返回更多有效的結(jié)果信息（結(jié)果多邊形的 ID 號等） 。 二算法框架 整個算法分為兩步：柵格索引生成和基于索引的柵格空間謂詞實現(xiàn)。 整個柵格索引生成過程算法框架如圖 1 所示。首先，對地

8、理要素的矢量點進(jìn)行坐標(biāo)轉(zhuǎn) 換，便于利用亞像素精度進(jìn)行后續(xù)的計算。然后，進(jìn)行輪廓掃描和繪制控制器計算填充單 元跨段，在此過程中計算出圖形輪廓處的該圖形占柵格單元的面積的百分比，該百分比稱 為柵格單元對應(yīng)于該圖形的實際占用面積。最后，將要素 ID 信息和實際占用面積信息存入 以像素為索引的結(jié)構(gòu)里。 坐標(biāo)轉(zhuǎn)換通道 輪廓掃描 繪制控制器計算 填充單元及跨段 水平掃描線填充 單元及跨段 要素信息（柵格ID號、面積百分比等）信 息按掃描線要求存入緩存 輸入矢量要素 生成底圖索引 圖1. 步驟一的算法框架 經(jīng)過底圖索引生成這個步驟之后，即完成了柵格化過程，以柵格矩陣形式存儲，其中 坐標(biāo)值為索引，所屬的多邊形

9、 ID 號和所占的柵格面積百分比等為圖層信息，以文件形式 保存下來。 這樣，兩個圖層的空間謂詞判斷的時候，只需要找到同一柵格，對其面積等進(jìn)行判斷， 從而獲得符合條件的多邊形 ID 號返回結(jié)果。示意圖如圖 2。 圖 2 步驟二的流程圖 三基于柵格方法的空間謂詞實現(xiàn) 柵格索引生成 柵格索引生成部分，用于對于輸入的圖層生成對應(yīng)的柵格底圖，柵格底圖的柵格單元 以壓蓋所述柵格單元的圖層的圖形的要素 ID 為要素索引，柵格單元以坐標(biāo)值為位置索引， 每個柵格單元具有對其壓蓋的圖形在所述柵格單元的實際占用面積的比值。 圖 3 (a) 地理要素的幾何表示 (b) 柵格近似 實現(xiàn)圖片像素與矢量點關(guān)聯(lián)，具體指在繪制

10、地理要素的圖形同時，生成一張與該圖形 匹配的柵格底圖，該柵格底圖就是與該圖形對應(yīng)的索引圖，如圖 3 所示。柵格底圖的每個 柵格單元都對應(yīng)了該地理要素的屬性信息內(nèi)容，例如地理要素的要素 ID 號等，以要素 ID 號為柵格單元的要素索引。因此完全不存在搜索存在重疊區(qū)域這種情況?？勺鳛樗饕焖?提取要素信息，也是實現(xiàn)下述空間謂詞的基礎(chǔ)。 生成柵格索引需要以下步驟： （1）輸入矢量方式表示的圖層中地理要素的圖形的矢量點，按顯示屏幕的分辨率對地 理要素的矢量點坐標(biāo)進(jìn)行坐標(biāo)轉(zhuǎn)換，按顯示屏幕的像素點進(jìn)行柵格劃分，柵格單元以坐標(biāo) 值為位置索引，柵格單元以對其壓蓋的圖形的要素ID 為要素索引。 如果沒有圖形對柵

11、格單元進(jìn)行壓蓋，則柵格單元的要素索引和實際占用面積的信息都 為初始化時的缺省值。坐標(biāo)值是根據(jù)實際地理坐標(biāo)投影到屏幕坐標(biāo)的柵格行列號。 在本文中，將 double 類型的矢量點坐標(biāo)都乘以256，相當(dāng)于將該坐標(biāo)的二進(jìn)制表示左 移 8 位。這種坐標(biāo)轉(zhuǎn)換的優(yōu)點是考慮了小數(shù)部分對像素的柵格單元權(quán)值(cover)的影響，便 于利用亞像素精度進(jìn)行后續(xù)的計算。 （2）對圖層中的圖形進(jìn)行輪廓掃描，對于每個圖形，按如下公式計算圖形的輪廓線經(jīng) 過的每一柵格單元的權(quán)值和覆蓋面積5， cov21erfyfy （1） (21) covareafxfxer （2） 其中，（fx1，fy1）為經(jīng)過該柵格單元的輪廓的線段起始點

12、的小數(shù)坐標(biāo)部分， （fx2，fy2）為經(jīng)過該柵格單元的輪廓的線段終止點的小數(shù)坐標(biāo)部分，cover 為權(quán)值，area 為面積。 運用了亞像素精度（subpixel accuracy）的布蘭森漢姆（Bresenham）6生成直線算 法進(jìn)行輪廓所描，Bresenham 生成直線算法是一種基于誤差判別式來生成直線的方法。與傳 統(tǒng) Bresenham 所不同的是，該算法利用誤差判別選擇像素的過程是基于亞像素的，把一個 像素分成 NN 個小像素，例如，將單位柵格平均分成了256256 個子像素。 （3）對于每個圖形，繪制控制器遍歷圖形的輪廓經(jīng)過的柵格單元，依據(jù)柵格單元的覆 蓋面積判斷所述柵格單元是否被圖形

13、完全填充，對完全填充的柵格單元和未完全填充的柵 格單元分別進(jìn)行標(biāo)記，將輪廓內(nèi)的柵格單元進(jìn)行跨度填充，將這些柵格單元標(biāo)記為完全填 充。 首先，繪制控制器將輪廓經(jīng)過的所有柵格單元，例如上述計算的A 和 B 等整數(shù)坐標(biāo)屬 于此處的單元格，進(jìn)行排序，將 X 坐標(biāo)相同的點按照 Y 坐標(biāo)由小到大排序。然后，繪制控 制器按照行掃描順序，掃描順序指按照 X 坐標(biāo)由小到大掃描每行，從最小行到最大行逐行 掃描，利用圖形中每個掃描柵格單元的 area 進(jìn)行判斷柵格單元是否完全被圖形填充，對于 未完全填充的柵格單元，進(jìn)行標(biāo)記，例如利用 add_cell（）函數(shù)進(jìn)行標(biāo)記，對于完全填充 的柵格進(jìn)行標(biāo)記，例如利用 add_

14、span（）函數(shù)進(jìn)行標(biāo)記。未完全填充的柵格指圖中所計算 的 area 沒有完全覆蓋當(dāng)前柵格，如圖4 所示。 圖 4 area 和 cover 示意圖 由于 cover 有正負(fù)，所以在掃描每一行的時候都將所有輪廓的單元格的cover 相加， 因為圖形的輪廓是閉合的，所以當(dāng)該跨段標(biāo)記完以后遍歷的所有柵格單元的cover 加和會 為 0，通過這樣的判斷，能夠自動找到哪部分需要填充，哪部分不需要填充。 （4）將完全填充的柵格單元的圖形在柵格單元的實際占用面積的比值設(shè)置為 1；對于 未完全填充的柵格單元，根據(jù)所述柵格單元的權(quán)值和覆蓋面積計算所述柵格單元的圖形在 柵格單元的實際占用面積的比值；保存柵格單元

15、的位置索引、要素索引和實際占用面積的 比值，進(jìn)而生成所述圖形對應(yīng)的柵格底圖。 輪廓掃描的時候保存的柵格單元的 area 并非是有效面積，因為不知道圖形的內(nèi)部還是 外部。內(nèi)部還是外部同輪廓的走向相關(guān)，由圖4 可以看出，area 是由輪廓跟柵格單元的左 側(cè)圍成的面積，而當(dāng)輪廓的走向是順時針時，真正的面積應(yīng)該是柵格單元的面積減去area 得到的，剩余一部分的面積，所以真正的輪廓的柵格單元實際被圖形包含的面積需要在繪 制的時候才能確定。 計算每個未完全填充的柵格單元的實際面積。確定出一個圖形輪廓所經(jīng)過的每個柵格 單元,然后再計算每個柵格單元中有多少面積是落在圖形內(nèi),把整數(shù)坐標(biāo)相同的柵格單元的 area

16、 和 cover 累加，然后通過 cover 和 area 共同作用計算出輪廓經(jīng)過的柵格單元實際被圖 形占用面積，用 alpha 表示。 輪廓走向由 cover 記錄，cover 正負(fù)值表示不同的輪廓走向，順時針或逆時針，所 以真正需要計算的屬于圖形內(nèi)部的面積是需要這兩個變量共同計算得出，通過 area 和 cover 共同計算出 alpha。 alpha=cover-=cover（1-） 256256 area 256256 2fx1fx （3） 這個值越大，則代表圖形壓蓋的格子百分比越多。 經(jīng)過以上步驟，能更好的利用已有的矢量數(shù)據(jù)柵格化近似，提高處理速度，也就是完 成了柵格化過程，以柵格矩

17、陣形式存儲，其中坐標(biāo)值為位置索引，屬性信息等為圖層信息， 以文件形式保存下來。 基于索引的柵格空間謂詞實現(xiàn) 對于兩個待比較的地理要素的圖層，兩個圖層的柵格底圖中坐標(biāo)相同的柵格單元相互 對應(yīng)，將相對應(yīng)的兩個柵格單元的實際占用面積的信息進(jìn)行比較，得出所述兩個圖層的空 間謂詞判斷結(jié)果。 對于遍歷的柵格單元，計算所述柵格單元對應(yīng)于兩個圖層的實際占用面積的比值的和， 判斷所述和是否大于 100%，如果是，停止遍歷，空間謂詞判斷結(jié)果為兩個圖層相交。并且 在得出空間謂詞判斷結(jié)果后還用于返回所述柵格單元在兩個柵格底圖中對應(yīng)的要素 ID。 首先，分別確定兩個待比較的圖層的外包，以兩個圖層的外包的相交區(qū)域為遍歷區(qū)

18、域； 對遍歷區(qū)域中的柵格單元進(jìn)行遍歷。在遍歷的所有柵格單元的所述實際占用面積的比值的 和都不大于 1 時，按如下公式計算平均期望值， count cellareacellarea 21 （4） 其中，為遍歷的柵格單元對應(yīng)于一個圖層的實際占用面積的比值， 1cellarea 為所述柵格單元對應(yīng)于另一個圖層的實際占用面積的比值，為遍歷的柵 2cellarea count 格單元的數(shù)量； 如果平均期望值大于預(yù)設(shè)的條件閥值，則空間謂詞判斷結(jié)果為兩個圖層相交。 兩個待比較的圖層分別為A 和 B，判斷兩個圖層是否有圖形相交（overlap），預(yù)設(shè)的 期望閥值為 60%。 具體的說：在兩個圖層中輪廓的交作為

19、新輪廓，在新外包里掃描線遍歷，如果某個柵 格單元在兩個圖層中都有被圖形壓蓋，則進(jìn)行如下對比：取出兩個圖層中此柵格單元對應(yīng) 的信息，設(shè) cellarea1、id1 為 A 圖層的柵格單元的實際占用面積的比值和當(dāng)前對應(yīng)圖形的 要素 ID 號;cellarea2、id2 為 B 圖層的柵格單元的實際占用面積的比值和當(dāng)前圖形的要素 ID 號；如果 cellarea1+cellarea2=100%，說明兩個圖層在此柵格中相交了，將相交對 （id1 和 id2）存入結(jié)果集。所有的柵格單元都不滿足cellarea1+cellarea2=100%，則將 期望值 cellarea1cellarea2 依次加到

20、value 值里，count 記錄共加入了多少次柵格。最 終兩個圖層可能相交的平均期望值即為value/count，這個值是個百分比，如果得出60%， 則說明兩個圖層有 60%的可能性相交。 判斷兩個圖層間是否有包含關(guān)系（contain）的圖形時，確定包含圖層和被包含圖層， 對于包含圖層中的每個圖形，比較所述圖形和被包含圖層中每個圖形的在同一柵格單元的 實際占用面積比值，將被包含圖層中實際占用面積的比值都不大于所述圖形的實際占用面 積比值的圖形為所述圖形的包含圖形。對于包含圖層的每個圖形，以被包含圖層中的所有 圖形為所述圖形的比較圖形，并組成結(jié)果集。 設(shè)兩個圖層分別為 A 和 B，判斷是否 A

21、 包含 B 的多邊形，如果是，返回 B 中被 A 包 含的多邊形信息。如圖 5 中，A 圖層為粗框的多邊形，B 圖層包含 1、2、3 和 4 號多邊形。 分為三個步驟： （1）先用以上方法獲得在 A 圖層之內(nèi)的所有 B 圖層的結(jié)果集 result1（2、3 和 4） ，即 B 圖層的多邊形的每個格子的面積均小于或者等于 A 圖層的格子面積（1 能排除，因為在 1 和多邊形邊相交部分 1 的格子面積大于圖層 A 的） ； （2）取出 result1 的所有多邊形的外包與 A 圖層的外包進(jìn)行對比，如果超出則排除掉， 剩余的結(jié)果集加到 result2 中（4 能排除掉，剩余 2 和 3） ； （3）

22、把 result2 的所有多邊形分別與 A 圖層多邊形進(jìn)行對比，即把外包當(dāng)作一個多邊 形來跟 A 的圖層多邊形對比格子面積，如果均小于或者等于 A 的，則加入到 result3 中（3 排除掉，剩余 2） ； Result3 則為最終結(jié)果集，即落在 A 圖層多邊形內(nèi)的所有 B 圖層的多邊形，即 A 圖層 包含 B 圖層中的 2 號多邊形。 2 3 1 4 A 圖 5 contain 算子的示意圖 四總結(jié)與展望 本文通過將地理要素的屬性信息與柵格像素關(guān)聯(lián)，面向網(wǎng)絡(luò)地圖服務(wù)，避免了傳統(tǒng)計 算幾何算法復(fù)雜度高的缺點，可以提供更好的性能，幫助服務(wù)器支持更多的并發(fā)用戶數(shù)量。 柵格圖像不僅是矢量數(shù)據(jù)的可視化表達(dá)，更可視為是矢量數(shù)據(jù)的柵格化近似 （approximation），這種近似精度遠(yuǎn)高于最小外包矩形（MBR）等表達(dá)形式，可以作為空 間關(guān)系謂詞的實現(xiàn)基礎(chǔ)。 未來的工作中，我們將做更多的測試，并實現(xiàn)多邊形與線，多邊形與點等的空間謂詞 判斷。并且更深入的研究如何動態(tài)的最優(yōu)的決定柵格單元的大小。 參考文獻(xiàn) 1 Longley P, Goodchild M F, Maguire D, et al. Geographical Information Systems: Principles, Techniques, Management, and Appl