0

enter image description here

How can I tell what is the first segment to the right of AB? So we start walking from A, reach B and then I need to go most right - to C. But how do I find this mathematically? Bear in mind that there could be more segments from B in any direction. (some of them or all of them could be to the left of B - in my image C and D are to the right)

We do have all coordinates of vertices - x and y!

I am thinking to

  • find if C and D are to the right or left of line going trough AB,
  • if both are to the right, draw a perpendicular from C to AB and a perpendicular from D to AB and the shortest distance from A to the perpendiculars is the winner?
alex toader
  • 2,300
  • 1
  • 17
  • 20
  • Please let me refer you to this question: [How to know if point is on right or left side of line](https://stackoverflow.com/questions/68592435/how-to-know-if-point-is-on-the-right-side-or-on-the-left-side-of-line/68592731#68592731) – Stef Aug 26 '21 at 17:35
  • 1
    Note that in the question I linked, the question only asks whether one given point is on the right or the left; but the answer provides code that gives the "right-leftness" of a point as a number between +1 and -1; you should choose a point with the sign that you want (negative for right, positive for left), and the closest to zero. – Stef Aug 26 '21 at 17:37
  • Also please note that you might get different result if you look at it from A's perspective or from B's perspective. – Stef Aug 26 '21 at 17:38
  • @Stef Thanks I was wondering how that helps me. I will have to implement it in coding and feed some scenarios and see how it works. I will let you know! – alex toader Aug 26 '21 at 17:39
  • You have to specify what is measure for `more to the right`. Angle ABC? Distance (perpendicular) from C to AB line as you wrote? – MBo Aug 26 '21 at 17:59
  • @MBo more to the right is like you walk down a street and take the First right. That is the most right. Hope that explains it. – alex toader Aug 26 '21 at 18:14
  • 1
    So you need minimal angle? (angle ABC < ABD) – MBo Aug 26 '21 at 18:17
  • @MBo yes I think that should do it. Not sure if it solves all the cases.. but I think it does.. – alex toader Aug 26 '21 at 18:19

1 Answers1

1

You have coordinates AX, AY, BX, BY and PX, PY for every other point.

It is necessary to calculate minimal angle between vectors P-B and A-B among all points P[i]

abx = AX - BX
aby = AY - BY  //calculate once

pbx = PX - BX
pby = PY - BY  //calculated for every point

angle = atan2(-pbx*aby+pby*abx, pbx*abx+pby*aby)
if angle < 0:
    angle += 2*Math.pi  //to make range 0..2*Pi

Calculate angle for every point (uses function atan2, Math.atan2 in some languages and cross product and dot product of vectors), then choose minimum value - it corresponds "the most right turn"

Python code

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks. I will write some code for it and try it. Another way I see now is - I can draw triangles and find the angle from the triangle. Any idea which one will be more efficient/faster approach? – alex toader Aug 26 '21 at 18:34
  • 1
    For triangles you have to use trigonometric functions anyway, and approach with atan2 is more effective. I added link to working Python code. Note I changed sign inside atan parentheses. – MBo Aug 26 '21 at 18:39
  • thanks. I need it in PHP but I think they should be similar. Many thanks! – alex toader Aug 26 '21 at 18:44
  • one more question pls - the first segment to left is the one for which this algorithm returns the largest number? Looks like it but just to be sure.. – alex toader Aug 27 '21 at 14:21
  • 1
    Yes. Angle range is from 0 to 2Pi. Angles 0..Pi corresponds to the right turn, angles Pi..2Pi - to te left turn, larger values for the leftmost – MBo Aug 27 '21 at 14:29