在环形地图上,一组点的“质心”是指最小化到所有点平均距离的点。

8

编辑 正如有人指出的那样,我要找的实际上是最小化所有其他点之间总测地线距离的点。


我的地图在拼图和宇宙射击游戏中类似于地形。越过顶部将会传送到底部,越过左侧将会传送到右侧。

假设我在地图上有两个点(质量相同),我想找到它们的重心。我可以使用经典定义,基本上是中点

然而,假设这两个点位于质量的两端。还有另一个所谓的重心,通过"绕着边缘"形成。基本上,它是与其他两个点等距离但由“绕过边缘”连接的点。

举个例子

b . O . . a . . O .

有两个点O。它们的“经典”中点/质心是标记为a的点。然而,另一个中点也在b(通过绕过,b到两个点的距离相等)。

在我的情况下,我想选择两个点之间平均距离较小的那个。在这种情况下,a两个点之间的平均距离为三步。b的平均距离为两步。因此,我会选择b

解决两点问题的一种方法是简单地测试经典中点和最短的绕过中点,并使用具有较短平均距离的那个。

然而!这不容易推广到3个点、4个点、5个点或n个点。

是否有公式或算法可以用来找到这个?

(假设所有点的质量始终相等。我只使用“质心”这个术语,因为它是我所知道的唯一一个粗略描述我想要做的事情的术语)

如果我的解释不清楚,我会尽力解释得更好。


预期得分是多少?它只有3、4、5个,还是可能达到20或100个? - brainjam
@brainjam 我想要一个适用于所有点数的解决方案,但是对于我的应用程序,点数将从1到10不等。上限为150。 - Justin L.
点是否以某种方式组织?例如,您是否能够直观地发现重心?或者这些点是否可以随机分布在环面上? - brainjam
@brainjam 这个分布并不完全是随机的。点会一个接一个地随机放置在地图上。如果任何“相关”的点已经在地图上(关系不总是相互的),它将尝试被放置在已经在地图上的相关点之间的“质心”位置。 - Justin L.
4个回答

4
中心点的概念是在仿射空间中相关的概念。n维环面没有仿射结构。
你需要的是一个点,它最小化到所有其他点的(测地线)距离。
我建议以下:让x1...xn成为d维环面(或任何其他度量空间)上的一组点。
你的问题:
找到一个点mu,使得sum(dist(mu, x_k)^2)最小。
在仿射欧几里德情况下,你会得到通常的质心概念。
这是一个你可以用共轭梯度算法解决的问题(例如,可能有更好的选择),该算法在这种情况下表现良好。请注意,您需要适度的n(例如n < 10 ^ 3),因为该算法需要n ^ 2的空间和n ^ 3的时间。
也许更适合的是Levenberg-Marquardt算法,它专门用于最小化平方和。
请注意,如果您有一个很好的初始猜测(例如,将点视为R ^ d中的点而不是环面上的点的通常重心),该方法将更快地收敛。
编辑: 如果(x1...xd)和(y1...yd)是环面上的点,则距离由以下公式给出 dist(x, y)^2 = alpha1^2 + ... + alphad^2
其中alphai = min((xi-yi)mod 1,(yi-xi)mod 1)

@Alexandre,你能写下环面上测地线距离的公式吗?我不确定如何选择最小的测地线... - Dr. belisarius
@belisarius 如果你的环面只是一个“吃豆人空间”,也就是一个带有包裹边缘的矩形,那么两点之间的测地线就是它们之间的最小直线距离。 - flies
如果你的距离是非负数,那么你其实不需要对距离进行平方,对吧? - flies
@flies,您需要一个通用公式来最小化到测地中心的距离。此外,作为周期性边界问题,您有不止一条直线可选。 - Dr. belisarius
@文件:所有的平方都有两个目标:每当点接近彼此时,产生质心,并使问题在数值上易于处理。最小化一个 二次 函数非常简单。 - Alexandre C.

3
我制作了一个小程序来检查所涉函数的优秀程度,并发现在最小化过程中应该非常小心。下面您可以看到两组图,显示了点分布、欧几里得情况下需要最小化的函数和对应于“环形指标”的函数。
如您所见,欧几里得距离非常易于处理,而环形指标则存在一些局部极小值,使得难以找到全局极小值。此外,在环形指标情况下的全局最小值并不唯一。
万一需要,Mathematica中的程序如下:
Clear["Global`*"];

(*Define  non wrapping distance for dimension n*)
nwd[p1_, p2_, n_] := (p1[[n]] - p2[[n]])^2;

(*Define wrapping distance for dimension n *)
wd[p1_, p2_, max_,n_] := (max[[n]] - Max[p1[[n]], p2[[n]]] + Min[p1[[n]], p2[[n]]])^2;

(*Define minimal distance*)
dist[p1_, p2_, max_] :=
  Min[nwd[p1, p2, 1], wd[p1, p2, max, 1]] +
  Min[nwd[p1, p2, 2], wd[p1, p2, max, 2]];

(*Define Euclidean distance*)
euclDist[p1_, p2_, max_] := nwd[p1, p2, 1] + nwd[p1, p2, 2];

(*Set torus dimensions *)
MaxX = 20; 
MaxY = 15;

(*Examples of Points sets *)
lCircle = 
  Table[{10 Cos[fi] + 10, 5 Sin[fi] + 10}, {fi, 0, 2 Pi - .0001, Pi/20}];

lRect = Join[
   Table[{3, y}, {y, MaxY - 1}],
   Table[{MaxX - 1, y}, {y, MaxY - 1}],
   Table[{x, MaxY/2}, {x, MaxY - 1}],
   Table[{x, MaxY - 1}, {x, MaxX - 1}],
   Table[{x, 1}, {x, MaxX - 1}]];

(*Find Euclidean Center of mass *)
feucl = FindMinimum[{Total[
    euclDist[#, {a, b}, {MaxX, MaxY}] & /@ lRect], 0 <= a <= MaxX, 
             0 <= b <= MaxY}, {{a, 10}, {b, 10}}]

(*Find Toric Center of mass *)
ftoric = FindMinimum[{Total[dist[#, {a, b}, {MaxX, MaxY}] & /@ lRect],
         0 <= a <= MaxX, 0 <= b <= MaxY}, {{a, 10}, {b, 10}}]

干得好。不过我想看看OP的典型情况:如果点在拓扑意义上很好定位,那么最小化过程应该没问题。如果不是,那么问题确实很难... - Alexandre C.
@Alexandre 想象一下,在桌子上放着一个甜甜圈,顶部和底部的点对齐并且间距为2*PI/n ... 质心在哪里呢?:D 我认为任何遵循“环面对称性”的点分布都会有相同的问题。 - Dr. belisarius
1
是的,但允许多个质心的配置集很小(它是一个可数的闭无处稠密集合的并集,这就是“通常”的含义)。特别地,只要您扰动了这样的配置之一,您几乎肯定会有一个唯一的质心。另一个备注(根据对称性论证):R ^ 2中一条直线的质心在哪里? - Alexandre C.
@Alexandre 42?:D。非常好的评论! - Dr. belisarius

2
在一维情况下,您的问题类似于寻找平均角度。 角度a和b的平均值可以通过以下方式计算:
mean = remainder( a + remainder( b-a, C)/2.0, C)
其中C是整个圆的度量(即如果您使用弧度,则为2 * PI)。
如果您有n个角度a [],则可以通过以下方式计算平均值:
mean = a [0]; for i = 1..n mean = remainder(mean + remainder(a [i] - mean,C) / (i + 1),C)
所以我认为
meanX = X [0]; meanY = Y [0]
对于i = 1 .. n
 meanX = remainder( meanX + remainder( X[i]-meanX, W)/(i+1), W)
 meanY = remainder( meanY + remainder( Y[i]-meanY, H)/(i+1), H)

可能可以完成工作。但请注意,这将导致-W/2<=meanX。

啊!手指出了问题。n角情况应该继续。 - dmuir
再来一遍!for(i=1; i<n; ++i) mean = remainder(mean, remainder( A[i]-mean, C)/(i+1), C); - dmuir
2
你应该编辑你的答案,而不是试图通过评论来纠正错误。 - Don Roby
那么你的意思是我应该分别将它应用于我的两个不同的轴,然后答案就是合成结果? - Justin L.
经过对角度平均值的研究,看起来它几乎正是我所需要的东西。我会用我使用的算法/公式做一些实验,但是这为我提供了一个良好的起点。谢谢 =) - Justin L.

0

我是一个拓扑学家,也不知道自己在表达方面是否清晰明了,但对于这个问题,我有一些想法:

使用质量和引力来计算这种情况可能确实很优雅——我记得有许多库和高效算法可以找到任意数量的物体的引力向量。

如果你正在使用球形地图,我建议你在球内找到N个质点的实际重心。然后你从中心向外绘制一条线,穿过这个内部重心,找到球面上物体希望聚集的点。

然而,环形地图会使这个过程变得困难。

我的建议是,将您的地图展平并复制,形成一个 3 x 3 的地图拼贴(使用无限的地图领域可以得到更好的结果,但可能有些过头了)。我将为它们分配坐标 (0, 0) 至 (2, 2),其中 (1, 1) 是您的源地图。找出内部地图(1,1)的质点所吸引到的点——如果它们都朝着您的地图中心走,很好:您找到了重心。如果不是这样,如果靠近边缘的一个点正在走向内部地图以外的某个质量积累(例如地图 (2,1)),则在计算重心时要丢弃此质点。相反,您应该使用来自对面地图 ((在这种情况下是 (0,1)) 希望漫步进入您的中间地图的质点。
添加这些质点的加速度矢量将为您在环面上找到重心。 完成。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接