激光散亂點云K最近鄰搜索算法

　　針對激光散亂點云的數(shù)據(jù)量大，且具有面型的特點，為降低存儲器使用量，提高散亂點云的處理效率，提出了一種散亂點云K最近鄰（KNN）搜索算法。首先，利用多級分塊、動態(tài)鏈表的存儲方式，只存儲非空的子空間編號。對相鄰子空間進行3進制編碼，利用編碼的對偶關(guān)系，建立相鄰子空間之間的指針連接，構(gòu)造出包含KNN搜索所需的各類信息的廣義表，然后再搜索KNN。KNN搜索過程中，在計算被測點到候選點距離時，直接刪除篩選立方體內(nèi)切球之外的點，可將參入按距離排序的候選點數(shù)減少為現(xiàn)有算法的一半。依賴K值和不依賴K值的分塊原則，均可計算不同的K鄰域。實驗結(jié)果表明，該算法不僅具有低的存儲器使用量，而且具有較高的效率。