[Math] How to find the dimensions & new points after rotating a shape

geometrytrigonometry

Given a set of shapes with properties (width, height, angle, x, y), I need help determining their new dimensions & points after rotating them.

Points to consider:

  • Angles can be both positive & negative. Though unsure, it was pre-determined by the
    direction of rotation (user interaction).
  • X & Y will be the the upper left vertex of a shape.
  • Y starts from the top instead of bottom.
  • Rotation originates from the center of the shape.

Sample data which will be plotted on the same plane:

Please take note that the point(x, y) is the upper left vertex of the shape

Shape A

  • Width = 413
  • Height = 413
  • Angle = 156 deg
  • Point(887, 2730)

Shape B:

  • Width = 420

  • Height = 154

  • Angle = -63 deg

  • Point(3751, 2898)

Shape C:

  • Width = 280
  • Height = 140
  • Angle = -90 deg
  • Point(2403, 1988)

Shape D:

  • Width = 350
  • Height = 266
  • Angle = 90 deg
  • Point(2534, 3866)

I came across some known solutions online but will always get incorrect results. My confusion comes from the angle that can be both positive & negative, and then the non-standard orientation of plane where the starting point is upper left then goes down & to the right.

Please see the link below for a sample image based on the given data.

sample image

Thanks in advance.

Best Answer

Based on the image OP's illustration you have a left-handed coordinate system, where $x$ increases right, and $y$ down. Given axis-aligned bounding boxes' upper left corner coordinates, width, and height, you wish to find the axis-aligned bounding boxes after rotation by some angle around their center.

It looks like positive angles indicate counterclockwise rotation. In a left-handed coordinate system, this means rotation by $\varphi$ around point $(x_0 , y_0)$ is $$\begin{cases} x^\prime = x_0 + (x - x_0) \cos(\varphi) - (y - y_0) \sin(\varphi) \\ y^\prime = y_0 + (x - x_0) \sin(\varphi) + (y - y_0) \cos(\varphi) \end{cases}$$ where $(x, y)$ are the coordinates before the rotation, and $(x^\prime , y^\prime)$ after the rotation.

Let's say $( x_{min} , y_{min} )$ are the upper left coordinates, $w$ is the width, and $h$ is the height of the axis-aligned bounding box. Then,

  • $x_{min}$ is the left edge of the axis-aligned bounding box,

  • $y_{min}$ is the top edge of the axis-aligned bounding box,

  • $x_{max} = x_{min} + w$ is the right edge of the axis-aligned bounding box, and

  • $y_{max} = y_{min} + h$ is the bottom edge of the axis-aligned bounding box.

The four corners of the axis-aligned bounding box are therefore $( x_{min} , y_{min} )$, $( x_{max} , y_{min} )$, $( x_{min} , y_{max} )$, and $( x_{max} , y_{max} )$. When it is clear that we are talking about axis-aligned bounding boxes, this is often written in simplified form as $( x_{min} , y_{min} ) - ( x_{max} , y_{max} )$; i.e. as the diagonal line segment (in increasing coordinates).

If the center of rotation is at the center of the axis-aligned bounding box, then $$\begin{cases} x_0 = x_{min} + \frac{w}{2} = \frac{x_{min} + x_{max}}{2} \\ y_0 = y_{min} + \frac{h}{2} = \frac{y_{min} + y_{max}}{2} \end{cases}$$

Let's say we have an axis-aligned bounding box, and we know $x_{min}$, $y_{min}$, and have calculated $x_{max}$, $y_{max}$, $x_0$, and $y_0$, and that we want to rotate this by $\varphi$ (positive if clockwise, negative if counterclockwise, in this left-handed coordinate system).

There are two ways of calculating the axis-aligned bounding box after the rotation. First way is to calculate the four corner point coordinates: $$\begin{aligned} x_1 &= x_0 + (x_{min} - x_0) \cos \varphi - (y_{min} - y_0) \sin\varphi \\ y_1 &= y_0 + (x_{min} - x_0) \sin \varphi + (y_{min} - y_0) \cos\varphi \\ x_2 &= x_0 + (x_{max} - x_0) \cos \varphi - (y_{min} - y_0) \sin\varphi \\ y_2 &= y_0 + (x_{max} - x_0) \sin \varphi + (y_{min} - y_0) \cos\varphi \\ x_3 &= x_0 + (x_{min} - x_0) \cos \varphi - (y_{max} - y_0) \sin\varphi \\ y_3 &= y_0 + (x_{min} - x_0) \sin \varphi + (y_{max} - y_0) \cos\varphi \\ x_4 &= x_0 + (x_{max} - x_0) \cos \varphi - (y_{max} - y_0) \sin\varphi \\ y_4 &= y_0 + (x_{max} - x_0) \sin \varphi + (y_{max} - y_0) \cos\varphi \end{aligned}$$ so that after the rotation, we pick the smallest and largest coordinates: $$\begin{aligned} x_{min} &= \min( x_1 , x_2 , x_3 , x_4 ) \\ y_{min} &= \min( y_1 , y_2 , y_3 , y_4 ) \\ x_{max} &= \max( x_1 , x_2 , x_3 , x_4 ) \\ y_{max} &= \max( y_1 , y_2 , y_3 , y_4 ) \\ w &= x_{max} - x_{min} \\ h &= y_{max} - y_{min} \end{aligned}$$

The other way is to note that since the original shape is a rectangle, and we rotate around its center, two of the corners are just mirrored around the center; and we can simply find the largest coordinates in magnitude with respect to the rotation center: $$\begin{aligned} x_{\Delta} &= \left \lvert \frac{w}{2} \cos \varphi \right \rvert + \left\lvert \frac{h}{2} \sin \varphi \right \rvert \\ y_{\Delta} &= \left \lvert \frac{w}{2} \sin \varphi \right \rvert + \left\lvert \frac{h}{2} \cos \varphi \right \rvert \\ \end{aligned}$$ where $\lvert \; \rvert$ refer to taking the absolute value. Then, you can update the axis-aligned bounding box properties using $$\begin{aligned} x_{max} &= x_0 + x_{\Delta} = x_{min} + \frac{w}{2} + x_\Delta \\ y_{max} &= y_0 + y_{\Delta} = y_{min} + \frac{h}{2} + y_\Delta \\ x_{min} &= x_0 - x_{\Delta} = x_{min} + \frac{w}{2} - x_\Delta \\ y_{min} &= y_0 - y_{\Delta} = y_{min} + \frac{h}{2} - y_\Delta \\ w &= 2 x_\Delta \\ h &= 2 y_\Delta \end{aligned}$$ where the operations need to be done in the order shown (but you can omit $x_{max}$ and $y_{max}$, so that all right sides use the values prior to rotation (except for $x_\Delta$ and $y_\Delta$, of course).

In pseudocode, the rotation operation can be written as

Function rotate_aabb(xmin, ymin, width, height, angle):
    Let  c = cos(angle)
    Let  s = sin(angle)
    Let  halfw = 0.5*width
    Let  halfh = 0.5*height
    Let  xdelta = abs(c*halfw) + abs(s*halfh)
    Let  ydelta = abs(s*halfw) + abs(c*halfh)

    Let  xmin = xmin + halfw - xdelta
    Let  ymin = ymin + halfw - ydelta
    Let  width = 2*xdelta
    Let  height = 2*ydelta

    Return (xmin, ymin, width, height) 
End Function

which can be implemented using one sin, one cos, six multiplications, eight additions or subtractions, and four absolute values.

When rotating e.g. around the upper left corner, we have fewer symmetries:

Function rotate_aabb(xmin, ymin, width, height, angle):
    Let  c = cos(angle)
    Let  s = sin(angle)

    Let  x1 =  c*width
    Let  y1 =  s*width
    Let  x2 = -s*height
    Let  y2 =  c*height

    Let  x3 = x1 + x2
    Let  y3 = y1 + y2

    Let  txmin = min(0, x1, x2, x3)
    Let  txmax = max(0, x1, x2, x3)
    Let  tymin = min(0, y1, y2, y3)
    Let  tymax = max(0, y1, y2, y3)

    Let  width = txmax - txmin
    Let  height = tymax - tymin
    Let  xmin = xmin + txmin
    Let  ymin = ymin + tymin

    Return (xmin, ymin, width, height) 
End Function

and we need one sin and one cos, four multiplications, six additions or subtractions, and twice an operation to find the maximum and minimum among four values, one of which is zero.

In C (C99 or later), you can implement min(0, x1, x2, x3) as fmin(fmin(0.0, x1), fmin(x2, x3)) and max(0, y1, y2, y3) as fmax(fmax(0.0, y1), fmax(y2, y3)), although

txmin = 0.0;
if (txmin > x1) txmin = x1;
if (txmin > x2) txmin = x2;
if (txmin > x3) txmin = x3;

tymax = 0.0;
if (tymax < y1) tymax = y1;
if (tymax < y2) tymax = y2;
if (tymax < y3) tymax = y3;

and similarly for txmax and tymin, should generate optimal code on architectures with hardware min/max instructions, if optimizations are enabled. For example, on x86-64 with GCC 5.4.0 with -O2, the above generates a sequence of minsd and maxsd instructions (and no jumps, so no slowdown due to conditional expressions at all).

The notable downside of calculating the rotated bounding box based on the previous bounding box, is that unless the rotation is a multiple of 90°, the bounding box will become larger after every rotation.

Related Question