2D Eculidian matrix to 2D cartesian graph/plan

Question

Can anyone help ?

I am trying to convert a 2D matrix of distances to a 2D graph.

For instance, I would like to go from this :

|     A  B  C  D  E  F  G
|  A  -  2  2  5  1  3  5
|  B     -  2  4  4  2  1
|  C        -  1  2  4  8
|  D           -  4  5  3
|  E              -  1  2
|  F                 -  1
|  G                    -

To this (link to image) : https://i.stack.imgur.com/j8Moa.png

To show this example, I've used photoshop and GraphViz

graph G { node [shape=circle,height=.2,width=.2]; a -- b [len=2,label="2"]; a -- c [len=2,label="2"]; a -- d [len=5,label="5"]; a -- e [len=1,label="1"]; a -- f [len=3,label="3"]; a -- g [len=5,label="5"]; b -- c [len=2,label="2"]; b -- d [len=4,label="4"]; b -- e [len=4,label="4"]; b -- f [len=2,label="2"]; b -- g [len=1,label="1"]; c -- d [len=1,label="1"]; c -- e [len=2,label="2"]; c -- f [len=4,label="4"]; c -- g [len=8,label="8"]; d -- e [len=4,label="4"]; d -- f [len=5,label="5"]; d -- g [len=3,label="3"]; e -- f [len=1,label="1"]; e -- g [len=2,label="2"]; f -- g [len=1,label="1"]; }

Does anyone know know an easy way to do that ?

I would like to do it under mathlab or java.

Thanks a lot !

References :

• Create a graph from a set of distances
• http://albertomurta.wikispaces.com/file/view/coordinates_from_distances.pdf
• https://stackoverflow.com/questions/13513455/drawing-a-graph-or-a-network-from-a-distance-matrix

Answer 1

If you're given distances between every pair of nodes, then your problem is seriously overdetermined, and it's unlikely that there's a solution at all unless the input data have very special properties.

For the sample data you show, the distances between A, B, and G are 2, 5, and 1, which violates the triangle inequality so you've already an impossibility on your hands there.

If you have distances that you have reason to think do admit a solution, you can use a naive point-by-point algorithm:

1. Start by placing the first two points $A$ and $B$ horizontally beside each other on the $x$ axis with the appropriate distance.

2. For each new point, look at its known distances to $A$ and $B$. Use the distance formula $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ to get two equations for the coordinates of $P$. Square each side of each equation to get rid of the square roots, and subtract the equations from each other in order to get rid of the $x_P^2$ and $y_P^2$ terms. Noting that $y_A$ and $y_B$ are both $0$ and $x_A$ and $x_B$ are both known, this gives you a linear equation in $x_P$ that is easily solved.

3. Now you can find $y_P$, up to its sign, by the Pythagorean theorem given the distance $AB$. If this is the first point with a nonzero $y$ you place, select the sign of its $y$ arbitrarily; otherwise compute the distances between the two possible positions and a point you've already placed off-axis and choose the position that fits your data best.