Getting angle between all points in array

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]
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?

• itertools.combinations – hjpotter92 Jul 22 '18 at 21:29
• How are you using this, do you need all the angles? – Peilonrayz Jul 22 '18 at 21:40
• @Peilonrayz Yes, I need all the angles. Each point is a creature, and I need to see what other creatures are in its field of view. – Luke Borowy Jul 23 '18 at 14:46
• @pydude That sounds to me like you don't need all the points. You just need specific ones in specific directions. And since we don't know which direction the monsters are pointing, we can't help simplify that. – Peilonrayz Jul 23 '18 at 14:49
• @Peilonrayz But specific direction==angle (I think), so I need to see if the points are in that specific direction. – Luke Borowy Jul 23 '18 at 14:53

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)$.