<p>The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source <span class="math-container">$v$</span> from a point <span class="math-container">$p$</span> is <span class="math-container">$||v-p'|| + ||p - p'||$</span> where <span class="math-container">$p'$</span> is the intersection of the line <span class="math-container">$\overline{vp}$</span> with the current edge. In cases where <span class="math-container">$p'$</span> is &quot;behind&quot; <span class="math-container">$p$</span> with respect to <span class="math-container">$v$</span> we set the distance to the edge to be infinity.</p>
<p>The above seems to work in the simple tests I have generated at minimum.</p>

CC BY-SA 4.0
2020-07-06T00:08:13.977Z
2020-07-06T00:08:13.977Z
Makogan
<p>The following is an excerpt from a <a href="http://hhoppe.com/geodesics.pdf" rel="nofollow noreferrer">2005 paper</a> on geodesics on triangular meshes, taken from section 3.5</p>
<p><a href="https://i.sstatic.net/lvE1X.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lvE1X.png" alt="enter image description here" /></a></p>
<p>In this case <span class="math-container">$p$</span> is a point on some arbitrary face in a mesh, <span class="math-container">$p'$</span> is a point on one of the 3 edges in the triangle and <span class="math-container">$D(p')$</span> is the geodesic distance to that point.</p>
<p>I am very confused as to how this minimization is achieved. The paper doesn't go into detail, so I assume it's trivial, but I am not seeing the solution of the top of my head.</p>
<p>Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point <span class="math-container">$p$</span> onto the segment or one of the end points of the segment (depending on where <span class="math-container">$p$</span> is located with respect to the segment).</p>
<p>However, this is not necessarily the point that minimizes the expression <span class="math-container">$||p - p'|| + D(p')$</span> or in other words, <span class="math-container">$p'$</span> is not, in general, the orthogonal projection of <span class="math-container">$p$</span> onto the segment.</p>
<p>The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.</p>
<p>I have drawn a diagram on Geogebra to show the problem:</p>
<p><a href="https://i.sstatic.net/FmfBf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FmfBf.png" alt="enter image description here" /></a></p>
<p><span class="math-container">$\overline{BA}$</span> is the segment, <span class="math-container">$C$</span> is the point we are looking to minimize the distance from. <span class="math-container">$D$</span> is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), <span class="math-container">$E$</span> is the orthogonal projection of <span class="math-container">$C$</span> onto <span class="math-container">$\overline{BA}$</span>. Clearly the optimal point is somewhere between <span class="math-container">$E$</span> and <span class="math-container">$D$</span> but I don't know how to find it.</p>

CC BY-SA 4.0
2020-07-04T07:08:56.413Z
Doesn't 4.3 and onwards deal with this? It's probably also a good idea to consider: https://code.google.com/archive/p/geodesic/wikis/ExactGeodesic.wiki
lightxbulb
CC BY-SA 4.0
2020-07-04T20:03:00.100Z
Unfortunately section 4, section 4,3 included deals with their approximating method, however I need to use the exact geodesic, not the approximation. Those notes are indeed interesting, but they don't seem to address the problem I am currently facing, at minimum not explicitly. I have a hypothesis as to what the proper way to do this is, I am testing it right now, if successful I will answer my own question.
Makogan
<mathematics><computational-geometry><mesh><geometry>
Fast and exact Geodesics on meshes, Backtracking confusion
Makogan
# Fast and exact Geodesics on meshes, Backtracking confusion

(Asked by: username_0 on 2020-07-04)

The following is an excerpt from a [2005 paper](http://hhoppe.com/geodesics.pdf) on geodesics on triangular meshes, taken from section 3.5

[![enter image description here](https://i.sstatic.net/lvE1X.png)](https://i.sstatic.net/lvE1X.png)

In this case $p$ is a point on some arbitrary face in a mesh, $p'$ is a point on one of the 3 edges in the triangle and $D(p')$ is the geodesic distance to that point.

I am very confused as to how this minimization is achieved. The paper doesn't go into detail, so I assume it's trivial, but I am not seeing the solution of the top of my head.

Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point $p$ onto the segment or one of the end points of the segment (depending on where $p$ is located with respect to the segment).

However, this is not necessarily the point that minimizes the expression $||p - p'|| + D(p')$ or in other words, $p'$ is not, in general, the orthogonal projection of $p$ onto the segment.

The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.

I have drawn a diagram on Geogebra to show the problem:

[![enter image description here](https://i.sstatic.net/FmfBf.png)](https://i.sstatic.net/FmfBf.png)

$\overline{BA}$ is the segment, $C$ is the point we are looking to minimize the distance from. $D$ is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), $E$ is the orthogonal projection of $C$ onto $\overline{BA}$. Clearly the optimal point is somewhere between $E$ and $D$ but I don't know how to find it.

**Tags:** mathematics, computational-geometry, mesh, geometry

> **Comments:**
> **username_1**: Doesn't 4.3 and onwards deal with this? It's probably also a good idea to consider: https://code.google.com/archive/p/geodesic/wikis/ExactGeodesic.wiki  
> **username_0**: Unfortunately section 4, section 4,3 included deals with their approximating method, however I need to use the exact geodesic, not the approximation. Those notes are indeed interesting, but they don't seem to address the problem I am currently facing, at minimum not explicitly. I have a hypothesis as to what the proper way to do this is, I am testing it right now, if successful I will answer my own question.  

---

## 1 answers

### Answer by username_0 on 2020-07-06. Score: 0 | Accepted answer

The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source $v$ from a point $p$ is $||v-p'|| + ||p - p'||$ where $p'$ is the intersection of the line $\overline{vp}$ with the current edge. In cases where $p'$ is "behind" $p$ with respect to $v$ we set the distance to the edge to be infinity.

The above seems to work in the simple tests I have generated at minimum.


---

