Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) : http://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 :

share|improve this question
    
What's wrong with placing the vertices randomly and adding all edges with labels accordingly? –  Hagen von Eitzen Feb 10 '13 at 13:57
    
Do you want the graph to be cartesian coordinates such that the euclidean distances are maintained? If so, in your sample graph, G and D are really far away, despite a Euclidean distance of only 3. –  Paresh Feb 10 '13 at 14:05
    
Also, your link to Alberto Murta's paper gives the steps in some details. –  Paresh Feb 10 '13 at 14:20
    
Paresh : you are right, the graph is wrong, but it does show an example. In fact, I need a cartesian plan. I need to get a configuration that fits with the matrix whether or not they are many other solutions. As I am pretty begginer at maths, I though someone better than me could help me to find an easy-to-understand way to do it. The final goal is to put objects on a cartesian plan only by using their relative distance. Thanks a lot =) –  Charaf Feb 10 '13 at 15:02

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
Thanks a lot ! Your answer made it easier for me to understand. By the way, now I know the importance of math when we want to be real engineers (I know many engineers like me who are just completly dumb at maths). I'll post here an algoritm when I success in making it work. Thanks again. –  Charaf Feb 11 '13 at 16:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.