How do I partition an oriented bounding box?

Question

I am writing code that will build an oriented bounding box (obb) tree for a (not necessarily convex) polygon in 2 dimensions.

So far, I'm able to find the area-minimal obb of a polygon by finding its convex hull and using rotating calipers on the hull.

The picture below is an example of this. The yellow-filled polygon with red lines and red points depicts the original polygon. The convex hull is shown in blue with black lines and the obb is shown as purple lines.

(Edit) As requested: Interactive Version - tested only in chrome

Now I want to extend my code to build an OBB tree, instead of just an OBB. This means I have to cut the polygon, and compute new OBBs for each half of the polygon.

The recommended way to do this seems to be to cut the polygon by cutting the OBB in half. But if I cut the obb through the middle in either of its axes it looks like I would have to create new vertices on the polygon (otherwise how do I find the convex hull of that partition?).

1. Is there a way to avoid adding vertices like this?
2. If not, what is the easiest way to do it (with respect to implementation difficulty)? What is the most runtime-efficient way?

Answer 1

Here's an example of a concave polygon that we want to create an OBB tree for:

In order to split it into a new set of concave polygons, we can simply cut our current polygon by cutting the bounding box down the middle and adding new 'intersection' vertices as appropriate:

:

This can be done in O(vertices) time because we can simply iterate through all of the edges, and add an intersection vertex if the edge crosses the red splitting line.

The polygon can then be divided in terms of these intersection vertices to get a new set of smaller (but still possibly concave) polygons. There will be at least two such polygons (one per side of the red line) but there may be more. In this next picture, the new polygons have been colored for emphasis:

Recursively computing the oriented bounding boxes for these smaller polygons gives the desired result. For example, here are the boxes from recursion depth 2:

Hopefully this is clear enough to help someone who's struggling the same way I was!