使用距离矩阵来查找一组点的坐标点 [英] Using distance matrix to find coordinate points of set of points
问题描述
编辑：这是在飞机上。
这个问题被回答了这里，但在尝试不同的距离矩阵时，我真的无法使用这个答案，因为M矩阵具有负值，就像我的特征向量一样。所以当你取平方根时，程序（在R中）为那些相关的条目输出NaN。
我猜这每当D（i，j）^ 2大于D（1，j）^ 2 + D（i，1）^ 2时都会发生。
例如，假设我有距离矩阵：
0 73 102 496 432 184
73 0 303 392 436 233
102 303 0 366 207 353
496 392 366 0 172 103 $ b $ 432 436 207 172 0 352
184使用等式M（i，j）=（0.5）（D（b（b））， 1，j）^ 2 + D（i，1）^ 2-D（i，j）^ 2），我得到了（它已经有负项）：
<$ 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
然后我得到非零特征值& eigenvectors：
477718.27 101845.63 16474.30 -13116.72 -100692.49sqrt（eigenvector（i）* eigenvalue（i））时，我们会得到负值。
[，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
这里是我的最终输出：
$ p $[，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 35.86158 NaN 60.35139
NaN 232.5429 NaN NaN 242.43877
这是计算坐标点而不使用角？
如果是的话，我们是否必须修正距离矩阵，使D（i，j）^ 2不大于D（1，j）^ 2 + D（i，1）^ 2。
谢谢。 您的数据不一致
您的坐标与您的坐标不一致ℝ4点的位置，更不用说较低维度的空间。您可以通过计算平方距离矩阵的Menger行列式来说明这一事实：
D < - as.matrix（read。表格（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 $ b $ （b）432 436 207 172 0 352
184 233 353 103 352 0）））
n <-nrow（D）
det（cbind（D ^ 2，1），c （rep（1，n），0）））
＃结果：3.38761e + 25
如果你的坐标真的来自维度小于5的空间中的点，那么这个行列式将不得不为零。事实并非如此，你的距离是不一致的，或者这些点在维度足够高的空间中形成一个单纯形。但是没有维度，你的数据仍然不一致因为它在几种情况下违反了三角不等式：
abc 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经历更长的时间，但根据你的数据它是。
简单的平面方法
如果您的数据与平面上的点一致（即四个点的组合的所有Menger决定因素评估为零），您可以使用以下获得坐标：
distance2coordinates< ; - 函数（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 - （y）
x3 < - x [p3]
y3 < - y [p3]
plus < - abs（D [p3，] ^ 2 - （x3-x）^ 2 - （y3-y）^ 2）
减去-abs（D [p3，] ^ 2-（x3 - x）^ 2 - （y3 + y）^ 2）
y [minus <加上]< -y [减去<加上]
coords< - data.frame（x = x，y = y）
return（coords）
}
这个想法是你选择两个距离最大的点作为起点。你放在原点上，另一个放在正X轴上。然后你可以计算所有其他的x坐标，作为两个圆的交点，按照方程：
I：x²+y² = r 1 2pre>
II：（x-x 2）2 + y 2 = r 2 2
I-II：2 * x * x 2 = r 1 2 - r 2 2 + x 2 2
给定这些x坐标，您也可以获取y坐标，直到签名。然后你选择离这两个起点足够远的第三点来决定标志。
这种方法完全没有办法处理不精确的输入。它假定确切的数据，并且将仅使用部分距离矩阵来查找点。它不会找到与所有输入数据最匹配的点集。
在您的数据上，这将失败，因为平方根的一些参数将为负值。这意味着所涉及的两个圆并不相交，因此违反了三角不等式。
如果是，我们是否有（i，j）^ 2不大于D（1，j）^ 2 + D（i，1）^ 2来修复距离矩阵。
$ /
D（i，j）≤D（i，k）+ D（k，j）没有方块。这将确保三角不等式在任何地方都成立。结果仍然不需要是平面的;为此你必须修复所有那些Menger决定因素。 Given a distance matrix and a set of points, how do you figure out the coordinates of these points?
Edit: This is on a plane.
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 0Using 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.0Then 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.58372335Since 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.43877Is 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.
Thanks.
解决方案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+25If 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 + 103Going from a to c directly can never take longer than going via b, but according to your data it does.
Simple planar approach
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) }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₂²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.
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) 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屋！
