Following on from my previous post...

I'm going through this PDF file describing barycentric coordinates and trying to make sure I understand everything fully as I need to implement and support these in a computer program.

One page 3, area $A$ is defined as follows:

$$A = \begin{vmatrix}\bf{P_1}&\bf{P_2}&\bf{P_3}\\1&1&1\end{vmatrix}$$

and the notes say "Area $A$ is simply the triangle's area". Question 1: It's not though is it? It's twice the area (well, the signed area). Sorry if I'm asking a picky or silly question, but when I'm trying to understand things, even very minor things that confuse me throw me heavily off course!

Page 5 talks about finding the barycentric coordinates of a triangle defined by 3D coordinates which is exactly what I want to do. It says "We simply use this same method to form the sub-areas $A_1$, $A_2$, $A_3$ in (3)". Question 2: Now we have z coordinates, don't we have 4 equations in 3 unknowns? (or as $w = 1 - u - v$, 3 equations in 2 unknowns) which I believe is called an overdetermined system and something my brain doesn't know what do to with! I've only ever done inverses of square matrices. Hopefully someone can throw me a lifeline on this.

$$\begin{bmatrix}p^1_x - p^3_x & p^2_x - p^3_x \\ p^1_y - p^3_y & p^2_y - p^3_y\\ p^1_z - p^3_z & p^2_z - p^3_z\end{bmatrix}\begin{bmatrix}u\\v\end{bmatrix} = \begin{bmatrix}p_x - p^3_x\\p_y - p^3_y\\p_z - p^3_z\end{bmatrix}$$

  • $\begingroup$ Yes, it's twice the signed area. $\endgroup$ – Qiaochu Yuan Nov 23 '11 at 17:09
  • $\begingroup$ "...I believe is called an overdetermined system and something my brain doesn't know what do to with! I've only ever done inverses of square matrices." - that's where "least squares" might be applied... $\endgroup$ – J. M. is a poor mathematician Nov 23 '11 at 17:39
  • $\begingroup$ @J.M. Ahh... I watched an MIT video recently about least squares where they were fitting a line to some data points. I didn't make the connection about it being used for an overdetermined system of equations. Thank you. $\endgroup$ – PeteUK Nov 23 '11 at 20:47
  1. Yes, it's twice the signed area.

  2. You're right, it's overdetermined. This makes sense: barycentric coordinates can only be meaningfully assigned to points coplanar to the triangle. This linear system may not have an exact solution -- but you can look for the best possible solution $x$ in the sense of minimizing the error (this is called finding the least-squares solution, since you are minimizing the sum of the squares of the components of the residual): $$\min_x \frac{1}{2} \|Ax - b\|^2.$$ This objective function has a geometric interpretation in the case of your problem: $Ax-b$ is the vector between your original point, and the point in the plane of the triangle given by the barycentric coordinates you're searching for. So if your original point is not coplanar with the triangle, solving this optimization problem will find the barycentric coordinates of the point on the plane that's "under" your original point along the normal direction -- clearly the best that you can do.

To solve for the minimizing $x$, we take the derivative and set it equal to zero: $$A^T Ax - A^Tb = 0.$$ You can now readily solve this system, since $A^TA$ is a 2 x 2 symmetric positive-(semi)definite matrix, with $A^T b$ guaranteed to be in its column space.

  • $\begingroup$ The point I have is definitely coplanar with the triangle. Is there a shortcut in this case? I will work through this and respond/mark as answer when time permits. Thank you. $\endgroup$ – PeteUK Nov 23 '11 at 21:00
  • 1
    $\begingroup$ I don't think there's a shortcut that's significantly easier than solving a $2x2$ linear system. $\endgroup$ – user7530 Nov 23 '11 at 21:15
  • $\begingroup$ Marked as answer. Not worked through/implemented it yet as did calculations in 2D for now. Least squares seems to be definitely what I need though! Thanks. $\endgroup$ – PeteUK Nov 26 '11 at 16:17
  • $\begingroup$ I finally got round to implementing the least squares in my code for the 3D triangle case, and it works a treat! Took me a while to learn the theory regarding $x = (A^TA)^{-1}A^Tb$, but I'm glad I did. Thanks again. $\endgroup$ – PeteUK May 1 '13 at 13:26

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.