Draw a Circle Without Floating Point Arithmetic
[Math] Drawing a circumvolve, point-by-betoken, without floating point support
Now we need to add a circle to our clock.
Circumvolve is defined by Pythagorean theorem: $ten^2 + y^2 = r^2$, where $x$ and $y$ -- coordinates on plain and $r$ is radius.
Naive algorithm
So let's draw it! Enumerate all points in 0..radius range and discover "peak" for each bespeak. Height will exist $\sqrt{r^two - y^2}$ Nosotros will draw only a quadrant, i.e., $\frac{i}{iv}$ of the circle:
<!doctype html> <html> <caput> <style> #my-canvass { border: 1px solid gray; } </style> </head> <body> <canvass id="my-canvass" width="600" height="600"></sail> <script> var canvas = document.querySelector('#my-canvas'); var context = sheet.getContext('2d'); var half_width = canvas.width/2; var half_height = canvas.height/2; // clock is slightly smaller than sail: var clock_radius = Math.min(half_width, half_height)*0.85; function putPixel(x, y) { context.fillRect(x+half_width, y+half_height, one, i); }; part circumvolve() { // x^two + y^2 = radius^2 // ten^ii = radius^2 - y^ii // x=sqrt(radius^2 - y^2) for (x=0; x<clock_radius; x++) { var y=Math.sqrt(clock_radius*clock_radius - x**ii); putPixel(x, y); } }; circumvolve(); </script> </trunk> </html> 
Ouch! This arc looks correct, only the points at right-lesser are "dispersed".
The mutual way is to draw only octant ($\frac{1}{8}$) of a circle and and so "copy" the octant 7 times more. But to draw a 45° angle (or $\frac{\Pi}{4}$) y'all have to apply some trigonometry.
office circle() { // Pi/4 = octant. find a betoken on ten where octant is concluded: var octant_limit = clock_radius * Math.cos(Math.PI/4); for (ten=0; 10<octant_limit; x++) { var y=Math.sqrt(clock_radius*clock_radius - x**2); putPixel(x, y); } }; Looks dainty:
Now copy it seven more times:
for (x=0; 10<octant_limit; x++) { var y=Math.sqrt(clock_radius*clock_radius - x**two); putPixel(x, y); // copy our octant vii times: putPixel(x, -y); putPixel(-x, y); putPixel(-x, -y); putPixel(y, x); putPixel(y, -x); putPixel(-y, ten); putPixel(-y, -x); } 
Midpoint circumvolve algorithm
Naive algorithm is correct, but it requires at least 1 "heavy" operation -- square root.
Hither I will rework my algorithm a fleck:
function circumvolve(x0, y0, radius) { // starting signal: var x = radius; var y = 0; while (x >= y) { // main octant: putPixel(x0 + x, y0 + y); // copy octant 7 times: putPixel(x0 + y, y0 + x); putPixel(x0 - y, y0 + x); putPixel(x0 - x, y0 + y); putPixel(x0 - x, y0 - y); putPixel(x0 - y, y0 - x); putPixel(x0 + y, y0 - x); putPixel(x0 + x, y0 - y); y=y+1; var new_radius=Math.sqrt(x**2 + y**2).toFixed(); // besides convert to int // nosotros check here if the 'new radius' becomes too big // if so, subtract $10$ // we practice this to maintain the equation x^2 + y^2 = r^2 (for integer arithmetic) if (new_radius>radius) ten=10-1; } }; 
We "maintain" the equation here. If radius becomes too big, we get "stray" indicate back, so that it volition always lay on circle's border.
And this algorithm has also square root performance.
Please annotation -- we recalculate "new_radius" at each iteration. Tin can we "update" that value rather than scratching from offset? "Accommodate" it?
Yes, if we know a bits of calculus. I described it earlier. Instead of recalculating $x^2$ each time, we can add derivative to some temporary variable: $2x + ane$.
The function volition be different now:
part circumvolve(x0, y0, radius) { // starting point: var x = radius; var y = 0; var current_radius_squared = radius**2; while (x >= y) { // main octant: putPixel(x0 + ten, y0 + y); // copy octant 7 times: putPixel(x0 + y, y0 + x); putPixel(x0 - y, y0 + x); putPixel(x0 - x, y0 + y); putPixel(x0 - x, y0 - y); putPixel(x0 - y, y0 - x); putPixel(x0 + y, y0 - x); putPixel(x0 + x, y0 - y); // increase $y$ and update $current_radius$ y += 1; current_radius_squared += ii*y + 1; // if $current_radius$ is bigger than $radius$, decrease $x$ and update $current_radius$ again // nosotros do this to maintain the equation 10^2 + y^2 = r^ii (for integer arithmetic) if (current_radius_squared > radius**2) { x -= ane; current_radius_squared -= ii*x + one; } } }; Please annotation: we don't maintain current radius anymore. We maintain information technology in "squared" form. current_radius_squared is always equals to the $10^two + y^2$ expression.
So if in the expression $x^2 + y^two$, $ten$ is increased by 1, but add $2x + ane$ to it. If decreased by 1, subtract. No need to summate power(s).
Also, since nosotros precomputed $r^2$ value at outset, nosotros tin can use at every bit "reference" value.
Isn't it cool to apply some calculus to a real-life problem?
The third version is merely an optimization. Here we don't maintain current radius, we maintain just mistake or divergence between radius-we-have and radius-must-be.
This version is highly pop and y'all'll find it when googling for the midpoint circle algorithm.
function circumvolve(x0, y0, radius) { // starting indicate: var x = radius; var y = 0; var err = 0; while (x >= y) { // main octant: putPixel(x0 + ten, y0 + y); // copy octant 7 times: putPixel(x0 + y, y0 + 10); putPixel(x0 - y, y0 + x); putPixel(x0 - x, y0 + y); putPixel(x0 - x, y0 - y); putPixel(x0 - y, y0 - x); putPixel(x0 + y, y0 - ten); putPixel(x0 + x, y0 - y); // increase $y$ and update $err$ y += one; err += 2*y + 1; // if $err$ is bigger than zero, decrease $ten$ and update $err$ again // we exercise this to maintain the equation x^2 + y^ii - r^two = 0 (for integer arithmetic) if (err > 0) { x -= one; err -= two*10 + 1; } } }; The concluding optimized version is absurd. It requires only additions, subtractions and bit shifts: $2x$ is the same as x<<1, of class. It as well requires only integer arithmetic.
Summary: many explanations of midpoint algorithm employ the final, optimized version. Merely I added several unoptimized steps.
In that location are couple of web log posts I read to amend understanding. Mukund Sivaraman, Neeraj Mishra.
Equally seen at lobste.rs, HN.
List of my other blog posts.
yeagerafroackly62.blogspot.com
Source: https://yurichev.com/news/20220322_circle/
0 Response to "Draw a Circle Without Floating Point Arithmetic"
Postar um comentário