CODEWITHSUNDEEP
javascriptmathrotation
Jacob Gunther
Jacob Gunther

Reputation: 361

Find the bounding box of a rotated polygon with an axis of rotation

I've looked through some of the other close answers here but can't find any solutions to my problem.

I have a polygon that is rotated around an axis position, and I need to find the bounding box of the polygon. Essentially, the bounding box object should have the x and y position of the top left corner, and the width and height of the box itself. I am able to calculate the box of the polygon without rotation using this code, but it doesn't account for rotation too. The red square is the current bounding box without rotation, the green circle is the rotation axis, and the polygon is the polygon itself.

Rotated polygon with non-rotated bounding box

Ideally, I don't want to re-compute each vertex position on each call to get the bounding box, I want it to be in the math itself. Here's an example of the polygon and the bounding box without rotation: https://i.imgur.com/MSOM9Q1.mp4

Here is my current code for finding bounding box for the non-rotated polygon:

const minX = Math.min(...this.vertices.map((vertex) => vertex.x));
const minY = Math.min(...this.vertices.map((vertex) => vertex.y));

return {
    x: minX + this.position.x,
    y: minY + this.position.y,
    width: Math.max(...this.vertices.map((vertex) => vertex.x)) - minX,
    height: Math.max(...this.vertices.map((vertex) => vertex.y)) - minY
};

Polygon object structure:

Polygon object structure

Bounding box structure:

Bounding box object structure

What do I need to do calculate the bounding box of the rotated polygon?

Upvotes: 1

Views: 812

Answers (1)

Spektre
Spektre

Reputation: 51835

if you do not want to recompute the axis aligned BBOX from all the vertexes of polygon after any rotation/translation then do it from OBB that is only 4 vertexes ...

  1. Compute OBB of unrotated/untranslated polygon

    this operation is slow but its done just once (unless your polygon is changing shape or size)

  2. At any transformation of polygon

    transform the OBB vertexes in the same way too. And then compute axis aligned BBOX from transformed OBB vertexes (just finding min/max coordinates as you do now).

This way you have to compute stuff from only 4 vertexes instead of Ntransforming the complexity from O(N) into O(1).

Also having OBB might come in handy later on as it can speed up some operation or even improve precision of collision testing etc ...

Upvotes: 2

Related Questions