Find leftmost point in 2D

[terier]

Assume we have a line, defined by two points (A and B), and a set of points we have to test. Now we have to find the point where the angle PHI (see image) is the largest we can find. If we mirror a point over the line, the test should yield different results, as we want only negative-oriented points.

I guess the algorithm could first test if orientation is negative

Code: Select all

(ax-cx)*(by-cy)-(bx-cx)*(ay-cy) > 0

and then calculate the angle for all suitable points using

Code: Select all

phi = arccos(A.dot(B) / (A.length() * B.length())

but since this is computationally intense if there are many points to test, I wonder if there's any other way..

[nespa]

see getHorizontalAngle():

Code: Select all

      vector3df B,E,F,result1,result2;
      f32 PHI1,PHI2,PHI;

      result1 =E-B;
      result1 = result1.getHorizontalAngle();
      PHI1=result1.Y;

      result2 =F-B;
      result2 = result2.getHorizontalAngle();
      PHI2=result2.Y;

      PHI=PHI1-PHI2;
                
                if (PHI>180)
                 {
                     PHI=-(360-PHI)
                  };

[CuteAlien]

Not sure if it's faster. But I suppose another way of getting the result could be:

First normalize all lines. Next add AB to the secondary line vectors (normalized BC, BD, etc). For the resulting vector get the length (or faster, the square-length). If the resulting vector is left of AB you'll want the shortest length, if it's right of AB you'll want the largest length. Figuring out if it's left or right can be done similar - you add the normalized secondary vectors to the perpendicular vector of AB (AB rotated 90° to the right), and if the length of adding those increases you are on the right, when it decreases on the left.

[terier]

Thanks for replies, guys
@nespa getHorizontalAngle() includes a sqrt calculation and 2 arctan calculations, so I don't think that would be a good choice. Thanks for working on my problem though
@CuteAlien I will definitely try this one, not sure what impact the normalizations will have on speed, but worth experimenting a bit.