如何在點集/ 2D形狀中找到「中心」定位點？

Question

2D體素的中心座標表示2D點集。使用這些座標，畫面中的紅點指的是質量/重力的（近似）中心，即所有座標的平均值。忽略不同的灰度值，儘管它們巧合地提供了2D體素稍微更好的可見性:-)

綠點（大致）是我想得到的，但是如何（？）以原理方式？）。所以基本上我們在2D體素空間中有一個連通集，或者一組2D點，如果有幫助，可以假設整數座標。我想確定一個關於形狀「中心」的點，但是確定在形狀上，即該組的一部分。

僞代碼和/或C/C++歡迎:-)

更新：如果結構較厚，其實我喜歡綠點是有些中央而不是在輪廓上。

Answer 1

這裏是解決方案，可以在O(N)找到綠點： -

Find mean (xm,ym) 

Suppose (xm+a),(ym+b) is a point in the dataset 

E(xi,yi) = sum of squared distances of all points from (xi,yi) 

E(xm,ym) = k because it is the mean. 

E(xm+a,ym+b) = summation => (xi-(xm+a))^2 + (yi-(ym+b))^2 

      = summation => ((xi-xm)-a)^2 + ((yi-ym)-b)^2 

      = summation => (xi-xm)^2 + (yi-ym)^2 + a^2 + b^2 - 2a*(xi-xm) - 2b*(yi-ym) 

      = summation => (xi-xm)^2 + (yi-ym)^2 + summation => a^2 + b^2 +..... 

    summation => (xi-xm)^2 + (yi-ym)^2 = E(xm,ym) = k 

Hence 

E(a,b) = summation => a^2 + b^2 - 2a*(xi-xm) - 2b*(yi-ym) 

as a,b are constant in summation 

E(a,b) = (a^2+b^2)*N - 2a*(summation=>(xi-xm)) - 2b*(summation=>(yi-ym)) 

summation=>(xi-xm) = 0 
summation=>(y1-ym) = 0 

E(a,b) = a^2 + b^2 

Now to get green point which will minimize E(a,b) 

a = xk-xm 
b = yk-ym 

find (xp,yp)=>minimum{E(a,b)} among all (xk,yk) 

summation=>(xi-xm) and summation=>(yi-ym) can be found in O(N) after finding mean 

hence E(a,b) can be found in O(1) and (xp,yp) in O(N)