8

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

我的地图在地形上与《吃豆人》和《小行星》中的地图相似。越过顶部会将您弯曲到底部，越过左侧会将您弯曲到右侧。

假设我在地图上有两个点（质量相同），我想找到它们的质心。我可以使用经典定义，基本上是midpoint。

但是，假设这两个点位于质量的两端。可以说，还有另一个质心，是通过“环绕”形成的。基本上，它是与其他两个点等距的点，但通过“环绕”边缘连接。

例子

b . O . . a . . O .

两点O。它们的“经典”中点/质心是标记的点a。但是，另一个中点也在b(b通过环绕，与两个点等距)。

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

解决两点情况的一种方法是简单地测试经典中点和最短的环绕中点，并使用平均距离较短的中点。

然而！这不容易概括为 3 个点、4 个、5 个或n个点。

有没有我可以用来找到这个的公式或算法？

（假设所有点的质量总是相同的。我只使用“质心”，因为这是我知道的唯一术语来松散地描述我想要做的事情）

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

4

4 回答 4

4

质心的概念是与仿射空间相关的概念。n 维环面没有仿射结构。

你想要的是一个最小化（测地线）到所有其他点的距离的点。

我建议如下：让 x_1...x_n 是 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)

于 2010-09-14T11:18:55.140 回答
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}}]
于 2010-09-15T21:23:04.440 回答
2

在一维情况下，您的问题类似于找到平均角度。角度 a 和 b 的平均值可以通过下式计算

平均值 = 余数(a + 余数(ba, C)/2.0, C) 其中 C 是整个圆的度量（即，如果您使用弧度，则为 2*PI）。

如果您有 n 个角度 a[]，则平均值可以通过以下方式计算

平均值 = a[0]; 对于 i=1..n 均值 = 余数（均值 + 余数（a[i]-均值，C）/（i+1），C）

所以我认为

平均X = X[0]；平均 Y = 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

于 2010-09-14T11:18:31.323 回答
0

IANATopologist，我不知道我在这方面有多清楚，但对于它的价值，这些是关于这个问题的一些想法：

使用质量和重力来计算这种东西可能确实很优雅——ISTR 有许多库和有效的算法可以找到任意数量质量的重力矢量。

如果您使用的是球形地图，我建议您在球体内找到 N 个质点的实际重心。然后，您从中心向外通过该内部重心画一条线，以找到球体表面上您的质点希望聚集的点。

然而，环形地图使这变得困难。

那么，我的建议是展平并复制您的地图，为您提供 3 x 3 的地图被子（使用无限的地图区域会产生更好的结果，但可能会过大）。我将为它们分配坐标 (0, 0) 到 (2, 2)，其中 (1, 1) 是您的源地图。找到你的内部地图 (1, 1) 的质量点被吸引到的点——如果它们都向你的地图中间移动，很好：你找到了你的重心。如果不是，如果靠近边缘的一个点正朝着你的内部地图之外的一些质量积累，比如进入地图 (2, 1)，那么在计算你的重心时丢弃这个质量点。取而代之的是，您使用对面地图（在本例中为 (0, 1)）中想要游荡到中间地图的质点。

为这些质点添加加速度矢量可为您提供圆环上的重心。完毕。

于 2010-09-14T11:04:29.883 回答