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[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]
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  &amp; -\sin \theta \\
  \sin \theta &amp; \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[0] - x0, point[1] - 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]