查找潛在的最大圓圈

Question

我有一組2D點，我想找到潛在的最大空圓圈。因此，我並不是要編寫最大空圈算法。

這是一張圖片，試圖解釋我的話。

正如你所看到的，有一些圈子裏面分，所以我要的是，鑑於該組2D點，可以計算這個圈子的算法。

該組點代表包含洞的下水道牆。問題是這個孔可能是軟木塞，可能在圓的一側或多側包含一些污垢。所以，當你激光探測到這個部件時，你不會得到一個完美的圓，而是一個半圓。我想找到的是當沒有污物時，原始的洞，乾淨的洞。當我說潛力時，我的意思是最初的漏洞。在圖像中，綠色的圓圈就是原來的洞穴，圈內的點是一些污垢。最終目的是決定是否清潔或骯髒（檢測綠色圓圈內有多少點，並確定它有多髒）

它應該如何在現實生活中的另一個例子：

在這裏你可以看到，孔有污垢在底部（可能是孔的任何一側），所以當你發現激光它，你不會獲得了一圈，但一堆點的圓圈上部爲空。我想要的是從那些只能看到圓圈上半部分的點，重新構建原始的洞，就像清理時那樣。

另外，我從兩個不同的角度附加了兩個點雲圖像，這樣您就可以知道我正在處理什麼。

Answer 1

我會發現孔的邊框，然後檢查兩側。找到不是線性的，而是彎曲的，並將其設置爲圓形邊框。然後只適合圈到那邊。欲瞭解更多信息，請參閱：

• fitting ellipses
• Finding holes in 2d point sets

Answer 2

如果你能以繪製點到的圖像縮放座標，這裏是一個解決方案：

1. 抽獎點到圖像中
2. 使用所有點作爲源點計算距離圖。
3. 然後，每個像素將包含到closes點的距離。所以具有最高值的像素將是最大圓的中心，並且像素值將是圓的半徑。
4. 查找離圓心最近的點。
5. 找到經過所有論點的圓圈（Hough？）。解決方案可能不是唯一的。