0
$\begingroup$

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.

$\endgroup$
19
  • $\begingroup$ what do you mean by angle?? $\endgroup$ May 21 '18 at 19:28
  • $\begingroup$ @the integrator, the value used to rotate the shapes with. If it would help, please see the image uplink $\endgroup$
    – nonc
    May 21 '18 at 20:50
  • $\begingroup$ Are the “shapes” all rectangles? $\endgroup$
    – amd
    May 21 '18 at 20:53
  • $\begingroup$ This would be easier if you used linear algebra and rotation matrices $\endgroup$ May 21 '18 at 20:57
  • $\begingroup$ @amd, they can be squares as well. polygons to be exact $\endgroup$
    – nonc
    May 21 '18 at 20:57
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I stumbled upon a new requirement, this time the box/shape will be rotated by some angle around the upper left coordinates/top left corner (xmin, ymin) instead of the center of the shape. I already tried some substitutions and computations on my own, though no luck. How can I get the same desired values by changing the center of rotation or what can I change to do the same? Thank you. $\endgroup$
    – nonc
    May 23 '18 at 14:15
  • $\begingroup$ @nonc: There you go. Note that when rotating around a corner, we have much fewer symmetries to exploit, so the function is more complex, relatively speaking. The latter one can be extended to rotate around any of the four corners. A function rotating the AABB around an arbitrary point is almost the same, then x1, y1, ... need to be evaluated wrt. the center of rotation instead. $\endgroup$ May 23 '18 at 16:30

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.