HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Optimize vector rotation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
vectoroptimizerotation

Problem

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 = s

Solution

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]

Code Snippets

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]

Context

StackExchange Code Review Q#47003, answer score: 5

Revisions (0)

No revisions yet.