線性交錯式二元樹及其在地理資訊系統上之應用

Linear Interpolation- Based Bintree and Its Applications in Geographic Information Systems

地理資訊系統可以表達與運用分析地理資料，但是在表達地理資料上，必須處理大量的圖形影像，使得地理資訊系統的執行效率並不令人滿意。因此，尋找一種影像編碼方式，並且發展必要且有效率的影像分析運算，是發展地理資訊系統的重要課題。在以往的研究中，線性四元樹的影像編碼在這方面已經有不錯的表現。但是，因為線性二元樹可以合併為長方形區塊，所以可以使用更少的黑色節點來表示影像。本研究改進線性交錯式二元樹的編碼方式，減少每個節點需要的儲存空間，使得資料擷取與傳輸的時間可以縮短。本研究以此編碼方式發展出幾個基本的地理資訊空間運算，如集合運算、鄰點搜尋等，並且改進以往無法找出所有鄰點的缺點。而其在運算的處理也更為簡易，使得地理資料在分析與運算上更為迅速。

A Geographic Information System (GIS) is an information system that stores spatially referenced data. The performance of manipulating spatial data stored in maps usually is not very satisfactory. Hence, finding an encoding scheme that can manipulate spatial data more efficiently is the most important research task in GIS. In this paper, we use linear interpolation – based bintrees to represent binary images. Compared to quadtrees, bintrees have fewer image blocks and thereby need less storage space. Based on our encoding scheme, both the set and the neighbor finding operations are very simple and efficient；thus resulting in performance improvement in the manipulation of graphic images in GIS.