wenmin-wu/tabular-convex-hull-bbox-rotation

Convex Hull Bounding Box Rotation

Overview

An axis-aligned bounding box is rarely the tightest enclosure. Rotating the point cloud before computing the AABB can significantly reduce its area or max side length. Only the convex hull vertices matter, so reduce to hull first. Then use scipy.optimize.minimize_scalar to find the rotation angle that minimizes the bounding box metric — much faster than brute-force angle sweeps.

Quick Start

import numpy as np
from scipy.optimize import minimize_scalar
from scipy.spatial import ConvexHull

def bbox_side_at_angle(angle_deg, points):
    rad = np.radians(angle_deg)
    c, s = np.cos(rad), np.sin(rad)
    rot = np.array([[c, s], [-s, c]])
    rotated = points @ rot
    span = rotated.max(axis=0) - rotated.min(axis=0)
    return max(span[0], span[1])

def optimal_bbox_rotation(all_points):
    pts = np.array(all_points)
    hull_pts = pts[ConvexHull(pts).vertices]
    initial = bbox_side_at_angle(0, hull_pts)
    res = minimize_scalar(
        lambda a: bbox_side_at_angle(a, hull_pts),
        bounds=(0.001, 89.999), method='bounded')
    if initial - res.fun > 1e-10:
        return res.fun, res.x
    return initial, 0.0

best_side, best_angle = optimal_bbox_rotation(points)

Workflow

1. Collect all boundary points (polygon vertices) from placed objects
2. Compute convex hull to reduce point count
3. Define objective: max side length of AABB at rotation angle θ
4. Optimize θ in [0°, 90°) using bounded scalar minimization
5. Apply the optimal rotation to all objects for the tightest enclosure

Key Decisions

• Hull reduction: checking only hull vertices is exact and O(n log n) cheaper
• Rotation matrix: points @ rot.T is vectorized and fast for large point sets
• Search range: [0°, 90°) covers all unique orientations by symmetry
• Metric: max(width, height) for square-like target; area for rectangle target

References

• Santa-submission