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 highlevel 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 5gon.
Benchmark
Description
The benchmark was created for assessing the efficiency of the algorithm and comprises convex ngons 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 ngons were generated. Thus the total number of convex ngons in the data set is 10000.
A txt file with the name benchmark_<number_of_points>_<unique_id>.txt
corresponds to each ngon. These files have the following format:
 First line contains the number of points defining the convex ngon;
 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 5gon is given below:
benchmark_5_1.txt

5

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 minimalareatriangle github repository.