使用距离矩阵查找点集的坐标点 [英] Using distance matrix to find coordinate points of set of points
问题描述
给定一个距离矩阵和一组点，你如何计算出这些点的坐标?
Given a distance matrix and a set of points, how do you figure out the coordinates of these points?
这是在飞机上.
这里回答了这个问题，但尝试不同距离矩阵，我真的不能使用这个答案，因为 M 矩阵有负值，我的特征向量也是如此.因此，当您取平方根时，程序(在 R 中)为这些相关条目输出NaN".我猜每次 D(i,j)^2 大于 D(1,j)^2 + D(i,1)^2 时都会发生这种情况.
This question was answered here but in trying different distance matrices, I really couldn't use this answer because the M matrix had negative values, as did my eigenvectors. So when you took the square root, the program (in R) outputs "NaN" for those associated entries. I'm guessing this will happen every time D(i,j)^2 is greater than D(1,j)^2 + D(i,1)^2.
例如，假设我有一个距离矩阵:
For example, say I have a distance matrix:
0 73 102 496 432 184
73 0 303 392 436 233
102 303 0 366 207 353
496 392 366 0 172 103
432 436 207 172 0 352
184 233 353 103 352 0
使用方程 M(i,j) = (0.5)(D(1,j)^2+D(i,1)^2-D(i,j)^2)，我得到(已经有否定条目):
Using the equation M(i,j) = (0.5)(D(1,j)^2+D(i,1)^2-D(i,j)^2), I get (which already has negative entries):
0 0.0 0.0 0.0 0.0 0.0
0 5329.0 -38038.0 48840.5 928.5 -7552.0
0 -38038.0 10404.0 61232.0 77089.5 -40174.5
0 48840.5 61232.0 246016.0 201528.0 134631.5
0 928.5 77089.5 201528.0 186624.0 48288.0
0 -7552.0 -40174.5 134631.5 48288.0 33856.0
然后我得到非零特征值 &特征向量:
Then I get non - zero eigenvalues & eigenvectors:
477718.27 101845.63 16474.30 -13116.72 -100692.49
[,1] [,2] [,3] [,4] [,5]
0.00000000 0.0000000 0.00000000 0.00000000 0.00000000
-0.05928626 0.3205747 0.84148945 0.04869546 -0.42806691
-0.16650486 -0.5670946 -0.04507520 -0.58222690 -0.55647098
-0.73371713 0.2827320 0.07386302 -0.45957443 0.40627254
-0.59727407 -0.4623603 0.07806418 0.64968004 -0.03617241
-0.27144823 0.5309625 -0.52755471 0.15920983 -0.58372335
既然有负特征值和特征向量，当我们计算sqrt(eigenvector(i)*eigenvalue(i))，我们会有负值.这是我的最终输出:
Since there are both negative eigenvalues and eigenvectors, when we compute sqrt(eigenvector(i)*eigenvalue(i)), we'll have negative values. Here is my final output:
[,1] [,2] [,3] [,4] [,5]
0 0.0000 0.00000 0.00000 0.00000
NaN 180.6907 117.74103 NaN 207.61291
NaN NaN NaN 87.38939 236.71174
NaN 169.6910 34.88326 77.64089 NaN
NaN NaN 35.86158 NaN 60.35139
NaN 232.5429 NaN NaN 242.43877
这是不使用角度计算坐标点的唯一清晰方法吗?如果是，我们是否必须修复距离矩阵，使 D(i,j)^2 不大于 D(1,j)^2 + D(i,1)^2.
Is this the only clear way of computing the coordinate points without using angles? If it is, do we have to fix the distance matrix so D(i,j)^2 is not greater than D(1,j)^2 + D(i,1)^2.
谢谢.
推荐答案
你的数据不一致
您的坐标与ℝ⁴中点的位置不一致，更不用说低维空间了.您可以通过计算平方距离矩阵的门格尔行列式来判断这一事实:
Your data is inconsistent
Your coordinates are not consistent with positions of points in ℝ⁴, let alone a space of lower dimension. You can tell that fact by computing the Menger determinant of your squared distance matrix:
D <- as.matrix(read.table(textConnection("
0 73 102 496 432 184
73 0 303 392 436 233
102 303 0 366 207 353
496 392 366 0 172 103
432 436 207 172 0 352
184 233 353 103 352 0")))
n <- nrow(D)
det(rbind(cbind(D^2, 1), c(rep(1, n), 0)))
# Result: 3.38761e+25
如果您的坐标确实来自维度小于 5 的空间中的点，那么该行列式必须为零.事实上，您的距离不一致，或者这些点在足够高维度的空间中形成单纯形.
If your coordinates really came from points in a space of dimension less than five, then this determinant would have to be zero. As it is not, your distances are inconsistent, or the points form a simplex in a space of sufficiently high dimension.
但无论维度如何，您的数据仍然不一致，因为它在某些情况下违反了三角不等式:
But no mater the dimension, your data is still inconsistent since it violates the triangle inequality in several cases:
a b c ac abc ab bc
1 2 4: 496 > 465 = 73 + 392
1 3 4: 496 > 468 = 102 + 366
1 3 5: 432 > 309 = 102 + 207
1 6 4: 496 > 287 = 184 + 103
2 1 3: 303 > 175 = 73 + 102
2 6 4: 392 > 336 = 233 + 103
3 1 6: 353 > 286 = 102 + 184
5 4 6: 352 > 275 = 172 + 103
直接从a到c永远不会比通过b花费更长的时间，但根据您的数据确实如此.
Going from a to c directly can never take longer than going via b, but according to your data it does.
如果您的数据与平面中的点一致(即所有四个点的组合的门格尔行列式计算为零)，您可以使用以下方法获取坐标:
If you had data consistent with points in the plane (i.e. all Menger determinants for combinations of four points evaluate to zero), you could use the following to obtain coordinates:
distance2coordinates <- function(D) {
n <- nrow(D)
maxDist <- which.max(D)
p1 <- ((maxDist - 1) %% n) + 1
p2 <- ((maxDist - 1) %/% n) + 1
x2 <- D[p1, p2]
r1sq <- D[p1,]^2
r2sq <- D[p2,]^2
x <- (r1sq - r2sq + x2^2)/(2*x2)
y <- sqrt(r1sq - x^2)
p3 <- which.max(y)
x3 <- x[p3]
y3 <- y[p3]
plus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 - y)^2)
minus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 + y)^2)
y[minus < plus] <- -y[minus < plus]
coords <- data.frame(x = x, y = y)
return(coords)
}
这个想法是你选择两个距离最大的点作为起点.您将一个放在原点上，另一个放在正 x 轴上.然后，您可以根据方程式计算所有其他 x 坐标，作为两个圆的交点
The idea is that you choose two points with maximal distance as starting points. You place on in the origin and the other on the positive x axis. Then you can compute all other x coordinates from this, as the intersection of two circles, following the equations
I: x² + y² = r₁²
II: (x - x₂)² + y² = r₂²
I-II: 2*x*x₂ = r₁² - r₂² + x₂²
给定这些 x 坐标，您也可以获得 y 坐标，直到 sign.然后，您选择第三个点，距离这两个起点中的任何一个足够远，以决定标志.
Given these x coordinates, you can obtain y coordinates as well, up to sign. You then choose a third point, sufficiently far away from either of these two starting points, to decide on the sign.
这种方法根本不尝试处理不精确的输入.它假定准确的数据，并且只会使用距离矩阵的一部分来查找点.它不会找到与所有输入数据最匹配的点集.
This approach makes no attempt at all to handle imprecise input. It assumes exact data, and will only use part of the distance matrix to find the points. It will not find the point set most closely matching all of the input data.
在您的数据上，这将失败，因为平方根的某些参数将是负数.这意味着所涉及的两个圆根本不相交，因此违反了三角不等式.
On your data, this will fail, since some arguments to the square root will be negative. This means that the two circles involved don't intersect at all, hence the triangle inequality is violated.
如果是，我们是否必须修复距离矩阵，使 D(i,j)^2 不大于 D(1,j)^2 + D(i,1)^2.
If it is, do we have to fix the distance matrix so D(i,j)^2 is not greater than D(1,j)^2 + D(i,1)^2.
D(i,j) ≤ D(i,k) + D(k,j) 会有所帮助，即对于所有三元组且没有正方形.这将确保三角不等式在任何地方都成立.结果仍然不必是平面的；为此，您必须修复所有门格尔行列式.
D(i,j) ≤ D(i,k) + D(k,j) would help, i.e. for all triples and without squares. This would ensure that the triangle inequality holds everywhere. The result still need not be planar; for that you'd have to fix all those Menger determinants.
这篇关于使用距离矩阵查找点集的坐标点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
