Jayjay

Let A, B, P0 and P1 be two-dimensional points. The problem is to find point P on line segment P0-P1 (if exists) such that

1) distance from P to line segment AB is smaller than certain real number r, and
2) P is the closest to P0 of such points.

In other words, if we think of P as a point moving with constant speed from point P0 to P1 so that at time t=0 it's in point P0 and at time t=1 in point P1, I'm trying to figure out an algorithm that calculates the time when distance from P to line segment AB goes below a given threshold. I realize this could be done with numeric methods, but it would be nice if the algorithm wasn't computationally too expensive (I might use it to calculate balls bouncing off walls, if I can learn how to do this elegantly enough).

fando

What happens if the line segments are parallel? Do you want a unique P?

xorbie

If I understand you correctly, the problem here is that there are infinite solutions (or none, if it is too far) but you obviously cannot go through them all. If I were you, I would use calclulus. Set up a formula for distance from AB assuming a constant velocity of P0P1 (because it takes 1 s to go from P0 to P1). The function would be d(t).

Then take the derivative of d(t) and set it to 0. Wherever the derivative is equal to 0, you have either a min or max. Hopefully, whatever distance formula you have is not very tricky.

Tetlepanquetzatzin

A good start might be to solve a subtly different problem: Given points A, B, P, P', we find a point P" on the line segment P-P' such that the distance to the line segment A-B is exactly r.

Let's denote by "AB" the vector from A to B, and by "t AB" the vector AB multiplied by t. Let C be the point on A-B that is closest to P". There are two cases to consider:

CASE 1: C is located between the endpoints A and B. Geometrical considerations yield

OP" = OP + t PP'
OC = OA + s AB
CP = +/- r v

where t and s are real numbers in the interval 0 <= s,t <= 1 and v is a unit vector perpendicular to AB. Combining these equations, we obtain

+/- r v = AP + t PP' - s AB

This is a system of two linear equations with two unknowns. If PP' and AB are not parallel, t may be immediately found by taking the dot product with v, i.e.

t = (-AP*v +/- r) / (PP'*v)

Both s and t should be determined for both cases (+r and -r), and one should check if 0 <= s,t <= 1.

CASE 2: C is one of the endpoints. This case is solved using simple calculus.

It is possible that no valid solution exist (if the minimum distance between P-P' and A-B is larger than r, or if the maximum distance is smaller than r) and it is possible that one or more solutions exists. In the latter case, simply invoke your second condition and pick the solution corresponding to the smallest t.

Provided that the distance from P to A-B is larger than r, this will also solve your original problem.

Jayjay

Thanks, that sounds about right. Certainly much simpler than my back-of-the-envelope scribblings so far.