3
$\begingroup$

Given a non-degenerate triangle ABC and an arbitrary point P in 3D space, I can project P onto the plane defined by ABC and check whether the triangle contains it as described here. I end up with barycentric coordinates of the point.

In case the point does not lie inside the triangle, i.e. any of alpha, beta or gamma are not in range [0..1], I now want to find the point inside the triangle which is closest to the projection of P onto the plane defined by ABC. How would I do that?

$\endgroup$
3
$\begingroup$

You know that $$ \begin{align} P = \alpha A + \beta B + \gamma C &= \beta(B-A) + \gamma(C-A) + A\\ &= \alpha (A-B) + \gamma(C-B) + B \\ &= \alpha (A-C) + \beta(B-C) + C. \end{align} $$ We can classify the outside of the triangle in six regions:

1) $0\leq\beta$, $0\leq\gamma$, and $1\leq\beta+\gamma$, in which case the point is closest to $BC$. (In which case would it be closest to the $B$ or $C$?)

2) $0\leq\alpha$, $0\leq\gamma$, and $1\leq\alpha+\gamma$, in which case the point is closest to $AC$.

3) $0\leq\alpha$, $0\leq\beta$, and $1\leq\alpha+\beta$, in which case the point is closest to $AB$.

I'll let you work the other three cases which involve mixed signs, for example $1<\gamma$, $\beta<0$, for which the vertex $C$ is the closest point.

$\endgroup$
  • $\begingroup$ Thanks for your answer. If the three checks above failed, and still one coefficient alpha/beta/gamma is greater than 1, P is closest to A/B/C respectively. Is this correct? $\endgroup$ – Daerst Jan 6 '15 at 14:39
  • $\begingroup$ @Daerst yes. ${}{}{}$ $\endgroup$ – hjhjhj57 Jan 6 '15 at 19:14
  • $\begingroup$ Thanks, I marked your answer as accepted. Unfortunately, I can't upvote because of my low reputation. I'll be back! $\endgroup$ – Daerst Jan 7 '15 at 13:32
  • $\begingroup$ This does not work. The lines separating the 6 regions outside the triangle are each parallel to a triangle edge. However, the region closest to an edge is bounded by the edge and two perpendiculars emanating from the adjacent vertices. A nondegenerate triangle cannot have parallel edges, qed. As a concrete example, A=(0,0), B=(-1, epsilon), C=(1,epsilon). (Almost) every point with y > epsilon will be "closest to BC", yet there are many points which are closer to one of the vertices B or C. $\endgroup$ – Paul Du Bois Nov 10 '15 at 23:04
  • $\begingroup$ @PaulDuBois I think your comment is correct, but it seems the proposed method is fine as long as you use a finite segment when finding the closest point on BC. $\endgroup$ – Tom Makin Oct 11 '16 at 14:06
1
$\begingroup$

As @PaulDuBois commented, the above answer (@hjhjhj57) is incorrect for obtuse angles.

In fact, we can classify the outside of the triangle in three regions:

1) $\alpha\geq 0$ and $\beta<0$, in which case $P$ is closest to either $AB$ or $AC$,

2) $\beta\geq 0$ and $\gamma<0$, in which case $P$ is closest to either $AB$ or $BC$,

3) $\gamma\geq 0$ and $\alpha<0$, in which case $P$ is closest to either $AC$ or $BC$.

The three regions are equivalent under substitution of variables and I will work out case 1:

If $\gamma<0$, and $(P-A)(B-A)>0$, $i.e.$ the projection of $P$ onto $AB$ where vector multiplication is the dot product, then $P$ is closest to $AB$ (verify that this can only be the case if $A$ is obtuse). Then \begin{eqnarray} \beta' &=& \text{min}(1, \frac{(P-A)(B-A)}{(B-A)(B-A)} ) \\ \gamma' &=& 0 \end{eqnarray}

Otherwise $P$ is closest to $AC$ with \begin{eqnarray} \beta' &=& 0 \\ \gamma' &=& \text{min}(1, \text{max}(0, \frac{(P-A)(C-A)}{(C-A)(C-A)} ) ) \end{eqnarray}

And lastly \begin{eqnarray} \alpha' &=& 1 - \beta' - \gamma' \\ P' &=& \alpha'A + \beta'B + \gamma'C \end{eqnarray}

$\endgroup$

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.