I'm working on my bachelor thesis (on Computer Science) and right now I'm having a problem about finding shortest path between two points on 3D triangular mesh that is manifold. I already read about MMP, but which computes distance function $d(x)$ between given point and vertex $x$ on mesh.

I got to know that the problem I'm solving is named Geodesics but What I really couldn't find is some good algorithm which uses A* for finding shortest path between two given points on two given vertices.

I 'invented' also algorithm which uses A* by using Euclidian Distance Heuristics and correction after finding new Point on any Edge.. I also have edges saved in half-edge structure.

So my main idea is this:

  1. We will find closest edge by A* algorithm and find on this edge point with minimalizing function $f(x) + g(x)$ where $f$ is our current distance and $g$ is heuristics(euclidean distance)
  2. Everytime we find new edge, we will unfold current mesh and find closest path to our starting point

So now my questions:

  • Do you know some research paper which talks about this problem ??
  • Why nobody wrote about algorithm that uses A* ??
  • What are your opinions about algorithm I proposed ?
  • $\begingroup$ Do you mean the shortest distance following the edges vertex by vertex, or the true geodesic distance (assuming a polyhedral surface) ? $\endgroup$
    – user16034
    Commented Mar 14, 2022 at 15:14
  • $\begingroup$ @YvesDaoust True geodesic distance, Shortest distance following edges would be quite easily done by A* Pathfinding.. $\endgroup$ Commented Mar 14, 2022 at 15:18
  • $\begingroup$ Ok, I agree with your method. Maybe you can replace the Euclidean distance heuristic precisely by using the edge-following distance. $\endgroup$
    – user16034
    Commented Mar 14, 2022 at 15:27
  • $\begingroup$ @YvesDaoust well If I use edge-following heuristics, then the heuristic is no longer admissible (estimated distance is not lower or equal to real distance) $\endgroup$ Commented Mar 14, 2022 at 15:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.