patternpythonMinor
Optimize vector rotation
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
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
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
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 xformdef 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 xformdef 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.