Smallest Bounding Box for Point Cloud | Dataford Interview Questions

Align Technology's ClinCheck software can analyze 2D projections of intraoral scans. Given a finite point cloud, find the minimum-area rectangle that contains every point, allowing the rectangle to have any orientation.

Return the rectangle's area, width, height, and orientation. The orientation is the angle in radians between the rectangle's width side and the positive x-axis, normalized to the interval [0, π/2).

Formal Specification

Implement minimum_bounding_box(points), where points is a list of distinct or repeated 2D points represented as [x, y]. Return [area, width, height, angle], with every numeric value rounded to six decimal places. If multiple rectangles have the same minimum area, any one is valid.

The minimum-area rectangle has at least one side collinear with an edge of the point cloud's convex hull. Therefore, first compute the convex hull, then evaluate each hull-edge orientation.

Constraints

1 <= len(points) <= 2,000
Each point has exactly two coordinates
Coordinates are finite real numbers in [-10^6, 10^6]
Repeated points may occur
Output values must be rounded to six decimal places
Multiple minimum-area rectangles may exist

Function Signature

def minimum_bounding_box(points):

Your question is Smallest Bounding Box for Point Cloud. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem