algorithm - 如何在点集/二维形状中找到 "central" anchor ？

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)