3
$\begingroup$

I need to find true shortest path between two points. true means that shortest path can be laid both through the vertices, and through the edges.

Input

  • Set of triangles, given by coordinates of 3D-points.
  • Source and target points.

Output

  • Sequence of 3D-points representing a true shortest path from source to target.

I found video with visualization here. But I couldn't find ready algorithm, so I tried to create my own. Please make my algorithm review and let me know whether it is correct or it has issues. Also I will be gratefull if you have ready algorithm.

My algorighm

  1. Find the shortest path via only vertices (E.g. by Dijkstra).
  2. Get triangles (faces) that go along the path. In the next steps we will consider vertices that belong only to these triangles.
  3. Find another vertices that can lie on true shortest path but are not known vertices. These are the points that are placed on edges.

    foreach startVertex in vertices
    {
        foreach finishVertex in vertices
        {
            // Create line segment between two vertices.
            lineSegment = ToLineSegment(startVertex, finishVertex);
    
            // Make lineSegement-projection on edges.
            // Return points that are the intersection of the projection and the edges. 
            additionalVertices = FindIntersectWithEdges(lineSegment);
            result.AddResult(additionalVertices); 
        }
    }
    
  4. Find the shortest path via all vertices that received in previous two steps (E.g. by Dijkstra).
$\endgroup$
  • $\begingroup$ How about reducing your problem to classical shortest path? $\endgroup$ – Yuval Filmus Nov 14 '17 at 21:24
  • $\begingroup$ @YuvalFilmus, Unfortunately no. I need true shortest path. The same as in the specified video. $\endgroup$ – Palindromer Nov 14 '17 at 22:06
  • $\begingroup$ I don't understand what you mean by "true shortest path". What does it mean for a path to be "laid both through the vertices, and through the edges"? Can you provide a mathematical definition? $\endgroup$ – D.W. Nov 16 '17 at 0:59
  • $\begingroup$ @D.W. True (or geodesic) shortest path - shortest path between two points on the boundary of a polyhedron. The shortest path must lead along the surface of the polyhedron. $\endgroup$ – Palindromer Nov 16 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.