一種基于行列法離散點邊界搜索算法

0 引言

平面離散點的邊界在GIs、計算機圖形學以及地圖學中都有廣泛的應用，所以構造平面離散點邊界是一個重要的問題，現在已有不少關于平面離散點邊界處理技術的研究。湖南大學的陳濤等人提出了一種搜索盒邊界搜索算法，算法的基本思想就是通過構建一個搜索盒，將離散點都放人到搜索盒中，找到空的搜索盒，即為邊界搜索盒，然后從某一個邊界搜索盒開始，搜尋出封閉的邊界?，F在比較新的一種算法是華僑大學王建軍等人的網孔法的點云數據邊界算法，該算法利用網格得到邊界網孔，找到每個邊界網孔的最小凸邊。該算法可以得到點云集的邊界，但算法比較復雜，使用起來花費很多時間。本文提出一種新的簡單的行列搜索邊界算法，通過計算步長得到搜索的最小范圍，然后進行行搜索和列搜索，通過對溢出點處理，最終得到邊界曲線。該算法簡單、效率高，能夠構造平面的凹凸點集，通用性強。