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.

$\endgroup$
2
  • 1
    $\begingroup$ Your "fourth point" would be contained on either the acute angle or the obtuse angle determined by your lines... $\endgroup$
    – J. M. ain't a mathematician
    Jul 12, 2012 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Jul 12, 2012 at 17:09

4 Answers 4

Reset to default
3
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Beautifully simple! And easy to program too. $\endgroup$
    – TonyK
    Nov 22, 2012 at 13:11
  • $\begingroup$ would it be too much to ask if you could provide resources that could explain what's going on here? like what kind of math is being used, what are all the fancy symbols and what do they mean, etc $\endgroup$
    – Josie Thompson
    Nov 20, 2015 at 12:50
  • 1
    $\begingroup$ @Josie: It's mostly linear algebra. I've defined a new function called $\wedge$ which takes two vectors $u$ and $v$ and returns the number $u_xv_y-u_yv_x$. If it's confusing, you could mentally replace all instances of $u\wedge v$ with $f(u,v)$, which might be more familiar notation. Does that help? If not, let me know which part needs clarification. $\endgroup$
    – user856
    Nov 20, 2015 at 14:30
  • $\begingroup$ I think that kind of cleared it up. I was doing a bit of research and I thought that the carrot symbol was denoting a wedge product. When You're multiplying u - sub x by v sub y, are you multiplying the different parts of their vectors? (btw I'm not sure how to do mini-markup for math so please excuse the way I wrote that) $\endgroup$
    – Josie Thompson
    Nov 20, 2015 at 23:17
  • $\begingroup$ @Josie: Yes, I'm assuming $u = (u_x, u_y)$, so $u_x$ and $u_y$ are the $x$- and $y$-components of the vector $u$. And similarly for $v = (v_x, v_y)$. Incidentally, the function $u\wedge v$ is essentially the same as the wedge product, which is why I chose that symbol. $\endgroup$
    – user856
    Nov 21, 2015 at 4:11
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Steve
    Jul 13, 2012 at 21:41
  • $\begingroup$ 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. $\endgroup$
    – erlking
    Jul 13, 2012 at 22:50
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Jul 12, 2012 at 16:52
  • $\begingroup$ @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). $\endgroup$
    – Ross Millikan
    Jul 12, 2012 at 16:54
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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 =) $\endgroup$
    – Steve
    Jul 12, 2012 at 21:44
  • $\begingroup$ 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. $\endgroup$
    – Robert Mastragostino
    Jul 12, 2012 at 22:21
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Jul 13, 2012 at 21:35
  • $\begingroup$ Do you know roughly what the range is where it fails? That seems kind of bizarre. $\endgroup$
    – Robert Mastragostino
    Jul 13, 2012 at 22:00
  • $\begingroup$ 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 -_-;; $\endgroup$
    – Steve
    Jul 14, 2012 at 8:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .