Search code examples
pythonangle

Signed angle between directed line segments

I have an algorithm in which I need to work out the signed angle (-180 to 180) between edges in a graph. I've done some research and found plenty of specific answers but can't figure out how to relate them to my situation (e.g. this question which uses atan2, however the OP wanted only positive angles) I've tried implementing a few different ways (using atan2 or arccos) but I'm struggling to relate the examples to my specific problem. I've tried treating the edges as vectors but got strange results.

Given a graph with points (A, B, C, D, E), and the average of those points (avg)... how do I find the signed angle between one of those points (e.g. A) and the other points (e.g. B, C, D, E), taking the angle from the current origin (A) to the 'avg' point as equal to 0 degrees. Example below...

enter image description here

...in this example, the anti-clockwise angle from (A, avg) to (A, B) would be positive something (between 0 and 180), and the angle from (A, avg) to (A, E) would be negative something (between 0 and -180).

Ideally I want a formula which I could also apply to defining any of the points as the origin, for example taking point C as the origin.. the 'zero angle' would be (C, avg) and the angle between (C, avg) and (C, A) would be negative (0 to -180) and the angle between (C, avg) and (C, E) would be positive (0 to 180).

I haven't studied math beyond high-school so I find it hard to decipher equations with symbols I don't understand.

UPDATE: Thought I'd clean this up to make it more obvious what the conclusion was. I made two small changes to the accepted answer, resulting in the below snippet:

def angle(vertex, start, dest):
    AhAB = math.atan2((dest.y - vertex.y), (dest.x - vertex.x))
    AhAO = math.atan2((start.y - vertex.y), (start.x - vertex.x))
    AB = AhAB - AhAO
    # in between 0-math.pi = do nothing, more than math.pi = +(-2 * math.pi), less than zero = do nothing
    AB = math.degrees(AB + (-2 * math.pi if AB > math.pi else (2 * math.pi if AB < 0 - math.pi else 0)))
    return AB

...the final one-liner may be a bit much to grok after a few months of not working on this, so I turned it into it's own function, taking the result of AB = AhAB - AhAO as it's argument...

def calc(ab):
    if ab > math.pi:
        return ab + (-2 * math.pi)
    else:
        if ab < 0 - math.pi:
            return ab + (2 * math.pi)
        else:
            return ab + 0

I thought this was a little clearer to read, though more lines.

The final function in full:

def angle(vertex, start, dest):
    """Calculates the signed angle between two edges with the same origin. 
       Origin is the 'vertex' argument, 'start' is the bounding point of the edge to calculate the angle from.
       Positively signed result means anti-clockwise rotation about the vertex."""

    def calc_radians(ab):
        if ab > math.pi:
            return ab + (-2 * math.pi)
        else:
            if ab < 0 - math.pi:
                return ab + (2 * math.pi)
            else:
                return ab + 0

    AhAB = math.atan2((dest.y - vertex.y), (dest.x - vertex.x))
    AhAO = math.atan2((start.y - vertex.y), (start.x - vertex.x))

    res = calc_radians(AhAB - AhAO)

    return math.degrees(res)

Note: The function assumes the three arguments will all be instances of a typical Point class with x and y attributes. Also, the example graph above has only positive values, but I am fairly sure that this works with graphs that involve negative values too.

Solution

  • I read your problem statement as follows: given 2 points A and B, and a center O, find the angle A to B as the angle, positive if anticlockwise, between the vectors A→O and A→B.

    If my premises are correct, then you can

    • find the angle between A→B and a horizontal, rightward line passing in A,
    • find the angle between A→O and a horizontal, rightward line passing in A,
    • find the angle A to B as the difference of said angles,
    • normalize the result range so that it's between -π and +π.

    What I've said can be visualized as follows

    enter image description here or in code (assuming a Point class with attributes x and y)

    AhAB = math.atan2((B.y-A.y), (B.x-A.x)) # -π < AhAB ≤ +π
AhAO = math.atan2((O.y-A.y), (O.x-A.x)) # -π < AhA) ≤ +π
AB = AhAB - AhAO                        # -2π < AB ≤ +2π
AB = AB + ( 2*math.pi if AB < math.pi else (-2*math.pi if AB> math.pi else 0))

    Addendum

    Here it is a small code example, the position of the points is just similar to what you can see in the picture

    In [18]: from math import atan2, pi
In [21]: class Point():
    ...:     def __init__(self, x, y):
    ...:         self.x, self.y = x, y
    ...:     def __repr__(self):
    ...:         return '(%s, %s)'%(self.x, self.y)
In [22]: A = Point(0.0, 0.0)
In [23]: B = Point(-2.0, 2.0)
In [24]: O = Point(0.0, -3.0)
In [25]: AhAB = atan2((B.y-A.y), (B.x-A.x)) ; print(3/4, AhAB/pi)
0.75 0.75
In [26]: AhAO = atan2((O.y-A.y), (O.x-A.x)) ; print(-1/2, AhAO/pi)
-0.5 -0.5
In [27]: AB = AhAB - AhAO ; print(5/4, AB/pi)
1.25 1.25
In [28]: AB = AB + ( 2*pi if AB < pi else (-2*pi if AB> pi else 0)) ; print(AB/pi)
-0.75
In [29]:

    The last line normalize your result AB to be in the correct range -π < AB ≤ π, adding or subtracting 2π that doesn't change the meaning of the measured angle.