Mfcttrf

I need a mathematical algorithm for finding the angle, formed by three points, which is open toward a fourth point.

For example, in Fig1 below I desire angle $theta$ because it is "facing" point $P$. However, the formula for the angle between two vectors, $$theta=cos^-1Big(fracvecucdotvecvuvBig)$$ gives angle $alpha$ because the above relation always returns the angle which is less than 180 degrees.

(Fig1)

In contrast, in Fig2 I desire angle $alpha$ because this time it is "facing" point $P$.

(Fig2)

As a final example, in Fig3 below I need angle $theta$, because it is still technically "facing" point $P$.

(Fig3)

This problem can occur in any orientation, making it difficult to say, for example, "If point $P$ is to the left of points $A, B, C$, use the leftmost angle, otherwise use the right" or something like that.

Any help would be appreciated!

My Attempted Solution

If anyone's interested, my current solution is to split the angle facing the point $P$ in half and add those two together.

In Fig4 below, I use the grey line to split the angle in half, find $s$ and $t$ using dot product, then add $s$ and $t$ to get the angle facing $P$.

(Fig4)

This works until I reach a situation like that in Fig5. What I need is $s+t$, but what I get is $q+t$ because the dot product gives $q$ (since $s$ is greater than $180$ degrees).

(Fig5)

It's a conundrum.

Except if $A,B,C$ are collinear, for any $P$ on the non-reflex side of $angle ABC$, the unique solution $(t,u)$ to $vecBP=tvecBA+uvecBC$ will have $t,uge0$. This leads to the following algorithm:

1. Translate all the points so $B$ is at the origin.




2. In these new coordinates, solve the linear system
   $$beginbmatrixx_A&x_C\y_A&y_Cendbmatrixbeginbmatrixt\uendbmatrix=beginbmatrixx_P\y_Pendbmatrix$$




3. If both $t$ and $u$ are non-negative, take the non-reflex angle $alpha$ resulting from the application of the standard formula for angle between two vectors. Otherwise, take the complementary reflex angle $theta$.




4. If $A,B,C$ are collinear, the linear system in step 2 will be indeterminate, and it is easy to check whether $angle ABC=0$ (in which case $2pi$ is returned) or $pi$ (in which case $pi$ is returned).

Unless $A-B$ and $C-B$ are linearly dependent, you can uniquely express $P-B$ in terms of them:
$$ P-B=rcdot(A-B)+scdot(C-B).$$
Now $P$ is in the smaller of the two possible angles if and only if $r$ and $s$ are both positive. It is on the ray $BA$ if and only if $s=0$ and $rge0$, and on the ray $BC$ if and only if $r=0$ and $sge 0$. In all other cases, it is in the larger angle.

You can sort this out by comparing the signs of three determinants. Let $$d_0 = detbeginbmatrixB_x&B_y&1\A_x&A_y&1\C_x&C_y&1endbmatrix.$$ This tells you the direction in which the vertices of $triangleBAC$ are traversed: positive means counterclockwise, negative clockwise, and the points are colinear if it’s zero. Note that the area of this triangle is equal to $frac12lvert d_0rvert = frac12lVert A-BrVert,lVert C-BrVert,lvertsinphirvert$, with $lvertphirvertin[0,pi)$, so when the points aren’t colinear this is another way to find the angle between them. Moreover, unlike the dot product, this determinant can tell left from right. On the other hand, it can’t tell the order of the points when they’re colinear, which the dot product can.

Now, assuming that $d_0ne0$, compare the signs of the corresponding determinants for $triangleAPB$ and $triangleBPC$ $$d_A=detbeginbmatrixA_x&A_y&1\P_x&P_y&1\B_x&B_y&1endbmatrix text and d_C=detbeginbmatrixB_x&B_y&1\P_x&P_y&1\C_x&C_y&1endbmatrix,$$ respectively, to the sign of $d_0$: If they are all the same, then $P$ lies within the “narrow” side and you can use the angle $theta$ computed in your question; if any differ, then $P$ is on the “wide” side and you want $2pi-theta$. If either $d_A$ or $d_C$ is zero, ignore it; if both are zero, then $P=B$ and you might as well use $theta$.

If you expand these determinants, you might find that the resulting expressions look familiar. For example, $d_0 = (A-B)wedge(C-B)$, where $mathbf vwedgemathbf w=v_x w_y-v_y w_x$ is the “two-dimensional cross product” of the vectors.