Stretchy graph problem
March 23, 2006 10:28 AM Subscribe
Say I have 5 points: a,b,c,d,e. I know the position of each one at t=0: pa0,pb0 etc. Now say that at t=1, the distance between each one changes, so I know Dab1,Dac1...Dde1. Is there an equation or algorithm which will allow me to know (or aproximate) the positions at t=1 : pa1...pe1?
Does this actually have a solution? What branch of mathematics or geometry deals with this kind of problem?
Sorry if my terminology or notation is off, any corrections are most welcome.
My final objective is to do something similar to those dynamic maps that stretch in real time according to, say, travel times, cost, etc.
Does this actually have a solution? What branch of mathematics or geometry deals with this kind of problem?
Sorry if my terminology or notation is off, any corrections are most welcome.
My final objective is to do something similar to those dynamic maps that stretch in real time according to, say, travel times, cost, etc.
Response by poster: Shutter: what if we choose one of the points as an arbitrary center, say point a?
posted by skree at 10:36 AM on March 23, 2006
posted by skree at 10:36 AM on March 23, 2006
You might want to look into graph theory, although that's going to get into connectedness and spanning more than it is distances.
posted by mikeh at 10:47 AM on March 23, 2006
posted by mikeh at 10:47 AM on March 23, 2006
There doesn't seem to much of a frame of reference if all the movements are independent. Probably by using calculus, you could get some sort of approximation.
posted by JJ86 at 10:52 AM on March 23, 2006
posted by JJ86 at 10:52 AM on March 23, 2006
skree:
suppose the five points are initially on a line
Now, at t=1, distances have changed. I tell you, if there is any solution, there are at least two: just mirror your solution along the initial line.
Now, throw away the line assumption: the points are arbitrarily distributed at t=0. You can still see that there is a way to mirror a solution to t=1 in order to arrive at a new solution. The question is: in this case, it MAKES a difference: depending on your choice of solution, the points will have moved more or less. shitty graphical example:
posted by qvantamon at 10:53 AM on March 23, 2006
suppose the five points are initially on a line
Now, at t=1, distances have changed. I tell you, if there is any solution, there are at least two: just mirror your solution along the initial line.
Now, throw away the line assumption: the points are arbitrarily distributed at t=0. You can still see that there is a way to mirror a solution to t=1 in order to arrive at a new solution. The question is: in this case, it MAKES a difference: depending on your choice of solution, the points will have moved more or less. shitty graphical example:
t=0:
a
c
b
t=1:
a
c
b
OR
b
c
a
In the first case, b moved much less compared to a than in the second case. More than that: In one case, b crossed the a-c line, and in other it did not.posted by qvantamon at 10:53 AM on March 23, 2006
If you knew that the rate of movement of all particles was a constant then it should be much easier. Then the difference between pa1 and pa2 would be same as pb1 and pb2, etc. With that info it would be a simpler matter.
posted by JJ86 at 10:55 AM on March 23, 2006
posted by JJ86 at 10:55 AM on March 23, 2006
by the way, if you fix 3 non-colinear points, you CAN locate all the rest, just by the distances. But with 2 fixed points, you get the symmetry problem (two solutions, mirrored along the line formed by the two fixed points). With only one fixed point, you can rotate, mirror, twist, and find a LOT of solutions.
posted by qvantamon at 10:59 AM on March 23, 2006
posted by qvantamon at 10:59 AM on March 23, 2006
qvantamon, but you still need a frame of reference to make that comparison. Did b cross the a-c axis, or did a cross the b-c axis? Which points actually moved?
posted by JJ86 at 10:59 AM on March 23, 2006
posted by JJ86 at 10:59 AM on March 23, 2006
When you say distance, do you mean a scalar or a vector Skree? Scalar:5 miles. Vector:4 miles east and 3 miles north.
With scalars, it's still going to be non-unique. With vector displacements, and a stationary reference point, then yes, you can indeed determine the new positions of everything.
posted by Shutter at 11:00 AM on March 23, 2006
With scalars, it's still going to be non-unique. With vector displacements, and a stationary reference point, then yes, you can indeed determine the new positions of everything.
posted by Shutter at 11:00 AM on March 23, 2006
You could look at this as a graph layout problem. The points are the "nodes" of the graph. You could add edges between the nodes for where it makes sense (maybe an edge between every set of 2 nodes). Then you could change the weight of the edges, and use a graph layout algorithm to redraw it.
See http://simg.cs.arizona.edu/pages/layout.html (something like the merged layout).
So for example, an increased travel time between to points would mean you change the weight of the edge between those 2 nodes and then re-layout the graph.
posted by gus at 11:03 AM on March 23, 2006
See http://simg.cs.arizona.edu/pages/layout.html (something like the merged layout).
So for example, an increased travel time between to points would mean you change the weight of the edge between those 2 nodes and then re-layout the graph.
posted by gus at 11:03 AM on March 23, 2006
You can place constraints on how far any individual point can move in an iteration: This would remove the "flipping" problem that qvantamon points out.
However, you can still never be safe from slight rotations or translations of the entire "structure." The data you have just isn't sufficient to define that.
posted by vacapinta at 11:09 AM on March 23, 2006
However, you can still never be safe from slight rotations or translations of the entire "structure." The data you have just isn't sufficient to define that.
posted by vacapinta at 11:09 AM on March 23, 2006
What's your final application?
One way to implement this would be to simulate damped springs connecting the points.
When the distance between two points changed, you would make it so that the spring was in compression (if the distance decreased) or in tension (if the distance decreased).
Then when the distances changed, the graph would bounce to its new position, with new lengths. Introduce damping so the points don't oscillate.
You can use a Runge-Kutta method to simulate this.
posted by driveler at 11:11 AM on March 23, 2006
One way to implement this would be to simulate damped springs connecting the points.
When the distance between two points changed, you would make it so that the spring was in compression (if the distance decreased) or in tension (if the distance decreased).
Then when the distances changed, the graph would bounce to its new position, with new lengths. Introduce damping so the points don't oscillate.
You can use a Runge-Kutta method to simulate this.
posted by driveler at 11:11 AM on March 23, 2006
My first insinct was to agree that there was no unique solution. But now I'm not sure. Keep it simple and take just 3 points -- a, b, c. I think there may be some trilateration or triangulation stuff going on that might constrain the solution a bit. Not that I'm well versed in the subject. See what you think.
posted by bim at 11:24 AM on March 23, 2006
posted by bim at 11:24 AM on March 23, 2006
The important bit missing from the question is that you want (I assume) to minimize the total distance each "point" moves (or perhaps some similar thing like the sum of the squares of the distances moved).
I suspect that there should always be a unique solution if you measure positions relative to one of the points, but I can't imagine how one would prove it.
What driveler described with the springs sounds like an excellent way to do it. I don't remember enough calculus to follow that method, though. The simple and obvious method of just adding up all the forces on each point and iteratively moving it that way may be less efficient but I think it would work.
posted by sfenders at 11:28 AM on March 23, 2006
I suspect that there should always be a unique solution if you measure positions relative to one of the points, but I can't imagine how one would prove it.
What driveler described with the springs sounds like an excellent way to do it. I don't remember enough calculus to follow that method, though. The simple and obvious method of just adding up all the forces on each point and iteratively moving it that way may be less efficient but I think it would work.
posted by sfenders at 11:28 AM on March 23, 2006
Lastly, this problem sounds an awful lot like something the good folks over at Sourceforge are working on.
Good luck.
posted by bim at 11:49 AM on March 23, 2006
Good luck.
posted by bim at 11:49 AM on March 23, 2006
Based on the question, there isn't enough information. Knowing the distance between point A0 and point A1 doesn't tell you which direction A1 is relative to A0.
posted by knave at 11:55 AM on March 23, 2006
posted by knave at 11:55 AM on March 23, 2006
Now that I think about it, Runge-Kutta is just a generalized type of Euler integration, which is simpler and should work just fine for visualization.
You'd set the initial positions and connections of all the points. Then use Hooke's law to write out all the forces acting on the points in vector form and set all the velocities of the points to 0.
When the distance between a pair of points changes, there will be a force acting on those points. Hooke's law will tell you the acceleration, then from that you can calculate the velocity and new position (after a small time step) using Euler integration.
This will change the distances between the other points, which now also have forces acting on them, so you have to apply Euler integration to find the new accelerations, velocities, and positions for all the points at each time step. Repeat this process until all the points settle.
You'll probably have to add damping (just subtract a constant fraction of the velocity from the acceleration) to the springs and fix one point to keep things stable.
posted by driveler at 11:56 AM on March 23, 2006
You'd set the initial positions and connections of all the points. Then use Hooke's law to write out all the forces acting on the points in vector form and set all the velocities of the points to 0.
When the distance between a pair of points changes, there will be a force acting on those points. Hooke's law will tell you the acceleration, then from that you can calculate the velocity and new position (after a small time step) using Euler integration.
This will change the distances between the other points, which now also have forces acting on them, so you have to apply Euler integration to find the new accelerations, velocities, and positions for all the points at each time step. Repeat this process until all the points settle.
You'll probably have to add damping (just subtract a constant fraction of the velocity from the acceleration) to the springs and fix one point to keep things stable.
posted by driveler at 11:56 AM on March 23, 2006
Since the distance is intended to represent some other relationship, there won't always be any ideal solution. For example, you might want a distance of 1 unit between points A and B, 200 between A and C, and 1 between B and C. So, that might complicate things.
posted by sfenders at 1:21 PM on March 23, 2006
posted by sfenders at 1:21 PM on March 23, 2006
I'm not familiar with stretchy maps, but..
If you only have cross-distance terms (like Dab1, but not Da01) then you have a seriously under specified problem. The entire cluster could move an arbitrary distance in that time step.. You could constrain the motion of the entire cluster to 0 - keeping the centroid the same. After that you still need vector distances, or some other directional constraints..
Since I'm not familiar with that type of map, I can't say how reasonable driveler's spring idea is. I can say that there is no need for numerical integration though. The dynamic system you would be creating is linear, and an analytic solution exists - basically the matrix exponential.
posted by Chuckles at 1:28 PM on March 23, 2006
If you only have cross-distance terms (like Dab1, but not Da01) then you have a seriously under specified problem. The entire cluster could move an arbitrary distance in that time step.. You could constrain the motion of the entire cluster to 0 - keeping the centroid the same. After that you still need vector distances, or some other directional constraints..
Since I'm not familiar with that type of map, I can't say how reasonable driveler's spring idea is. I can say that there is no need for numerical integration though. The dynamic system you would be creating is linear, and an analytic solution exists - basically the matrix exponential.
posted by Chuckles at 1:28 PM on March 23, 2006
Let's take the simplest case and assume that we are talking about 3 points in a two dimensional space.
Let the distance between a and b equal 1 (so point b lies on a circle around point a with a radius of 1).
Let the distance between a and c be 3 (so point c lies on a circle around point a with a radius of 3). What can we infer about the relationship between b and c?
I DO know that the distance between b & c has a maximum value of 4 (when all points lie in a line with a between b and c) and a minimum value of 2 (when all points lie on a straight line with b between a & c). Any value for b-c in between 2 and 4 create a triangle using the three points.
So, once the distance b-c is given, we DO know the relative postitions of a, b, and c (the look of the triangle that is created). We don't know the absolute positions, though, unless one of the points is fixed i.e., we don't know exactly where that triangle is anchored in the two dimensional space.
...and if you are a glutton for punishment, there's another askMeFi question on the physics of car accidents and roll overs!
posted by bim at 2:36 PM on March 23, 2006
Let the distance between a and b equal 1 (so point b lies on a circle around point a with a radius of 1).
Let the distance between a and c be 3 (so point c lies on a circle around point a with a radius of 3). What can we infer about the relationship between b and c?
I DO know that the distance between b & c has a maximum value of 4 (when all points lie in a line with a between b and c) and a minimum value of 2 (when all points lie on a straight line with b between a & c). Any value for b-c in between 2 and 4 create a triangle using the three points.
So, once the distance b-c is given, we DO know the relative postitions of a, b, and c (the look of the triangle that is created). We don't know the absolute positions, though, unless one of the points is fixed i.e., we don't know exactly where that triangle is anchored in the two dimensional space.
...and if you are a glutton for punishment, there's another askMeFi question on the physics of car accidents and roll overs!
posted by bim at 2:36 PM on March 23, 2006
Response by poster: When you say distance, do you mean a scalar or a vector Skree?
Scalar, definitely
What's your final application?
A stretchy map, that is one that rearranges to fit changing distances between its nodes/cities/metro stations.
One way to implement this would be to simulate damped springs connecting the points.
I'd thought of that, especially since not every set of distances would be solvable, you could settle on a static or dynamic closest-approximation.
The important bit missing from the question is that you want (I assume) to minimize the total distance each "point" moves
Nope, no optimization intended, just visualization.
The entire cluster could move an arbitrary distance in that time step..
Thing is, I only care about relative positions between points, not the absolute position of the entire system.
One thing which I didn't state and might simplify the problem is that it would be valid to view the entire system from one arbitrary point, and even just give the distances from that one point.
Sorry for underspecifying the problem, and thanks for all the answers so far. The discussion itself is interesting, IMO.
posted by skree at 2:58 PM on March 23, 2006
Scalar, definitely
What's your final application?
A stretchy map, that is one that rearranges to fit changing distances between its nodes/cities/metro stations.
One way to implement this would be to simulate damped springs connecting the points.
I'd thought of that, especially since not every set of distances would be solvable, you could settle on a static or dynamic closest-approximation.
The important bit missing from the question is that you want (I assume) to minimize the total distance each "point" moves
Nope, no optimization intended, just visualization.
The entire cluster could move an arbitrary distance in that time step..
Thing is, I only care about relative positions between points, not the absolute position of the entire system.
One thing which I didn't state and might simplify the problem is that it would be valid to view the entire system from one arbitrary point, and even just give the distances from that one point.
Sorry for underspecifying the problem, and thanks for all the answers so far. The discussion itself is interesting, IMO.
posted by skree at 2:58 PM on March 23, 2006
Response by poster: Here's something which is similar to the application I have in mind, though not identical.
I know I could just look at their source code, but I'm still interested in the more abstract approach to the problem, or any other better solutions.
posted by skree at 3:10 PM on March 23, 2006
I know I could just look at their source code, but I'm still interested in the more abstract approach to the problem, or any other better solutions.
posted by skree at 3:10 PM on March 23, 2006
shutter got it right with the first answer. Assume your five points are all rigidly connected -- they're five notches on stick, for instance, five points on a ruler, whatever.
No matter now the stick moves in space, the relative distance of the notches from each other stays the same -- that's the definition of "rigidly connected".
So there's no way to calculate absolute positions for the relative position of the notches.
posted by orthogonality at 6:33 PM on March 23, 2006
No matter now the stick moves in space, the relative distance of the notches from each other stays the same -- that's the definition of "rigidly connected".
So there's no way to calculate absolute positions for the relative position of the notches.
posted by orthogonality at 6:33 PM on March 23, 2006
All right...I'll buy the "orthogonal" answer. :) Good example.
posted by bim at 6:44 PM on March 23, 2006
posted by bim at 6:44 PM on March 23, 2006
Response by poster: But I'm not assuming the points are rigidly connected, in fact I assume the opposite, and I only care about the position of each point in relation to each other, not the absolute position of the whole system.
posted by skree at 9:43 PM on March 23, 2006
posted by skree at 9:43 PM on March 23, 2006
In the example, they do not have x- and y-coordinates for separations, but they do have distance and direction, which comes to the same thing.
Which is to say, I believe the way they solve the underspecified issue is by maintaining the direction between Stationi, Stationi+1 and Stationi-1 for the entire system (it looks a little like some arms are rotating, but on closer inspection I believe they are not).
As for how they get the stretchy look.. I think they start iterating out along the lines, and along new lines each time a junction is hit. At each new station the updated position in the map is calculated, but they don't just move that station, they move the entire daughter branch and everything connected to it. They make moves in increments, either a certain number of increments per move, or a certain distance per increment. Some daughter branches will be connected by more than one junction, which will create loops. They have to do something to avoid getting caught that way, but I have no idea how they do it.
posted by Chuckles at 10:25 PM on March 23, 2006
Which is to say, I believe the way they solve the underspecified issue is by maintaining the direction between Stationi, Stationi+1 and Stationi-1 for the entire system (it looks a little like some arms are rotating, but on closer inspection I believe they are not).
As for how they get the stretchy look.. I think they start iterating out along the lines, and along new lines each time a junction is hit. At each new station the updated position in the map is calculated, but they don't just move that station, they move the entire daughter branch and everything connected to it. They make moves in increments, either a certain number of increments per move, or a certain distance per increment. Some daughter branches will be connected by more than one junction, which will create loops. They have to do something to avoid getting caught that way, but I have no idea how they do it.
posted by Chuckles at 10:25 PM on March 23, 2006
skree writes "But I'm not assuming the points are rigidly connected, in fact I assume the opposite, "
Ok, but if the points are free to arbitrarily move relative to each other, each point's movement can be of the same magnitude and direction, which means they'd not move at all relatively to any other points. (That again was shutter's answer: what if all the points move north by one unit?)
Since they all could move in the same direction with the same magnitude, you have to ask yourself if you could solve the problem if they do. Since you can't solve the problem for that particular case, that means you can't solve the problem for any arbitrary case., which means there's no general solution.
If fact, you can quickly convince yourself that the relative positions of the points have absolutely nothing to do with their absolute position. Think of any set of points: the vertices of a pentagon, for example. Imagine that pentagon somewhere on a 2-D plane. As a "cut-out" paper pentagon laid on top of a piece of paper.
Now rotate or shift that pentagon. That is, move the pentagon around on the paper. Note that as you shift the pentagon around the plane, as you rotate it, the position of each point relative to each other point remains the same, the distant of any point to any other point remains the same. Your cut-out's shape and size doesn't change. Any point on the surface of the pentagon cut-out maintains the exact same distance and relative vector from any other point on the surface of the cut-out.
In all that movement, the relative positions don't change at all.
posted by orthogonality at 10:25 PM on March 23, 2006
Ok, but if the points are free to arbitrarily move relative to each other, each point's movement can be of the same magnitude and direction, which means they'd not move at all relatively to any other points. (That again was shutter's answer: what if all the points move north by one unit?)
Since they all could move in the same direction with the same magnitude, you have to ask yourself if you could solve the problem if they do. Since you can't solve the problem for that particular case, that means you can't solve the problem for any arbitrary case., which means there's no general solution.
If fact, you can quickly convince yourself that the relative positions of the points have absolutely nothing to do with their absolute position. Think of any set of points: the vertices of a pentagon, for example. Imagine that pentagon somewhere on a 2-D plane. As a "cut-out" paper pentagon laid on top of a piece of paper.
Now rotate or shift that pentagon. That is, move the pentagon around on the paper. Note that as you shift the pentagon around the plane, as you rotate it, the position of each point relative to each other point remains the same, the distant of any point to any other point remains the same. Your cut-out's shape and size doesn't change. Any point on the surface of the pentagon cut-out maintains the exact same distance and relative vector from any other point on the surface of the cut-out.
In all that movement, the relative positions don't change at all.
posted by orthogonality at 10:25 PM on March 23, 2006
Response by poster: orthogonality: I understand all that, but you're still assuming the relative position of the points is fixed. My first assumption is the exact opposite, that the distances between the points change. I don't care about the absolute position of the overall system, only the relative one between the points. If we start out with all the points on some rigid surface, the answer is trivial and I wouldn't have asked it in the first place.
Great answers everyone, you've given me much to mull over, and learn, of course.
posted by skree at 5:53 AM on March 24, 2006
Great answers everyone, you've given me much to mull over, and learn, of course.
posted by skree at 5:53 AM on March 24, 2006
More thoughts on using the simulated springs: it wouldn't need to be anything much like a realistic physical simulation, so I don't see any need to even keep track of acceleration and momentum. Just move the points at each iteration by a distance proportional to the force, perhaps scaling down the distances moved at each step. The imagined "springs" wouldn't have to follow Hooke's law. If you wanted to give more importance to closer relationships, they could get less powerful the longer they got. There are some situations where it'd get "stuck", like for instance if three points in a line had to be arranged in a triangle, there would be two different ways to do it with no way to decide between them. So, adding some small random motion at each step should solve that.
This might result in something more interesting than that London Tube map, which seems relatively simple. I think a cartogram would be more closely related.
posted by sfenders at 6:32 AM on March 24, 2006
This might result in something more interesting than that London Tube map, which seems relatively simple. I think a cartogram would be more closely related.
posted by sfenders at 6:32 AM on March 24, 2006
Skree, I think that what you're looking for can be accomplished. Once you're in the land of "dealing with maps" there are all sorts of nifty contstraints you can impose on the visualization to make things work. Not that it'll be easy...but if it were easy someone else would have done it by now right?
posted by Shutter at 8:11 AM on March 24, 2006
posted by Shutter at 8:11 AM on March 24, 2006
Response by poster: sfenders: good call on the cartogram reference, as that's pretty close to the final application. Plus, now I know what the damn things are called!
Plus, you're right on the not-needing physical verosimilitude.
Shutter: I'm all about the nifty constraints.
posted by skree at 9:01 AM on March 24, 2006
Plus, you're right on the not-needing physical verosimilitude.
Shutter: I'm all about the nifty constraints.
posted by skree at 9:01 AM on March 24, 2006
This thread is closed to new comments.
posted by Shutter at 10:34 AM on March 23, 2006