I have a trivial function that rotates 2d vectors, and a method in a class representing a polygon that rotates every point in the polygon around an origin. The code is fairly optimized as it is, but I was wondering if there is any faster way of doing it, since the function is called a HUGE amount of times and I need it to be as fast as it can possibly be.
Here is the code for the rotation function (in a file called geo.py):
def rotate_vector(v, angle, anchor):
"""Rotate a vector `v` by the given angle, relative to the anchor point."""
x, y = v
x = x - anchor[0]
y = y - anchor[1]
# Here is a compiler optimization; inplace operators are slower than
# non-inplace operators like above. This function gets used a lot, so
# performance is critical.
cos_theta = math.cos(angle)
sin_theta = math.sin(angle)
nx = x*cos_theta - y*sin_theta
ny = x*sin_theta + y*cos_theta
nx = nx + anchor[0]
ny = ny + anchor[1]
return [nx, ny]
And here is the code for the polygon object:
import geo
class ConvexFrame(object):
"""A basic convex polygon object."""
def __init__(self, *coordinates, origin=None):
self._origin = origin
# The coordinates in this object are stored as offset values, that is,
# coordinates that represent a certain displacement from the given origin.
# We will see later that if the origin is None, then it is set to the
# centroid of all the points.
self._offsets = []
if not self._origin:
# Calculate the centroid of the points if no origin given.
self._origin = geo.centroid(*coordinates)
orx, ory = self._origin
append_to_offsets = self._offsets.append
for vertex in coordinates:
# Calculate the offset values for the given coordinates
x, y = vertex
offx = x - orx
offy = y - ory
append_to_offsets([offx, offy])
offsets = self._offsets
left = geo.to_the_left
# geo.to_the_left takes three vectors (v0, v1 and v2) and tests if vector v2
# lies to the left of the line between v0 and v1. The offset values are input
# in counter-clockwise order, so all points v(i) should lie to the left of the
# the line v(i-2)v(i-1).
n = len(offsets)
for i in range(n):
v0 = offsets[i-1]
v1 = offsets[i]
v2 = offsets[(i+1)%n]
if not left(v0, v1, v2):
raise ValueError("""All vertices of the polygon must be convex.""")
def rotate(self, angle, anchor=(0, 0)):
# Avg runtime for 4 vertices: 7.2e-06s
orx, ory = self._origin
x, y = anchor
if x or y:
# Default values of x and y (0, 0) indicate
# for the method to use the frame origin as
# the anchor. Since we are rotating the offset
# values and not actually the coordinates, we
# have to adjust the anchor relative to the origin.
x = x - orx
y = y - ory
_rot = geo.rotate_vector
self._offsets = [_rot(v, angle, (x, y)) for v in self._offsets]
If I can get this below 3e-06s for 4 vertices that would be phenomenally helpful.
UPDATE 1:
Just found an optimization; in the list comprehension I say (x, y) every iteration, meaning I have to rebuild the tuple every single iteration. Removing that shaves the time down to between 7e-06 and 6.9e-06s for 4 vertices.
def rotate2(self, angle, anchor=(0, 0)):
# Avg runtime for 4 vertices: 7.0e-06s
# Best time of 50 tests: 6.92e-06s
orx, ory = self._origin
x, y = anchor
if x or y:
# Default values of x and y (0, 0) indicate
# for the method to use the frame origin as
# the anchor.
x = x - orx
y = y - ory
anchor = x, y
_rot = geo.rotate_vector
self._offsets = [_rot(v, angle, anchor) for v in self._offsets]
