4
$\begingroup$

Given a point $P$ and three triangle vertices $U$, $V$, $W$, all in $\mathbb{R}^3$, I need to find the point in the triangle $UVW$closest to $P$. Does the following algorithm work, or have I missed any case?

  1. Project $P$ onto the plane spanned by $UVW$. If the projected point lies inside the triangle, this is the closest point. Otherwise:

  2. Project $P$ onto the three lines $UV$, $VW$, $WU$. If any of the projections lies on the edge, add these points to a list of candidates.

  3. Add the three vertices to the list of candidates. Now we have 3-6 solution candidates, and one of these must be the closest point on the triangle.

Have I missed anything? For instance, could the solution lie on the edge of the triangle even if that edge was discarded in step 2? I couldn't find a counter-example, but I don't trust my skills that much.

$\endgroup$
1
$\begingroup$

That algorithm is fine. But it's easier, once you've projected to a point $Q$ in the plane, to search in the plane. If $Q$ is interior to the triangle, you're done, as you observed.

Now you can test, for each edge, say $UV$, whether the projection $Q$ and the remaining point $W$ are on opposite sides of the line $UV$. If so, $W$ is not the closest point, and you can find the closest point by projecting onto $UV$: if the projection lies between $U$ and $V$, it's the closest point; if not, then one of $U$ or $V$ is.

Thomas Akenine-Moller has done a LOT of work on this kind of thing, and has many very clever algorithms for doing it with the smallest possible number of computations. To be more precise, he's studied ray-triangle interserction algorithms, but many of the ideas there apply here as well. Sample paper: Tomas Möller and Ben Trumbore. Fast, minimum storage ray-triangle intersection. J. Graph. Tools, 2(1):21–28, October 1997.

As for "have I missed anything", one way to think of it is that you start at the point $Q$ and draw ever-expanding disks until one touches the triangle. When you view it that way, it's pretty clear that the choices you described are exhaustive.

(Apologies for my earlier answer: I was just being too glib, and should have paused and thought for just a moment longer...)

$\endgroup$
  • $\begingroup$ What about this case in your algorithm? $C$ is farthest away and discarded, but the closest point lies on the edge $AC$. $\endgroup$ – Anna Jan 5 '15 at 15:53
  • $\begingroup$ This does not work. Consider $Q=(0,1)$, $A=(100,0)$, $B=(-10,0)$, $C=(0,-1)$. You would throw out $A$ and project $Q$ to $BC$, wheres the true closest point is $(0,0)$. $\endgroup$ – Hagen von Eitzen Jan 5 '15 at 15:54
  • $\begingroup$ Edited to fix this; thanks for pointing it out. $\endgroup$ – John Hughes Jan 5 '15 at 16:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.