Calculating the barycentric coordinates for a point based on edge lengths alone

Question

I am trying to calculate the barycentric weights of a triangle from which I have no Cartesian coordinates- only a set of edge lengths describing the configuration of a flattened tetrahedron with points A, B, and C, as well as an extra (usually) internal point P (but, again- I don't actually know where these points are, all I have area the edge lengths between them- so AB, BC, CA, PA, PB, and PC).

Thus far this is pretty easy to do simply by calculating the area of the main triangle (ABC) and the area of each of the three sub-triangles (PAB, PBC, and PCA). The barycentric weights of the unknown point P are therefore:

u = A_PAB / A_ABC
v = A_PBC / A_ABC
w = A_PCA / A_ABC

This works fine for any point located inside the triangle, but predictably fails for any point outside of the triangle. This is occurring because the area calculations do not take into consideration the orientation of the triangle (which I don't technically know), so I have no way of determining a winding order- the moment one of the sub-triangles becomes external to the main triangle, things go south since I'm missing the negative sign of one or more barycentric coordinates.

Is there any easy way to calculate the signs of the barycentric coordinates for coordinates that may need to represent a point located outside of the triangle?

Once again, I don't know the x, y coordinates of the triangle points- just the edge lengths of everything. I figured there must be a way to detect the signs of the coordinates somehow, though I've yet to figure out a reliable way of doing this.

Answer 1

After mulling this over for a bit, it seems like the most straightforward manner to solve this is based on a comment left by achille hui- namely in that the sum of all non-normalized barycentric regions must equal the original triangle area (or 1.0 if they've already been normalized).

This gives a fairly simple equation in the form of:

area_abc = area_pab * s1 + area_pbc * s2 + area_pca * s3

Where the goal is to simply solve for the signs (either +1 or -1) of s1, s2, and s3 respectively.

In my particular case, this results in a whopping 7 combinations of signs to try:

+1, +1, +1
-1, +1, +1
+1, -1, +1
+1, +1, -1
-1, -1, +1
+1, -1, -1
-1, +1, -1

(-1, -1, -1) is obviously impossible since there can be no situations where all three barycentric regions would require flipped signs, so that can be skipped. The remaining possibilities simply represent the signs of the 6 regions on the exterior of the triangle (technically the regions formed by the overlap of the lines that make up each of the triangle sides).

Due to various floating point issues (as this is a problem I'm ultimately trying to solve in code), I landed up going with a simple algorithm that simply tries each combination of signs and keeps track of the one with the closest distance to zero in the form of abs(area_abc - (area_pab * s1 + area_pbc * s2 + area_pca * s3)), which is basically guaranteed to always return the correct configuration of signs.

I landed up doing this over checking against an epsilon value and returning the first potential hit because floating point precision issues can jog that out of alignment (especially if you're using Heron's Formula or something similar to calculate the original triangle areas based on their side lengths). Searching for the closest match instead eliminates this issue and will work 100% of the time.

I tried a few other approaches, but frankly... all of them were just as complicated or more complicated than doing a simple brute-force search of all possible sign combinations. It doesn't really feel as elegant as it could be, but it works, and it's fast- so that's what I landed up going with.

Answer 2

Let

$$\begin{cases}a=BC,b=CA,c=AB\\u=PA,v=PB,w=PC\end{cases}.$$

First of all, I imagine that your distances are compatible, but a "sanity check" is never bad. How to do it ? By verifying that their Cayley-Menger determinant is zero :

$$\begin{vmatrix} 0 & 1 & 1 & 1 &1 \\ 1 & 0 & c^2 & b^2 & u^2 \\ 1 & c^2 & 0 & a^2 & v^2 \\ 1 & b^2 & a^2 & 0 &w^2 \\ 1 & u^2 & v^2 & w^2& 0 \end{vmatrix}=0$$

I think that a reasonable line of action is as follows.

• "Install" triangle $ABC$ in a system of coordinates where for example, up to a renaming $a=AB$ is the longest side, with $A(0,0)$, $B(0,a)$ ;

• Compute coordinates $C(x_C,y_C)$ (based on distances $a$ and $b$) in such a way that $y_C > 0$ (please note that necessarily $0 \le x_C \le c$) ; this warrants in particular a positive orientation of triangle $ABC$.

• Find the two intersection points $I(x,y)$ of circles $C(A,u)$ (centered in $A$ with radius $AP=u$) and $C(B,v)$. Which means that

$$\begin{cases}x^2+y^2&=&u^2& \ \ (a)\\(x-c)^2+y^2&=&v^2& \ \ (b)\end{cases},\tag{1}$$

Expanding (b) and computing the difference (a)-(b), we get :

$$x=\underbrace{\frac{1}{2c}(c^2+u^2-v^2)}_{x_P}$$

Plugging this value of $x$ in $(1)(a)$ gives two potential points $P_1,P_2$ with common abscissa $x_P$ and resp. ordinates :

$$y_P=\pm \sqrt{u^2-x_P^2}$$

• Compute the two distances $P_1C$ and $P_2C$ : one of them only (in general) will match value $w$. In this way, you have found the right point $P$.

• Finally, convert the cartesian coordinates of $P$ into barycentric coordinates $(p,q,r)$ by solving the system:

$$\begin{cases}px_A&+&qx_B&+&rx_C&=&x_P\\ py_A&+&qy_B&+&ry_C&=&y_P\\ p&+&q&+&r&=&1\end{cases} \iff \begin{cases}&&qc&+&rx_C&=&x_P\\ &&&&ry_C&=&y_P\\ p&+&q&+&r&=&1\end{cases}$$

giving immediately :

$$\begin{cases}r&=&\frac{y_P}{y_C}\\ q&=&\frac{1}{cy_C}(x_Py_C-y_Px_C)\\ p&=&1-q-r\end{cases}$$

Remark: Direct computation of barycentric coordinates (by using Heron's formula), is possible, but it is more complicated due to signs management...