1
$\begingroup$

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.

  • 0
    Exactly. What is the fastest way mathematically to determine whether this is the case? I'm currently working out three angles and determining whether the test angle is within the other two but hoping that there's a way to do this in less steps than I'm currently using. As in, determining three angles.2012-07-12

4 Answers 4

3

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$.

  • 0
    @Rahul: Thank you so much!2015-11-22
1

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.

  • 0
    Finding λ1 and λ2 simply reduces to solving the 2x2 system of linear equation C=λ1A+λ2B. In this simple case, the solution can be written out explicitly: $\lambda_1=\frac{c_1b_2−b_1c_2}{a_1b_2−b_1a_2},\lambda_2=\frac{a_1c_2−c_1a_2}{a_1b_2−b_1a_2}$. This always works when A and B are linearly independent. The signs of λ1 and λ2 then uniquely define the location of C: both positive means in the interior of the cone, if one is zero it lays on one of the lines. There are $9$ different cases corresponding to the different combinations of signs. A sketch really helps to clarify this.2012-07-13
0

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.

  • 0
    @Steve: Then I don't have any better. The point is that you suggest there will be some points not in the angle, but there are four different angles and the point will be in one of them (unless it is on one of the lines).2012-07-12
0

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} and $D_{AB}, 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.

  • 0
    @Steve I've updated with more explicit information. Hopefully this helps. Something with the calculation is definitely wrong, the video seems to be testing if $mouse \cdot point0$ is negative, or something along those lines, since it's only true in the left half of the screen.2012-07-14