Getting angle between all points in array

Question

I have got some code that calculates the angle between all of the points in an array. It works, but it is quite slow. This is because it has complexity O(n^2). It has to loop through the array and apply the angle function to every combination of points.

import math
import random
def angle(pos1,pos2):
    dx=pos2[0]-pos1[0]
    dy=pos2[1]-pos1[1]
    rads=math.atan2(dy,dx)
    rads%=2*math.pi
    degs=math.degrees(rads)
    return degs
class Point(object):
    def __init__(self):
        self.pos=[random.randint(0,500) for _ in range(2)]#random x,y
        self.angles=[]
points=[Point() for _ in range(100)]
for point in points:
    point.angles=[] #so that each frame, they will be recalculated
    for otherC in points:
        if otherC is point:continue #don't check own angle
        ang=angle(point.pos,otherC.pos)
        point.angles.append(ang)

I feel like it could be greatly sped up by using numPy or some other method. I did some searching (here), but all I could find was functions to get angle between planes, or complex numbers. I just need simple arrays. How can this code be optimized for more speed?

Answer 1

Mathematically, if you have the angle between \$ A(x_1, y_1) \$ and \$ B(x_2, y_2) \$, given as:

$$ \theta = \tan^{-1}{\dfrac{y_2 - y_1}{x_2 - x_1}} \tag{in degrees} $$

then, the angle between \$ B \$ and \$ A \$ would be:

$$ \phi = 180° + \theta \mod {360°} $$

The \$ \mod{360} \$ is simply there if you want results in the interval \$ [0, 360) \$.

---

With the above, you'll only need to calculate angles between 2 points once, halving the number of calculations performed.