＆QUOT;中心质量＆QUOT的;一组在环向包裹的地图点之间最小化所有点的平均距离 [英] "Center of Mass" between a set of points on a Toroidally-Wrapped Map that minimizes average distance to all points
问题描述
修改的正如有人所指出的那样，我所寻找的是真正的点最大限度地降低所有其他点之间的总测量距离的
我的地图地形类似于那些在Pac-Man游戏和小行星。但过顶会扭曲你的底部，和去过去的左边会扭曲你的权利。
My map is topographically similar to the ones in Pac Man and Asteroids. Going past the top will warp you to the bottom, and going past the left will warp you to the right.
说我有两个点（相同质量的）在地图上，我想找到质量的中心。我可以用经典的定义，基本上是在中点
Say I have two points (of the same mass) on the map and I wanted to find their center of mass. I could use the classical definition, which basically is the midpoint.
不过，假设这两个点都在大规模的两端。有质量的另一个中心，可以这么说，通过包装围绕形成。基本上，它是点等距离到两个其它点，而是由回绕链边缘。
However, let's say the two points are on opposite ends of the mass. There is another center of mass, so to speak, formed by wrapping "around". Basically, it is the point equidistant to both other points, but linked by "wrapping around" the edge.
示例
b . O . . a . . O .
两点 0 。大众自己的经典的中点/中心标记点 A 。然而，另一个中点也是在 B （ B 是等距到两个点，通过缠绕）。
Two points O. Their "classical" midpoint/center of mass is the point marked a. However, another midpoint is also at b (b is equidistant to both points, by wrapping around).
在我的情况，我想选择一个具有两个点之间较低的平均距离。在这种情况下， A 具有两个点的三个步骤之间的平均距离。 B 有两个步骤平均距离。所以，我会选 B 。
In my situation, I want to pick the one that has lower average distance between the two points. In this case, a has an average distance between the two points of three steps. b has an average distance of two steps. So I would pick b.
解出二点的情况的一种方法是简单地测试两个古典中点和最短缠绕中点，并使用一个具有较短的平均距离。
One way to solve for the two-point situation is to simply test both the classical midpoint and the shortest wrapped-around midpoint, and use the one that has a shorter average distance.
不过！这不容易推广到3分，或4，或5，或的 N 的分
However! This does not easily generalize to 3 points, or 4, or 5, or n points.
有一个公式或算法，我可以用它来找到这个？
Is there a formula or algorithm that I could use to find this?
（假设所有积分将永远是等质量的，我只能用重心，因为它是我知道松散地描述我试图做的唯一的术语）
(Assume that all points will always be of equal mass. I only use "center of mass" because it is the only term I knew to loosely describe what I was trying to do)
如果我的解释不清，我会尽量解释它更好的。
If my explanation is unclear, I will try to explain it better.
推荐答案
质心的概念是对相关的一个概念仿射空间的。 n维环面没有仿射结构
The notion of center of mass is a notion relevant on affine spaces. The n-dimensional torus has no affine structure.
你想要的是一个点，最大限度地减少（测地线）距离到所有其他点。
What you want is a point which minimizes (geodesic) distance to all the other points.
我建议如下：让X_1 ... x_n是在D维环面点的集合（或为目的的任何其他度量空间）
I suggest the following: let x_1...x_n be a collection of points on the d-dimensional torus (or any other metric space for that purpose).
您的问题：
找点多亩，使之和（DIST（亩，x_k）^ 2）是最小的。
find a point mu such that sum(dist(mu, x_k)^2) is minimal.
在仿射欧几里德的情况下，你会得到质背中心的通常概念。
In the affine-euclidian case, you get the usual notion of center of mass back.
这是一个问题，你将能够解决（比如，有可能是更好的选择）用的共轭梯度法的，在这种情况下表现良好。要注意的是，你需要适量的氮（例如N'小于10 ^ 3），由于算法需要N ^ 2在空间和n ^ 3的时间
This is a problem you will be able to solve (for instance, there are probably better options) with the conjugate gradient algorithm, which performs well in this case. Beware that you need moderate n (say n < 10^3) since the algorithm needs n^2 in space and n^3 in time.
或许更适合的是Levenberg-Marquardt算法，它是专为最小平方和。
Perhaps better suited is the Levenberg-Marquardt algorithm, which is tailored for minimization of sum of squares.
请注意，如果你有一个很好的初始猜测（比如，被视为在研发^ D，而不是圆环点的点的质平常中心），该方法将收敛更快。
Note that if you have a good initial guess (eg. the usual center of mass of the points seen as points in R^d instead of the torus) the method will converge faster.
编辑： 如果（X1 ... XD）和（Y1 ...码）都在环面点，该距离由下式给出 DIST（X，Y）^ 2 =α1 ^ 2 + ... + ALPHAD ^ 2
If (x1...xd) and (y1...yd) are points on the torus, the distance is given by dist(x, y)^2 = alpha1^2 + ... + alphad^2
在这里alphai = MIN（（喜 - 义）MOD 1，（YI - 十一）MOD 1）
where alphai = min((xi - yi) mod 1, (yi - xi) mod 1)
这篇关于＆QUOT;中心质量＆QUOT的;一组在环向包裹的地图点之间最小化所有点的平均距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
