A better and quicker way
31/08/2024
The previous solution to compute the polygon circumscribed to an ellipse as an example of the benefit of OOP and dichotomy has two weaknesses: it gives an irregular polygon and the last vertex is often closer to the ellipse than all the others.
This enhanced version of the algorithm fixes these two problems.
A regular polygon is found by a strategy that uses the double symmetry of an ellipse: horizontal and vertical. Only the vertices of the first quadrant are computed, a vertical symmetry is used to compute the vertices of the second quadrant and an horizontal symmetry is applied to compute the remaining vertices.
The precision criteria is applied to the most distant vertex which is replaced by two new vertices computed to insert a new edge tangent to the ellipse at the orthogonal projection of that vertex. This is repeated until all vertices are closer to the ellipse than the requested precision.
As for the programming techniques illustrated by this new algorithm, dichotomy is still used to compute the distance of a vertex to the polygon and a double linked list is used to manage the vertices thus allowing an easy insertion of the new vertices.
This technique converges very quickly :
