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 vertexes of the first quadrant are computed, a vertical symmetry is used to compute the vertexes of the second quadrant and an horizontal symmetry is applied to compute the remaining vertexes.
The precision criteria is applied to the most distant vertex which is replaced by two new vertexes computed to insert a new edge tangent to the ellipse at the orthogonal projection of that vertex. This is repeated until all vertexes 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 vertexes thus allowing an easy insertion of the new vertexes.
This technique converges very quickly :
