3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ itertools.combinations \$\endgroup\$ – hjpotter92 Jul 22 '18 at 21:29
  • \$\begingroup\$ How are you using this, do you need all the angles? \$\endgroup\$ – Peilonrayz Jul 22 '18 at 21:40
  • \$\begingroup\$ @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. \$\endgroup\$ – pydude Jul 23 '18 at 14:46
  • \$\begingroup\$ @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. \$\endgroup\$ – Peilonrayz Jul 23 '18 at 14:49
  • \$\begingroup\$ @Peilonrayz But specific direction==angle (I think), so I need to see if the points are in that specific direction. \$\endgroup\$ – pydude Jul 23 '18 at 14:53
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.