Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Your "fourth point" would be contained on either the acute angle or the obtuse angle determined by your lines... –  J. M. Jul 12 '12 at 16:34
    
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. –  Steve Jul 12 '12 at 17:09
add comment

4 Answers 4

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.

share|improve this answer
    
I forgot to mention that I'm using this for a computer program. This is the process I'm currently using to determine whether the fourth point is in the wedge that the previous two points create. I'm trying to figure out if there's a faster way to get to the result than to get the angles of three lines using two points a piece and also compensating for the addition of 2pi. –  Steve Jul 12 '12 at 16:52
    
@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). –  Ross Millikan Jul 12 '12 at 16:54
add comment

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.

share|improve this answer
    
You understand my question perfectly, but I'm having difficulty understanding your solution. Do I need to reduce the vectors A, B and C to one unit in your equation? If not, this would run much better in my program than other solutions. Even if they do need to be reduced, I'd like to understand your method to compare it to the other ones I'm currently using for processing speed. Having A, B and C, I'm unsure how I am to figure out what λ1 and λ2 are. Also, can your method be used to determine whether C resides on the ray spanned by A or B as well as determining if it resides within the cone?ty –  Steve Jul 13 '12 at 21:41
    
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. –  erlking Jul 13 '12 at 22:50
add comment

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.

share|improve this answer
    
I follow up until the multiplication and greater than. I'll try to explain what I get and hopefully you'll be able to clarify what I don't. I subtract points A, B and C individually by point O so that they are all shifted to be in the same position they would be in if the angle's point were at (0,0). After that is where I'm confused. How do I determine whether one point is greater than another? And in what way should I be multiplying the existing points? I think you understand what I'm asking and this definitely seems like it'll process faster than what I'm currently using =) –  Steve Jul 12 '12 at 21:44
    
The middle step of "divide all points by their new length, so that they're $1$ distance away from the vertex" is important. The type of multiplication is the dot product. If the points all have a distance $1$, then the dot product is just $\cos\theta$, where $\theta$ is the angle between them. $\cos$ is bigger when the angles are smaller, so the dot product (cosine really) is bigger, the angles are smaller, so you're on the inside. –  Robert Mastragostino Jul 12 '12 at 22:21
    
I implemented this and for the most part, it works nicely but I keep running into a strange problem where this also proves to be true for a range that is outside of the cone formed by points O, A and B. For A=(0.9913462,-0.1312741), B=(0.4740998,0.8804711) and C=(-0.5978239,-0.8016275). C should be outside of the cone formed by O, A and B but when plugged in, it is less than both AdotC and BdotC. Is there a reason for this and is it something that I can fix? –  Steve Jul 13 '12 at 21:35
    
Do you know roughly what the range is where it fails? That seems kind of bizarre. –  Robert Mastragostino Jul 13 '12 at 22:00
    
youtu.be/e9h16q-n8Mk I went ahead and put together a video that should illustrate where it seems to go wrong. I've also tried two other formulas that I received here stackoverflow.com/questions/11456671/… If you could take a look and maybe help me figure out what's going wrong, that'd be immensely. . . well, helpful =) Please let me know if you have any questions about what's going on -_-;; –  Steve Jul 14 '12 at 8:50
show 1 more comment

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

share|improve this answer
    
Beautifully simple! And easy to program too. –  TonyK Nov 22 '12 at 13:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.