Minimum area enclosing triangle algorithm implementation

Related publication

Ovidiu Pârvu and David Gilbert, Implementation of linear minimum area enclosing triangle algorithm, Computational and Applied Mathematics, Springer, pp. 1–16, November 2014 (Open Access)

Abstract

An algorithm which computes the minimum area triangle enclosing a convex polygon in linear time already exists in the literature. The paper describing the algorithm also proves that the provided solution is optimal and a lower complexity sequential algorithm cannot exist. However, only a high-level description of the algorithm was provided, making the implementation difficult to reproduce. The present note aims to contribute to the field by providing a detailed description of the algorithm which is easy to implement and reproduce, and a benchmark comprising 10000 variable sized, randomly generated convex polygons for illustrating the linearity of the algorithm.

Simple usage example

The video below illustrates the step by step execution of the algorithm for a convex 5-gon.

Benchmark

Description

The benchmark was created for assessing the efficiency of the algorithm and comprises convex n-gons generated randomly using the Computational Geometry Algorithms Library (CGAL). The value of n ranges from 100 to 10000 with a step size of 100. For each value of n 100 random n-gons were generated. Thus the total number of convex n-gons in the data set is 10000.

A txt file with the name benchmark_<number_of_points>_<unique_id>.txt corresponds to each n-gon. These files have the following format:

  • First line contains the number of points defining the convex n-gon;
  • The next n lines contain the coordinates of the points: <point_x_coordinate> <point_y_coordinate>;
  • The last line is blank.

An example of a txt file describing a convex 5-gon is given below:

benchmark_5_1.txt
5
300 700
400 480
643 200
800 1100
1202 1005

Download

A free copy of the benchmark dataset is made available here.

Correctness

All correctness verification approaches described in the scientific note have been implemented in C++ and are made freely available in the minimal-area-triangle github repository.