Using a distance matrix to find the coordinate points of a set of points
Given a distance matrix and many points, how do you determine the coordinates of those points?
Edit: this is on a plane.
This question was answered here , but when trying to use different distance matrices, I really couldn't use this answer because the M matrix had negative values, just like my eigenvectors. So when you take the square root, the program (in R) prints out "NaN" for those related records. I assume this will happen every time D (i, j) ^ 2 is greater than D (1, j) ^ 2 + D (i, 1) ^ 2.
For example, let's 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
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 records):
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 and 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
Since there are negative eigenvalues and eigenvectors, when we compute sqrt (eigenvector (i) * eigenvalue (i)) we will have negative values. Here is my final result:
[,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
Is this the only clear way to calculate coordinate points without using angles? If so, is it necessary to fix the distance matrix so that D (i, j) ^ 2 is at most D (1, j) ^ 2 + D (i, 1) ^ 2.
Thank.
source to share
Your data is incompatible
Your coordinates do not agree with the positions of the points in ℝ⁴, let alone a space of lower dimensions. You can tell this fact by calculating the Menger determinant of your square 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
If your coordinates really came from points in space of dimension less than five, then this determinant should be equal to zero. Since this is not the case, your distances do not match, or the points form a simplex in a sufficiently high dimensional space.
But don't measure the dimension, your data is still incompatible as it breaks the triangle inequality in some 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
Going from a to c directly may not take longer than going through b, but according to your data it does.
Simple flat approach
If you had data corresponding to points on a plane (i.e. all Menger determinants for combinations of four points are zero), you can use the following to get the 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 pick two points with the maximum distance as starting points. You place at the origin and the other at the positive x-axis. Then you can calculate all the other x coordinates from that 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 also get the y coordinates, right up to the signature. You then select a third point, far enough from either of these two starting points to select a sign.
This approach does not attempt to handle imprecise data at all. It accepts precise data and will only use part of the distance matrix to find points. It will not find the point that most closely matches all input data.
In your data, this will fail as some square root arguments will be negative. This means that the two involved circles do not intersect at all, so the triangle inequality is violated.
If so, we have to fix the distance matrix so that D (i, j) ^ 2 is at most D (1, j) ^ 2 + D (i, 1) ^ 2.
D (i, j) ≤ D (i, k) + D (k, j) will help, i.e. for all triples and without squares. This would ensure the triangle inequality everywhere. The result still doesn't have to be flat; to do this, you will have to fix all these Menger determinants.
source to share
This is a simple python function to calculate what you need hyperspheres solution.
import sympy
import numpy as np
def give_coords(distances):
"""give coordinates of points for which distances given
coordinates are given relatively. 1st point on origin, 2nd on x-axis, 3rd
x-y plane and so on. Maximum n-1 dimentions for which n is the number
of points
Args:
distanes (list): is a n x n, 2d array where distances[i][j] gives the distance
from i to j assumed distances[i][j] == distances[j][i]
Returns:
numpy.ndarray: cordinates in list form n dim
Examples:
>>> a = sympy.sqrt(2)
>>> distances = [[0,1,1,1,1,1],
[1,0,a,a,a,a],
[1,a,0,a,a,a],
[1,a,a,0,a,a],
[1,a,a,a,0,a],
[1,a,a,a,a,0]]
>>> give_coords(distances)
array([[0, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1]], dtype=object)
>>> give_coords([[0, 3, 4], [3, 0, 5], [4, 5, 0]])
array([[0, 0],
[3, 0],
[0, 4]], dtype=object)
"""
distances = np.array(distances)
n = len(distances)
X = sympy.symarray('x', (n, n - 1))
for row in range(n):
X[row, row:] = [0] * (n - 1 - row)
for point2 in range(1, n):
expressions = []
for point1 in range(point2):
expression = np.sum((X[point1] - X[point2]) ** 2)
expression -= distances[point1,point2] ** 2
expressions.append(expression)
X[point2,:point2] = sympy.solve(expressions, list(X[point2,:point2]))[1]
return X
source to share
It is solvable
If you want to see the coordinates of the Cartesian coordinates that fit the distance matrix you specified, please see the following image.
matrix distance and coordinates
Your input matrix gives the distances between 6 nodes, which we will call a, b, c, d, e and f. There are only 5 dimensions needed to assign coordinates to all six nodes that fit your distance matrix. Two of these measurements are imaginary, which is a consequence of breaking the triangle rule. The results were obtained using the law of cosines and partial crunching.
- a (0, 0, 0, 0, 0)
- b (73, 0, 0, 0, 0)
- c (-521.07, 510.99i, 0, 0, 0)
- d (669.05, -802.08i, 664.62, 0, 0)
- e (12.72, -163.83i, 488.13, 158.01i, 0)
- f (-103.45, 184.11i, 84.52, 138.06i, 262.62)
source to share