CoreSource checked

Minimum Bounding Rectangle

Finds the smallest-area rectangle that encloses a set of points or a convex polygon.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Intermediate
Family: Bounding Geometry
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

Minimum bounding rectangle is commonly computed from a convex hull with rotating calipers over candidate edge orientations.

Core Concepts

convex hullrotating calipersoriented rectanglearea minimization

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

When to Use

Use when collision and intersection tests needs convex hull.
Use when the input matches the assumptions behind bounding Geometry.

When Not to Use

Avoid when floating-point robustness is critical and no tolerance strategy is defined.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Finds the smallest-area rectangle that encloses a set of points or a convex polygon
Uses convex hull and rotating calipers to guide the work.
Produces geometric relation, simplified shape, or constructed geometry.

Use Cases

Collision and intersection tests
Shape analysis
Geometry processing

Inputs

Points, segments, polygons, or meshes
Query shape or tolerance

Outputs

Geometric relation, simplified shape, or constructed geometry

Key Formulas (1)

Rectangle area

area = width · height

area = width * height

Scores each candidate orientation by its enclosing rectangle area.

Pseudocode

1.Prepare the inputs and state needed for Minimum Bounding Rectangle.
2.Apply the convex hull step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return geometric relation, simplified shape, or constructed geometry.

Canonical Example

Input: Minimum Bounding Rectangle input
Output: Geometric relation, simplified shape, or constructed geometry
Explanation: Minimum Bounding Rectangle applies convex hull to produce geometric relation, simplified shape, or constructed geometry.

Implementation Notes

Use robust orientation and tolerance checks for boundary cases.
Keep the convex hull step separate enough to test independently.

Common Pitfalls

Degenerate cases such as collinear points or shared edges often need explicit handling.
Test boundary and adversarial cases, not only ideal inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Draw the input shapes, active tests, and generated geometric result.

Step 1 of 4: Prepare the inputs and state needed for Minimum Bounding Rectangle.

geometry-mechanism

Notes

Minimum Bounding Rectangle operates in O(n log n) time and O(n) space within the Bounding Geometry family. Key governing relation: area = width * height. Often compared with Rotating Calipers and Convex Hull.