CODEWITHSUNDEEP
math3dlinedistance
Bryan Brown TheDudeFromCI
Bryan Brown TheDudeFromCI

Reputation: 144

Shortest Distance Between 3 Points Along a Line Segment

I'm currently working on a pathfinding algorithm for navigation meshes. Skipping the details, I need to find an algorithm for finding the shortest distance between three points along a line segment.

The path much travel from point A to B to C. A and C are fixed points in 3D space. B is a point located somewhere on the line segment DE. What location of B minimizes the distance of the path ABC?

Upvotes: 1

Views: 2357

Answers (1)

Rory Daulton
Rory Daulton

Reputation: 22534

You do not give any algorithm or code of your own, so I'll just state an algorithm in broad terms. If you need more details, such as the mathematical formulas or code, show us more of the work you have done on the problem then I will be glad to help more.

This is an algorithm without calculus but using 3D geometry. The overall idea is to find the point B on line DE that minimizes the path A-to-B-to-C. If that point is on the segment DE, that is your answer. If the point lies beyond D, then D is your answer, and if the point lies beyond E then E is your answer.

To find that point B on line DE, consider the altitude from point A to line DE and also the altitude from point C to line DE. Now rotate point C around line DE so the new point C' is in the same plane as point A and line DE but on the opposite side of the line from point A. Now find the intersection of segment AC' and line DE--there certainly is one. That intersection point is your point B on line DE.

All that would be made easier by making a rigid transformation of the 3D space to place point D at the origin, point E on the positive x-axis, and point A in the upper half-plane above the x-axis. You would then find the desired point, and then do the inverse rigid transformation on point B.

Do you understand? I am not now in a position to show you a graphic of that algorithm, though I could make one up tomorrow. As I said, show some work of your own then I will be glad to give more details.

I should briefly mention two other approaches. A calculus approach uses the derivative of the expression of the path length. This will involve solving a cubic polynomial equation that has only one real root. A computer approach uses the golden-section algorithm or something similar to approximate the minimum of the path-length expression. Choose your poison. (None of these approaches are exactly easy.)

Upvotes: 2

Related Questions