離散點(diǎn)云最小包圍圓求解

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

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

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

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