Best way to find the Coordinates of a Point on a Line-Segment a specified Distance Away from another Point [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

Image of the problem at:

In my code I have 4 points: Q, R ,S , T.

I know the following

• Coordinates for R, T, and S;
• That segment RT < RQ < RS;
• I need to figure out the coordinates of Q.

I already know point Q can be found on the line segment TS. However I need to get the coordinates for Q and I need it to be a relatively efficient calculation.

I have several solutions for th开发者_高级运维is problem but they are all so convoluted and long I know I must be doing something wrong. I feel certain there must a simple elegant way to solve this. The best solution would be one that minimizes the number of more intensive calculations but that also isn't ridiculously long.

---

Q is the intersecting point between a circle of radius d around R and the line TS, which leads to a quadratic equation with a number of parameters in the coefficients. I don't know if the following if “the best” solution (it may even be better to use a numerical solver in between), but it is completely worked out. Because I think it's more readable, I've changed your coordinate names to put T at (T1, T2), S at (S1, S2) and, to keep the formulas shorter, R at (0, 0) – just adjust S and T and the returned values accordingly.

tmp1 = S1^2 - S2*T2 - S1*T1 + S2^2;
tmp2 = sqrt(- S1^2*T2^2 + S1^2*d^2 + 2*S1*S2*T1*T2 - 2*S1*T1*d^2 -
      S2^2*T1^2 + S2^2*d^2 - 2*S2*T2*d^2 + T1^2*d^2 + T2^2*d^2);
tmp3 = S1^2 - 2*S1*T1 + S2^2 - 2*S2*T2 + T1^1 + T2^2;
t = (tmp1 + tmp2)/tmp3;
if (0 > t || t > 1) {
  // pick the other solution instead
  t = (tmp1 - tmp2)/tmp3;
}
Q1 = S1+t*(T1-S1);
Q2 = S2+t*(T2-S2);

Obviously, I take no warranties that I made no typos etc. :-)

EDIT: Alternatively, you could also get a good approximation by some iterative method (say, Newton) to find a zero of dist(S+t*(T-S), R)-d, as a function of t in [0,1]. That would take nine seven multiplications and one division per Newton step, if I count correctly. Re-using the names from above, that would look something like this:

t = 0.5;
d2 = d^2;
S1T1 = S1 - T1;
S2T2 = S2 - T2;
do {
  tS1T1 = S1 - t*S1T1;
  tS2T2 = S2 - t*S2T2;
  f = tS1T1*tS1T1 + tS2T2*tS2T2 - d2;
  fp = 2*(S1T1*tS1T1 + S2T2*tS2T2);
  t = t + f/fp;
} while (f > eps);

Set eps to control your required accuracy, but do not set it too low – computing f does involve a subtraction that will have serious cancellation problems near the solution.

---

Since there are two solutions Q on the (TS) line (with only one solution between T and S), any solution probably involves some choice of sign, or arccos(), etc.

Therefore, a good solution is probably to put Q on the (TS) line like so (with vectors implied):

(1)   TQ(t) = t * TS

(where O is some origin). Requiring that Q be at a distance d from R gives a 2nd degree equation in t, which is easy to solve (again, vectors are implied):

d^2 = |RQ(t)|^2 = |RT + TQ(t)|^2

The coordinates of Q can then be obtained by putting a solution t0 into equation (1), via OQ(t0) = OT + TQ(t). The solution 0 <= t <= 1 must be chosen, so that Q lies between T and S.

Now, it may happen that the final formula has some simple interpretation in terms of trigonometric functions… Maybe you can tell us what value of t and what coordinates you find with this method and we can look for a simpler formula?