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?

• hjpotter92: itertools.combinations
• Peilonrayz: How are you using this, do you need all the angles?
• Luke B: @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.
• Peilonrayz: @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.
• Luke B: @Peilonrayz But specific direction==angle (I think), so I need to see if the points are in that specific direction.

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.