1

If I have three points that create an angle, what would be the best way to determine if a fourth point resides within the angle created by the previous three?

Currently, I determine the angle of the line to all three points from the origin point, and then check to see if the test angle is in between the two other angles but I'm trying to figure out if there's a better way to do it. The function is run tens of thousands of times an update and I'm hoping that there's a better way to achieve what I'm trying to do.

Steve
  • 127
  • 3
  • 13
  • I assume you mean the "acutest" angle created by the first 3 point, correct? Also, your current approach seems right to me. You *are* using a dot-product to determine the angle, yes? – Ani Jul 12 '12 at 16:52
  • I'm sorry, I'm not sure what "acutest" angle is. It sounds like it means the smallest angle, but I'm not certain. Currently, I'm using Math.Atan2(Vector2, Vector2) to determine the angle of the lines. My current approach works fine, but I'm hoping that there's a cheaper way to determine whether or not the point is within the range of the three others. If the three other points were to just create a simple triangle, it'd be easy but the two lines extend out indefinitely so I'm not sure if there's a way to do this. – Steve Jul 12 '12 at 17:00

4 Answers4

2

Let's say you have angle DEF (E is the "pointy" part), ED is the left ray and EF is the right ray. 

      * D (Dx, Dy)
     /
    /          * P (Px, Py)
   /
  /
 *---------------*
E (Ex, Ey)       F (Fx, Fy)

Step 1. Build line equation for line ED in the classic Al * x + Bl * y + Cl = 0 form, i.e. simply calculate

    Al = Dy - Ey                    // l - for "left"
    Bl = -(Dx - Ex)
    Cl = -(Al * Ex + Bl * Ey)

(Pay attention to the subtraction order.)

Step 2. Build line equation for line FE (reversed direction) in the classic Ar * x + Br * y + Cr = 0 form, i.e. simply calculate

    Ar = Ey - Fy                    // r - for "right"
    Br = -(Ex - Fx)
    Cr = -(Ar * Ex + Br * Ey)

(Pay attention to the subtraction order.)

Step 3. For your test point P calculate the expressions

    Sl = Al * Px + Bl * Py + Cl
    Sr = Ar * Px + Br * Py + Cr

Your point lies inside the angle if and only if both Sl and Sr are positive. If one of them is positive and other is zero, your point lies on the corresponding side ray.

That's it.

Note 1: For this method to work correctly, it is important to make sure that the left and right rays of the angle are indeed left and right rays. I.e. if you think about ED and EF as clock hands, the direction from D to F should be clockwise. If it is not guaranteed to be the case for your input, then some adjustments are necessary. For example, it can be done as an additional step of the algorithm, inserted between steps 2 and 3

Step 2.5. Calculate the value of Al * Fx + Bl * Fy + Cl. If this value is negative, invert signs of all ABC coefficients: 

Al = -Al, Bl = -Bl, Cl = -Cl
Ar = -Ar, Br = -Br, Cr = -Cr

Note 2: The above calculations are made under assumption that we are working in a coordinate system with X axis pointing to the right and Y axis pointing to the top. If one of your coordinate axes is flipped, you have to invert the signs of all six ABC coefficients. Note, BTW, that if you perform the test described in step 2.5 above, it will take care of everything automatically. If you are not performing step 2.5 then you have to take the axis direction into account from the very beginning.

As you can see, this a precise integer method (no floating point calculations, no divisions). The price of that is danger of overflows. Use appropriately sized types for multiplications.

This method has no special cases with regard to line orientations or the value of the actual non-reflex angle: it work immediately for acute, obtuse, zero and straight angle. It can be easily used with reflex angles (just perform a complementary test).

P.S. The four possible combinations of +/- signs for Sl and Sr correspond to four sectors, into which the plane is divided by lines ED and EF. 

            * D
           / 
   (-,+)  /    (+,+)
         /
 -------*------------* F
       / E
(-,-) /     (+,-)
     /

By using this method you can perform the full "which sector the point falls into" test. For an angle smaller than 180 you just happen to be interested in only one of those sectors: (+, +). If at some point you'll need to adapt this method for reflex angles as well (angles greater than 180), you will have to test for three sectors instead of one: (+,+), (-,+), (+,-).

AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
  • I attempted to use your formulas and here is the result. Something seems very wrong and I can't tell if it's me that input it incorrectly or if my explanation of what I was trying to figure out was unclear. I'm swapping between three different methods that were given to me. http://youtu.be/e9h16q-n8Mk You may need to watch the video at the highest resolution to see the bool changing between true and false and between who's formula is currently selected. I feel like it's so far off that something must be drastically off. – Steve Jul 14 '12 at 08:44
  • here is how I implemented the methods provided. http://i935.photobucket.com/albums/ad199/fobwashed/formulas.jpg – Steve Jul 14 '12 at 09:02
  • @Steve: Well, you made an obvious typo in the implementation of "my" method: `float A1 = a.X - origin.Y`. It should be `float A1 = a.Y - origin.Y`. Also note that for this method it is important to understand which ray is the left ray of the angle and which ray is the right ray of the angle. In your case for this to work correctly the vector `beginVec2, endVec2` should go *from left to right* when observed from `origin`. If it goes from right to left, then the criterion changes: both `Sl` and `Sr` must be *negative* for the point to be inside. – AnT stands with Russia Jul 14 '12 at 15:47
  • @Steve: I added an edit to my answer (see "Note" and "Step 2.5") to explain how to deal with this. – AnT stands with Russia Jul 14 '12 at 15:47
  • Sorry for any offense in labeling it "your" method. I'm attempting to implement three different approaches and needed to indicate that =( I corrected the typo. The way everything is set up, the beginVec2 and endVec2 will always be obtained in a clockwise manner. Wherever the beginVec2 starts, the endVec2 will always be a clockwise rotation relative to the origin being the vertex. This is what it sounds like you meant with the beginVec2 and endVec2 going left to right when observed from the origin, but it didn't seem to work until I changed it to checking S1 and Sr to both be negative. – Steve Jul 14 '12 at 18:59
  • After that, everything works perfectly until the angle between the two points becomes greater than 180 degrees at which point things get a bit wonky. It will always register as true only when it's within range of the given angle but the angle that it registers as true begins to shrink more and more as the angle being tested gets larger and larger. I'll try to take another video and put it up for you to see. The only changes to the code I made was your correction on my typo and changing the S1 and Sr check to <= 0. Thank you so much for taking the time to help =) – Steve Jul 14 '12 at 19:04
  • Aside from the possibility of overflow if the coordinates get too high, this does seem like it'll run the fastest. Though I'll have to profile to be sure =P – Steve Jul 14 '12 at 19:05
  • @Steve: I suspect that in your coordinate system the Y axis is pointing *down*, not up. Is it so? If so, then you have to adjust for it as well. You can **either** 1) assume that negative `Sl` and `Sr` indicate that the point is inside (which is what you already did), **or** 2) simply invert the signs of all six ABC coefficients. I'll add another note to the answer. See **Note 2**. – AnT stands with Russia Jul 14 '12 at 19:48
  • @Steve: Exactly. You are using screen coordinates with X-axis pointing to the right and Y-axis pointing **down**. This will cause "sign flip" effect in all methods that involve "topological" calculations (left, right, clockwise, counterclockwise, etc.). Just invert sign for all ABC coefficients calculated in steps 1 and 2, and the test will produce positive `Sl` and `Sr` values for points inside the angle. – AnT stands with Russia Jul 14 '12 at 19:56
  • Thank you! You're correct in that the Y axis points downwards. I should have mentioned that initially, sorry about that as well. After inverting the sign for all six coefficients, things are working properly but I am still encountering the issue of when the angle is greater than 180 degrees that is visible in the video I last posted. As you can see, once the angle is greater than 180, the range that returns true decreases. Is there any way to fix this or do I need to just insure that any angles checked using this method doesn't exceed 180 degrees? – Steve Jul 14 '12 at 21:25
  • @Steve: As I mentioned before, what this method really does is splits the plane into 4 sectors. For each sector, you will get different combination of `+/-` signs from `Sl` and `Sr`: `(+,+)`, `(-,+)`, `(+,-)` and `(-,-)`. If the angle is 180 or less, you just need *one* sector: `(+, +)`. If you want to handle an angle that is greater than 180 (so called *reflex* angle), you will have to check for *three* sectors: `(+,+)`, `(-,+)`, `(+,-)`. I.e. you will have to apply a slightly different final criterion for (step 3) angles greater than 180. – AnT stands with Russia Jul 14 '12 at 22:20
  • @Steve: Alternatively, for angles greater than 180, you can run the test "for the other side", i.e. for the *complementary* angle (which in that case will be *less* than 180). If the point is in the complementary angle, then it is not in your angle and vice versa. – AnT stands with Russia Jul 14 '12 at 22:23
  • Does the function need to be told explicitly whether it is checking for an angle greater than 180 degrees if I check for three sectors or could I use something along the lines of "if ((+,+) || (-,+) || (+,-)) {return true;}" ?. If it needs to be explicitly told, I suppose I'd have to get the angle that DEF creates and determine if it's >180 for every single check. The main reason for my OP question was to avoid the calculations required with getting the angle of ED and EF and hopefully get a little more accuracy than working with float radians. – Steve Jul 14 '12 at 22:48
  • @Steve: It is a question of *how* you specify the angle. The function does not know which angle you need: the "smaller" one or the "bigger" one. If you accept as convention that we always test for the sector that is swept from `DE` to `FE` in *clockwise* direction, then it becomes unambiguous. In this case the function can by itself determine whether the angle is reflex or not by performing an internal test: calculate `Al * Fx + Bl * Fy + Cl`. If it is positive, the angle is less than 180 (test for `(+,+)`). If it is negative, the angle is more than 180. (test for `(+,+)`, `(-,+)`, `(+,-)`) – AnT stands with Russia Jul 14 '12 at 23:23
  • @Steve: Is in this method you will have to do branching for "less than 180" and "more than 180" situations. How you distinguish former from the latter is up to you. You can pass it from the outside, as a function parameter. Or you can accept the convention I described in my previous comment and recognize reflex angles internally (again, as described in my previous comment). – AnT stands with Russia Jul 14 '12 at 23:26
  • Thank you! I had to reverse the result of the check that determines whether or not the angle is the reflex or not. I believe this had to do with the check being run just prior to testing which plane it was on and by that point, the coefficients used all had their sign flipped by that point. So when the number is positive, it would check for all three planes while if it was negative, it'd only check against the one. Thank you again for your incredible help. I'm going to have to run some testing to be certain, but I think it should prove to run very fast. Thanks for your patience and help =) – Steve Jul 15 '12 at 05:20
1

Describe your origin point O, and the other 2 points A and B then your angle is given as AOB. Now consider your test point and call that C as in the diagram.

enter image description here

Now consider that we can get a vector equation of C by taking some multiple of vector OA and some multiple of OB. Explicitly 

  C = K1 x OA + K2 OB

for some K1,K2 that we need to calculate. Set O to the origin by subtracting it (vectorially) from all other points. If coordinates of A are (a1,a2), B = (b1,b2) and C = (c1,c2) we have in matrix terms

 [ a1 b1 ] [ K1 ] = [ c1 ]
 [ a2 b2 ] [ K2 ] = [ c2 ]

So we can solve for K1 and K2 using the inverse of the matrix to give

  1 / (a1b2 - b1a2)  [ b2 -b1 ] [ c1 ] = [ K1 ]
                     [ -a2 a1 ] [ c2 ] = [ K2 ]

which reduces to

 K1 = (b2c1 - b1c2)/(a1b2 - b1a2)
 K2 = (-a2c1 + a1c2)/(a1b2 - b1a2)

Now IF the point C lies within your angle, the multiples of the vectors OA and OB will BOTH be positive. If C lies 'under' OB, then we need a negative amount of OA to get to it similarly for the other direction. So your condition is satisfied when both K1 and K2 are greater than (or equal to) zero. You must take care in the case where a1b2 = b1a2 as this corresponds to a singular matrix and division by zero. Geometrically it means that OA and OB are parallel and hence there is no solution. The algebra above probably needs verifying for any slight typo mistake but the methodology is correct. Maybe long winded but you can get it all simply from point coordinates and saves you calculating inverse trig functions to get angles.

The above applies to angles < 180 degrees, so if the your angle is greater than 180 degrees, you should check instead for

 !(K1 >= 0 && K2 >= 0)

as this is exterior to the segment less than 180 degree. Remember that for 0 and 180 degrees you will have a divide by zero error which must be checked for (ensure a1b2 - b1a2 != 0 )

mathematician1975
  • 21,161
  • 6
  • 59
  • 101
  • Thanks for taking the time to help =) Though unfortunately, due to either my error in implementing your formulas or some kind of misscommunication on what I'm trying to achieve, things aren't working how I'd like them to. I thought it might be best to upload a video of it in action to illustrate what I'm trying to achieve and in what range things aren't working properly. http://youtu.be/e9h16q-n8Mk If you could maybe take a look, I'd be really thankful. =) – Steve Jul 14 '12 at 08:47
  • @Steve I have a type in there - ill correct it now., one of the matrix terms is wrong – mathematician1975 Jul 14 '12 at 08:59
  • Here is how I implemented it. http://i935.photobucket.com/albums/ad199/fobwashed/formulas.jpg – Steve Jul 14 '12 at 09:01
  • @Steve In your K2 calculation change the part b.X * c.Y to a.X * c.Y and it should work – mathematician1975 Jul 14 '12 at 09:05
  • @Steve Sorry about that - I had a matrix term error. Probably because it was 03:30 when i input this answer. Hope it works for you now. – mathematician1975 Jul 14 '12 at 09:36
  • Not a problem at all =) I made the change and it seems to work beautifully with one caveat. The angle that it checks for is always the acute angle formed and not the obtuse one. So if the cone is greater than 180 degrees, it'll check for whether or not the test point falls on or outside of the cone. Do you have any workaround for this? The reason why my points are labeled beginVec2 and endVec2 are because of the way I retrieve the points. They will always be retrieved in a clockwise manner with the begin being first, then the end being a clockwise rotation from the begin. – Steve Jul 14 '12 at 18:47
  • @Steve It only works for 180 degrees or less (dont forget 180 degrees wont work exactly otherwise you divide by zero). But if the angle is greater than 180 then if K1 and K2 are greater than zero you are OUTSIDE the interior so just check for K1<0 && K2<0 when your angle is greater than 180 – mathematician1975 Jul 14 '12 at 18:50
  • Yes - when the angle is greater than 180 degrees, use `!(K1>0 && K2>0)` to test – mathematician1975 Jul 14 '12 at 19:19
  • Unfortunately, I can only mark one answer as correct and I can't yet vote up other comments =( Your help is incredibly appreciated and I'm super thankful but there was another answer that resulted in what I needed including a way to determine whether the angle is greater 180 degrees using the points provided. I can't stress enough how appreciative I am of your help. I'm so sorry that I can't mark multiple posts as answers =( Thank you again! When I can, I will return and upvote your help! – Steve Jul 15 '12 at 05:27
0

Yes, I meant the smallest angle in my comment above. Look at this thread for an extensive discussion on cheap ways to find the measure of the angle between two vectors. I have used the lookup-table approach on many occasions with great success.

Community
  • 1
  • 1
Ani
  • 10,826
  • 3
  • 27
  • 46
0

Triangle O B C has to be positive oriented and also triangle O C A. To calaculate orientation, just use Shoelace formula. Both values has to be positive.

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
  • 1
    With any "topological" method, if it turns out that the OP is working with a coordinate system where X-axis is pointing right and Y-axis is pointing *down*, then the signs of all "topological" values will have to be inverted. Same issue as in my answer. – AnT stands with Russia Jul 14 '12 at 19:52