Figure out if a fourth point resides within an angle created by three other points

Question

If I have a point that is considered the origin and two lines that extend outwards infinitely to two other points, what is the best way to determine whether or not a fourth point resides on or within the angle created by those points?

The process I'm currently using is to get the angle of all three lines that extend out from the origin and then check to see whether the third angle is within the range of the first two.

Grid space is defined as Screen Space, that is, 2D Cartesian with the Y-Axis flipped so "up" is negative y and the origin is the upper left corner.

Answer 1

The two lines divide the plane into four wedges. The fourth point will be in one of these four wedges. To find which one, you can use the Atan2 function to find the angle of each line and the angle of the fourth point from the origin. You can look to see which ones it is between. You must remember that one of the wedges will cross $\theta=0$ and need to add $2\pi$ as required when checking.

Answer 2

If I understand you correctly you want to know whether the fourth point lies in the cone generated by the three other points with the origin as its apex. In that case, you can do this: Let $O,A,B$ denote the given vectors where $O$ is the origin and $C$ the fourth one. Unless $A$ and $B$ are linearly dependent you can uniquely write $C$ as a linear combination $C=\lambda_1 A + \lambda_2 B$. Now, if both $\lambda_1$ and $\lambda_2$ are positive $C$ lies within the cone spanned by $A$ and $B$. The other cases for values of $\lambda_1$ and $\lambda_2$ will give similar results such that $C$ lies on one of the rays spanned by $A$ or $B$ or will lie in the interior of the complement of the cone.

Answer 3

Shift your coordinates so that the point of the angle is the origin. Normalize the other points (so we're replacing all other points by ones that are a unit distance from the "origin". Say the cone is made by $O,A,B$ (in the new coordinates) and the point to find is $C$. If $A\cdot C$ and $B\cdot C$ are greater than $A\cdot B$, then it's between them.

EDIT: formula, with $O,A,B,C$ as the original, non-shifted points: $$D_{AB}=\frac{(A_x-O_x)(B_x-O_x)+(A_y-O_y)(B_y-O_y)}{\sqrt{(A_x-O_x)^2+(A_y-O_y)^2}\sqrt{(B_x-O_x)^2+(B_y-O_y)^2}}$$

If $D_{AB}<D_{AC}$ and $D_{AB}<D_{BC}$, then $C$ is in the angle. Otherwise, it's outside. The matrix method given on the stackoverflow page is also good, and may be easier. In this, $A,B,C$ have already been shifted.

$$C_x=\alpha A_x+\beta B_x$$ $$C_y=\alpha A_y+\beta B_y$$

if $\alpha$ and $\beta$ are both positive, then it's in the interior.

$$\alpha=\frac{C_yB_x-C_xB_y}{A_yB_x-A_xB_y}$$ $$\beta=\frac{C_yA_x-C_xA_y}{B_yA_x-B_xA_y}$$

My only suggestion is that the algorithm hasn't been implemented properly, possibly because of some subtle language/code issue. I'd advise you to post your written code on the stackoverflow question, it's harder to help without it.

Answer 4

No need to solve systems of linear equations, call trigonometric functions, or even normalize the vectors. Let $a$, $b$, and $c$ be the vectors $\overrightarrow{OA}$, $\overrightarrow{OB}$, and $\overrightarrow{OC}$, and denote $$u \wedge v = \begin{vmatrix}u_x & v_x \\ u_y & v_y\end{vmatrix} = u_x v_y - u_y v_x$$ for any two vectors $u$ and $v$. The sign of $u \wedge v$ tells you which side of the line parallel to $u$ the vector $v$ lies on, and vice versa. Then $C$ lies in the wedge between the rays $OA$ and $OB$ if and only if $a \wedge c$ and $c \wedge b$ have the same sign as $a \wedge b$.