5
\$\begingroup\$

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]
\$\endgroup\$
5
\$\begingroup\$

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[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]
\$\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.