Minimum area enclosing triangle algorithm implementation
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)
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.
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:
- The last line is blank.
An example of a txt file describing a convex 5-gon is given below:
A free copy of the benchmark dataset is made available here.
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.