# Optimize vector rotation

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
y = y - anchor
# 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
ny = ny + anchor
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]


You will likely be rotating many vectors by the same angle. Therefore, it would be wasteful to compute $\cos \theta$ and $\sin \theta$ repeatedly.

The typical way to think of linear transformations is as matrix multiplication:

$$\left[ \begin{array}{c} x' \\ y' \end{array} \right] = \left[ \begin{array}{rr} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\ \right] \left[ \begin{array}{c} x \\ y \end{array} \right]$$

So, define a make_rotation_transformation(angle, origin) function that returns a closure that holds the transformation matrix and origin vector.

from math import cos, sin

def make_rotation_transformation(angle, origin=(0, 0)):
cos_theta, sin_theta = cos(angle), sin(angle)
x0, y0 = origin
def xform(point):
x, y = point - x0, point - y0
return (x * cos_theta - y * sin_theta + x0,
x * sin_theta + y * cos_theta + y0)
return xform


def rotate(self, angle, anchor=(0, 0)):
xform = make_rotation_transformation(angle, anchor)
self._offsets = [xform(v) for v in self._offsets]