OOP and dichotomy: two powerful tools to the programmer
15/04/2024

The problem addressed here, as a demonstration of the power of Object Oriented Programming and dichotomy, is to compute the vertices coordinates of a polygon circumscribing an ellipse, in the context of a milling purpose.

In the figure above, the considered ellipse is in green. The inscribed simply regular polygon in red is easy to compute. Its $n$ vertices are: $$x=acos(2\mathrm{\pi }\frac{i}{n})$$ $$y=bsin(2\mathrm{\pi }\frac{i}{n})$$ $$withifrom0ton-1$$

However, it is a crude approximation to the ellipse and is not suitable at all to milling purpose…

The polygon in blue, derived from the intersections of the tangents to the ellipse at each of the vertices of the red polygon, is a better approximation and is adapted to milling purpose.

However, the distances (indicated by the figures next to its vertices) from each vertex to the ellipse vary from simple to double. Intuitively, there should be more vertices when the curvature is more important.

What we want here is illustrated by the dynamic computation accessible by clicking on the figure below:

This computation is done by a double nested dichotomy and an Object Oriented Programming approach.

Computing the distance to the ellipse

The distance of a point $(x,y)$ to a point $(acost,bsint)$ on the ellipse is: $$f\left(t\right)=\sqrt{{(acost-x)}^2+{(bsint-y)}^2}$$

And we are looking for the shortest distance to the ellipse which is the smallest value of $f\left(t\right)$ which happens for the zero of $\mathrm{f\text{'}}\left(t\right)$. That is to say solving the equation: $$(b^2-a^2)costsint+axsint-bycost=0$$

Which is beyond the mathematical knowledge of even the best programmer of numerunique… Fortunately there is another way and that is where comes the first dichotomy.

The figure above shows the fists 6 steps (segments in blue) of the dichotomy process applied to compute the distance from the point to the ellipse (black segment between the third and the sixth).

The point 1 is at the median position between points a and b.

There, the distance is increasing, thus the next step considers the point 2 which is at the median position between points a and 1.

There, the distance is decreasing, thus the next step considers the point 3 which is at the median position between points 2 and 1.

There, the distance is increasing, thus the next step considers the point 4 which is at the median position between points 2 and 3.

And so on until the arbitrary looked for precision is reached. At each step, the range of the searched position is divided by 2 ; the convergence is very fast and thus the process very efficient.

Computing the next suitable tangent to the ellipse

The same principle applies to computing the next tangent which intersection will be at a given distance to the ellipse, distance which is computed as above, hence the nested dichotomy.

On the figure below, the current tangent is in black, the result we are looking for is in red and the successive attempts are in blue.

Advantages of an Object Oriented Programming approach

Indeed, it greatly helps on concentrating on the concepts, hiding the low level complexity, to achieve a simple, more human readable solution.

A point has two coordinates: x and y.
A line is defined by a point and its directing vector.
An ellipse is defined by its parameters a and b.
On line 120 in the program extract above, the parametric equation of a point on the ellipse is straightforward.
The tangent to the ellipse on the point thus defined is as simple as it looks on line 126.

The dichotomy algorithme is coded in seven lines: 134-136 and 140-143 or, with exactly the same instructions, at 155-157 and 169-172.

The mathematically unsolvable equation is expressed on line 138. And the computation of the distance to the ellipse within the search of the next suitable tangent is done by the instructions at the lines 159-163:

• 159 : the next considered tangent,
• 160 : its intersection with the current tangent,
• 161-162 : the closest point ont the ellipse,
• 163 : its distance.

Yes, it is that simple!

Précédent