Find closest point in triangle given barycentric coordinates outside

3.6k Views Asked by At

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?

2

There are 2 best solutions below

5
On BEST ANSWER

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.

0
On

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}