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.

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