Home » Linear minimum area enclosing triangle implementation

Linear minimum area enclosing triangle implementation

Problem

Given an arbitrary set of points in the 2D Euclidean plane compute the enclosing triangle having the minimum area.

Minimal area enclosing triangle example
Figure 1: An example of a set of points in the 2D Euclidean plane (highlighted in green) and the corresponding minimal area enclosing triangle (highlighted in red).

Theoretical solution

Based on an elegant geometric characterization provided by Klee and Laskowski O’Rourke developed a linear algorithm for addressing the above problem; see the An optimal algorithm for finding minimal enclosing triangles paper for more details.

Implementation

A detailed description of all required algorithms is provided in the Implementation of linear minimum area enclosing triangle algorithm paper and a C++ implementation of these algorithms is made freely available at https://github.com/IceRage/minimal-area-triangle.

Leave a Reply

Your email address will not be published. Required fields are marked *