離散點云最小包圍圓求解

1、離散點最小包圍圓求解離散點最小包圍圓求解近年來激光雷達(dá)技術(shù)去得了快速的發(fā)展，由于它在數(shù)據(jù)上又精確度高，速度快，能夠快速展現(xiàn)出地物原貌等特點，對于海量的數(shù)據(jù)我們可以通過簡化為數(shù)學(xué)模型，進(jìn)而確定地物的中心點。點云數(shù)據(jù)在樹木，電桿等地物的提取中，樹木電桿的點云并不是無關(guān)的，而是具有高度的相關(guān)性，他們的投影可以看成平面的不規(guī)則圖形，通過求取最小包圍圓的中心和半徑，進(jìn)而判斷出電桿和樹木的中心位置，而這個過程就可以轉(zhuǎn)化為離散點求最小包圍圓的問題了。

2、在平面離散點數(shù)據(jù)中，樹木和電桿的離散點急可以近似的看成一個類似圓的圖形，通過求取圓形的中心就可以近似確定樹木和電桿的中心達(dá)到獲得地物中心點的目的。目前，通用的做法就是根據(jù)最小二乘原理求出近似中心，再以此為近似值進(jìn)行精確求取圓心坐標(biāo)。目前典型算法主要有Markdeberg的隨機增量算法：1.隨機打亂點集中的所有點的順序2.以序列中前兩個點構(gòu)造最小包圍圓d3.一次搜索其余的點，若某個點v在d外，則重新構(gòu)造最小包圍圓d’，是d’包含d中的所有

3、點且以v為邊界點。重復(fù)執(zhí)行第三步，直到求出最小包圍圓。隨機增量算法，一般點是有序的，故打亂點順序也需要耗費時間，然后構(gòu)造圓并進(jìn)行判斷，滿足在圓內(nèi)是排除這些點，再根據(jù)剩下的點生成最小包圍圓再一次判斷，這個方法構(gòu)造的包圍圓相當(dāng)于另外還有計算幾何求解最小包圍圓的算法：1.對點集構(gòu)造凸包，刪除凸殼內(nèi)的點2.以凸殼上的采樣點的最小二乘為圓心，求取最遠(yuǎn)一點到它的距離，令其為比較半徑Rc3.刪除無關(guān)數(shù)據(jù)點：以Rc為標(biāo)尺，刪除所有不可能參與構(gòu)成最小外接

4、圓的無關(guān)數(shù)據(jù)點，即，對于點Pi，若Pi1Pi的中垂線與PiPi1的中垂線的交點到Pi之間的距離RiRc則刪去Pi4.調(diào)整數(shù)據(jù)結(jié)構(gòu)，循環(huán)到步驟2，知道沒有無關(guān)數(shù)據(jù)點，循環(huán)終止5.對剩余的點構(gòu)造最遠(yuǎn)Vonoi圖，判斷Vonoi定點距其相關(guān)點的距離，其中距離最小者為所求的最小外接圓半徑，該Vonoi定點為最小外接圓圓心在實際點云數(shù)據(jù)處理中，電桿為人工建筑物，可以按上述幾種方法求取中心線位置，并有較好的精度，但是樹木，由于其生長的特殊性，以及后