8
$\begingroup$

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^{-1}\Big(\frac{\vec{u}\cdot\vec{v}}{uv}\Big)$$ gives angle $\alpha$ because the above relation always returns the angle which is less than 180 degrees.

Figure 1(Fig1)

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

Figure 2(Fig2)

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

Figure 3(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$.

Figure 4(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).

Figure 5(Fig5)

It's a conundrum.

$\endgroup$
  • 1
    $\begingroup$ Here’s the MathJax tutorial $\endgroup$ – gen-z ready to perish Jun 29 at 17:37
  • $\begingroup$ What would you like the results to be if you were to swap points $A$ and $C$ in all of these cases? There’s a fairly simple solution that involves comparing the signs of two $3\times3$ determinants, but interpreting them correctly depends on the answer to my question. $\endgroup$ – amd Jun 29 at 18:30
  • $\begingroup$ @amd In my implementation, I have a long string of consecutively drawn points (by a user dragging a mouse) and I look at every set of 3 points in the user-drawn-line and label them a, b, and c. a and c can be swapped, namewise, if that is what you mean. But for the sake of your answer, let's say that they can be swapped in the way you suggest. What follows from there? $\endgroup$ – retrovius Jun 29 at 18:40
  • $\begingroup$ Let me ask my question a different way: is $\alpha$ always measured counterclockwise from $\overrightarrow{BA}$ to $\overrightarrow{BC}$, in which case it might be greater than $\pi$, or is it simply the angle measure in the range $[0,\pi]$ between the two rays without regard to which ray is “first?” I.e., is $\alpha$ always the lesser of the two angles? $\endgroup$ – amd Jun 29 at 18:44
  • $\begingroup$ I see. My situation fits the second option, calculating the angle in the range [0,Pi] without regard to which ray is "first", corresponding to equation F in my question. $\endgroup$ – retrovius Jun 29 at 18:49
3
$\begingroup$

Except if $A,B,C$ are collinear, for any $P$ on the non-reflex side of $\angle ABC$, the unique solution $(t,u)$ to $\vec{BP}=t\vec{BA}+u\vec{BC}$ will have $t,u\ge0$. 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 $$\begin{bmatrix}x_A&x_C\\y_A&y_C\end{bmatrix}\begin{bmatrix}t\\u\end{bmatrix}=\begin{bmatrix}x_P\\y_P\end{bmatrix}$$

  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 $2\pi$ is returned) or $\pi$ (in which case $\pi$ is returned).

$\endgroup$
  • $\begingroup$ This accomplished exactly what I needed in a simple, intuitive, straightforward fashion. I knew there was something out there, I just didn't know how to ask the question. Thank you! $\endgroup$ – retrovius Jun 29 at 19:44
  • $\begingroup$ Will any problems arise when all four points are colinear? $\endgroup$ – retrovius Jun 29 at 20:04
  • 1
    $\begingroup$ @retrovius Handled by case 4. $\endgroup$ – Parcly Taxel Jun 30 at 5:30
4
$\begingroup$

Unless $A-B$ and $C-B$ are linearly dependent, you can uniquely express $P-B$ in terms of them: $$ P-B=r\cdot(A-B)+s\cdot(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 $r\ge0$, and on the ray $BC$ if and only if $r=0$ and $s\ge 0$. In all other cases, it is in the larger angle.

$\endgroup$
2
$\begingroup$

You can sort this out by comparing the signs of three determinants. Let $$d_0 = \det\begin{bmatrix}B_x&B_y&1\\A_x&A_y&1\\C_x&C_y&1\end{bmatrix}.$$ This tells you the direction in which the vertices of $\triangle{BAC}$ 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 $\frac12\lvert d_0\rvert = \frac12\lVert A-B\rVert\,\lVert C-B\rVert\,\lvert\sin\phi\rvert$, with $\lvert\phi\rvert\in[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_0\ne0$, compare the signs of the corresponding determinants for $\triangle{APB}$ and $\triangle{BPC}$ $$d_A=\det\begin{bmatrix}A_x&A_y&1\\P_x&P_y&1\\B_x&B_y&1\end{bmatrix} \text{ and } d_C=\det\begin{bmatrix}B_x&B_y&1\\P_x&P_y&1\\C_x&C_y&1\end{bmatrix},$$ 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 $2\pi-\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 v\wedge\mathbf w=v_x w_y-v_y w_x$ is the “two-dimensional cross product” of the vectors.

$\endgroup$
  • $\begingroup$ This is also a viable solution! It's very intuitive and clever! I implemented @Parcly_Taxel's answer because it was a little bit simpler to translate into C# code, and requires fewer computational steps, but thank you for your answer! $\endgroup$ – retrovius Jun 29 at 19:43
  • $\begingroup$ @retrovius The determinant (equiv. cross product) approach can be more numerically stable when the angle between the two vectors is small or they’re very short. In solving the linear system, you end up dividing by a small number, which can be problematic. $\endgroup$ – amd Jun 29 at 19:50

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.