一組點和軌跡形狀的中心點

Question

我有點像這樣的點的圖。

這些點形成的軌道可以是圓形或橢圓形。很明顯，上面兩張圖片中的圓形軌道的中心是不同的。

如何找到這些軌跡的中心點（圓形/橢圓形）？我想找到以（x，y）爲中心的座標，不一定必須是繪圖數據集中的點。即我不想要medoid。

編輯：另外，有無論如何，我可以找到一個圓/橢圓方程包含大多數這些點？在橢圓形軌道中，我添加了一個包圍軌道上點的橢圓。這些值是通過試驗和錯誤計算的。該中心也是通過眼球計算得出的。我怎樣才能以編程方式做到這一點？

Answer 1

Smallest circle problem這裏是關於smallest ellipse problem的論文（PDF格式下載可用）。兩者都有O（N）算法，並且應該能夠提供可以獲得中心的圓和區域的公式。但是，他們着重圍繞所有要點。要解決這個問題，你需要刪除一些邊界點，你也應該從算法中獲得。不幸的是，對於什麼樣的解決方案來說，這取決於你。

甲快速和簡單的隨機化的解決方案是：

隨機
1. 劃分的點的集合爲k組，每組N/k個點。
2. 運行每個集合的最小圓/橢圓算法
3. 對於k個集合中的每個集合，從主集合集合中選取至少1個但不再有m個邊界點。
4. 返回第1步，t次。
5. 返回剩餘點上的圓/橢圓算法的結果。

該算法以O（N）爲代價去除k和mk邊界點之間的每次通過。出於你的目的，你可能想要刪除一些百分比的邊界點，1-25％似乎是一個很好的起點。該解決方案假設k與N相比非常小，否則您將刪除太多點。

如果您想要從最小的橢圓中重複移除一個或所有的邊界點，重新計算最小的橢圓，然後再次移除邊界點，較慢但可能更好的算法很有用。

您可以通過將父節點設置爲其子節點的最小包圍橢圓的邊界點（便於更快移除的點作爲集合存儲）。邊界點的最大數量不應超過k（我認爲橢圓爲9，而圓爲3）。因此，要從O（k log N）處的數據結構中刪除一個點，因爲它需要重新計算每個受影響的O（log N）父節點的最小圓，即O（k）。所以從數據結構中刪除m個點應該是O（mk log N）。您可能還需要考慮計算每個移除的點的橢圓面積，並刪除每個點的費用O（Nk log N），直到您只剩下三個點。然後，您可以分析面積數據以確定應使用哪個橢圓。一個簡單的結果就是簡單地使用橢圓的面積最接近所有橢圓的平均面積，但可能並不完全符合您的要求。它也可能太慢，在這種情況下，我建議單次更快的算法。

Answer 2

這看起來像一個強大的橢圓擬合的實例。檢查本文： 魯棒橢圓和橢球擬合http://arxiv.org/pdf/0910.4610.pdf異常消除。

通過慣性橢圓（慣性的橢圓體的2D版本http://en.wikipedia.org/wiki/Moment_of_inertia#Inertia_ellipsoid）提供了第一個粗略和簡單的解決方案。它的中心就是質心，軸由2×2慣性矩陣的特徵向量/值給出。