3

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?

Community
  • 1
Daerst
  • 143

2 Answers2

3

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.

hjhjhj57
  • 4,125
  • 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? – Daerst Jan 06 '15 at 14:39
  • @Daerst yes. ${}{}{}$ – hjhjhj57 Jan 06 '15 at 19:14
  • Thanks, I marked your answer as accepted. Unfortunately, I can't upvote because of my low reputation. I'll be back! – Daerst Jan 07 '15 at 13:32
  • 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. – Paul Du Bois Nov 10 '15 at 23:04
  • @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. – Tom Makin Oct 11 '16 at 14:06
1

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}

Paul
  • 121