[Math] Algorithm to find the shortest path between 2 points on a 3D triangle strip

algorithmscomputational geometrygeodesicgeometry

I have a triangle strip in 3D.
see illustration here

The triangles do not lie in one plane. The number of triangles is limited (around 20). Furthermore I have two points (the start point and the end point). The two points lie either on an edge of a triangle or inside a triangle.

For programming I am looking for an algorithm which calculates the polyline representing the shortest line between the two points on the triangle strip.

I had a look at different books, papers, discussions etc on the subject of calculating the shortest path or the geodesic path on triangle meshes. The suggested algorithms seem quite complex.

Since my setup looks simpler (only a triangle strip – not a mesh, limited number of triangles) I try to find an easier solution.

One idea is to flatten the triangle strip so that all triangles lie in the plane of the first triangle. The plan is to rotate the second triangle around its connecting edge with the first triangle so that it becomes in plane with the first triangle. Then I continue this method for the other triangles until all of them are in plane. Then I draw a straight line between the two points and calculate the intersections with the connecting triangle edges to get the polyline.

Two questions:

  1. Is such a claculated polyline really the shortest path between the two
    points?

  2. What other strategies or algorithms (simple and fast) could be used to solve the problem?

Best Answer

A partial answer: Yes, a straight line on the flattened strip is the shortest path. Think about what happenes to the total path length as you shift any of the intersection points of this path with a triangle edge: the path gets longer.

Be careful, though. Your strip may connect in such a way that a straight line joining the two points will leave the strip. You’ll have to take that possibility into account for a full solution.

Update: I haven’t proven this, but my intuition tells me that if the straight-line path does leave the strip, then adjusting it to get the shortest path is pretty simple. Find the first edge crossing that takes you off the strip and move this intersection to the vertex of that triangle that’s nearest the ultimate goal. Then, take that as your new starting point, draw the straight line from there and iterate.

Related Question