need an algorithm

Lets have a cube (1x1x1 m) and two points (A and B) on it surface. How to calculate the shortest way from A to B ?

Thanks in advance.

Isn't this just a 3D version of the distance between two points?

double d = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2);

I am not sure, but I think he wants the shortest distance along the surface of the cube.

Why not use the shortest distance formula for 3-d space?


In computerese:

if point 1 is (x1, y1, z1) and point 2 is (x2, y2, z2):


diffx = x2 - x1;

diffy = y2 - y1;

diffz = z2 - z1;


dist = sqrt( diffx*diffx + diffy*diffy + diffz*diffz );


(Hope there are no typos / stupid errors in the above) :-()


What is more interesting is to find the shortest distance between two non-

parallel lines in 3-d space.


Regards,


Paul McKenzie

That's right, Gary!

I need a distanse along the surface.

Its the same formula as the 3D distance between 2 points (see other responses). One of the factors (depends on the surface) will be zero.

Well, you've gotten a couple of answers about how to figure what the distance between them IS, but I get the feeling that you're interested in knowing the vector from one to the other -- i.e. the angle as well as the distance.


This is also just about like figuring a 2D angle, except that you have to figure two angles: one horizontal and the other vertical. Assuming you've got points X1, Y1, Z1 and X2, Y2, Z2, you'd typically figure an XY angle and an XZ angle (it doesn't really matter which pair of angles as long as you're consistent in how you use them).


The first angle will be arctan((Y2-Y1) / (X2-X1));

You also have to take the signs of the results into account to get the angle in the correct quadrant. Alternatively, if you're using C or C++, take a look at the atan2 function, which handles that part more or less automatically.

Your answer is correct only if the two points lie on the same surface of the cube. What if the points lie on adjacent or opposite surfaces. Look at it this way, if the points are in the same plane (2d) and on adjacent surfaces then you have described a right triangle. The questioner is after the sum of the lengths of the two legs not the hypotenuse ( which would be the shortest distance). Now project this to arbitrary 3d space and you have the problem.

You break it up into cases. *Some* of them are the following.


1) Both points in the interior of one side. (Should be easy.)


2) One point in the interior of one side, other in the interior of an adjacent side.

(I'll do more of this example in the following.)


3) One point in the interior of one side, other in interior of opposite side.


4) One point on an edge, other in the interior of one of the sides making the edge.

(Should be easy.)


There are other cases, but I don't want to do all your homework.


Now to do more on case 2. Let the first point be (x1, y1, 0) and the second be

(x2,1,z2). So this is a front and top case. You can rotate things pretty easily to

do any other situation with adjacent sides. Let the path cross the top front edge

at (xm,1,0). Now you have two paths


d1 from (x1,y1,0) to (xm,1,0)

d2 from (xm,1,0) to (x2,1,z2)


And you need to find xm that minimizes the total of d1 + d2. (In this, ^2 means squared.)


d1 = sqrt( [x1-xm]^2 + [1-y1]^2)

d2 = sqrt( [xm-x2]^2 + [z2]^2)


So you need to minimize the total. So you need to take the derivative

w.r.t. xm, find the value of xm that gives zero derivative. Then you need

to be careful about getting positive values when they need to be positive

so you get the signs right when you work out xm. And you need to be

careful that you choose the root that gives 0 < xm < 1.


Hint: The value of xm that minimized d1+d2 is *not* the value of xm that

minimizes d1^2 + d2^2.


This should be enough of a hint to get you going. Don't forget that in some cases

the shortest path may be round the other side of the cube.

When you need such an algorithm then I could deliver it...


mail or post...

Greets

Jay