Calculating AABB of a Rotated 2D Rectangle

Warning! Some information on this page is older than 5 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Wed
02
Jun 2010

Today I've solved an interesting geometrical problem of calculating an AABB rectangle (Axis-Aligned Bounding Box) around an oriented rectangle (rotated by an angle) in 2D.

AABB of a rotated 2D rectangle

It seems simple but it's easy to come up with suboptimal solution like calculating all 4 corners of the rotated rectangle or calling sin and cos functions multiple times. So I've coded a simple demonstration in ActionScript 3 (Flash). Here is my algorithm:

Input data:

// Center position of the rectangle.
private const m_PosX : Number, m_PosY : Number;
// Half-width and half-height of the rectangle.
private const m_HalfSizeX : Number, m_HalfSizeY : Number;
// Rectangle orientation, in radians.
private var m_Orientation : Number;

Algorithm:

// corner_1 is right-top corner of unrotated rectangle, relative to m_Pos.
// corner_2 is right-bottom corner of unrotated rectangle, relative to m_Pos.
var corner_1_x : Number = m_HalfSizeX;
var corner_2_x : Number = m_HalfSizeX;
var corner_1_y : Number = -m_HalfSizeY;
var corner_2_y : Number =  m_HalfSizeY;

var sin_o : Number = Math.sin(m_Orientation);
var cos_o : Number = Math.cos(m_Orientation);

// xformed_corner_1, xformed_corner_2 are points corner_1, corner_2 rotated by angle m_Orientation.
var xformed_corner_1_x : Number = corner_1_x * cos_o - corner_1_y * sin_o;
var xformed_corner_1_y : Number = corner_1_x * sin_o + corner_1_y * cos_o;
var xformed_corner_2_x : Number = corner_2_x * cos_o - corner_2_y * sin_o;
var xformed_corner_2_y : Number = corner_2_x * sin_o + corner_2_y * cos_o;

// ex, ey are extents (half-sizes) of the final AABB.
var ex : Number = Math.max(Math.abs(xformed_corner_1_x), Math.abs(xformed_corner_2_x));
var ey : Number = Math.max(Math.abs(xformed_corner_1_y), Math.abs(xformed_corner_2_y));

var aabb_min_x : Number = m_PosX - ex;
var aabb_max_x : Number = m_PosX + ex;
var aabb_min_y : Number = m_PosY - ey;
var aabb_max_y : Number = m_PosY + ey;

Files to download:
AabbTest01.swf - online Flash demo
AabbTest01.zip - full project source code

I believe it can be optimized further (not only by rewriting it in C++ :) Anyone knows how?

Comments | #math #flash Share

Comments

[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2019