The final puzzle piece is how much to increment \u03b1 at each iteration, to ensure that every pixel is drawn properly?<\/p>\n
C (Circumference of a circle) = \u03c0 * d (diameter)<\/p>\n
d = r (radius) * 2, therefore<\/p>\n
C = 2\u03c0r<\/p>\n
C is the number of pixels you have to draw, and a complete circle is 2\u03c0 radians, so:<\/p>\n
\u03b1i (incremental angle) = 2\u03c0 \/ 2\u03c0r<\/p>\n
And, what’s nice about radians is that everything cancels:<\/p>\n
\u03b1i = 1 \/ r<\/p><\/blockquote>\n
In code, drawing a circle using trig would look like this:<\/p>\n
const pi2=2*Math.PI;\r\n\r\nfunction XtrigCircle(cx , cy , radius , r,g,b){\r\n var ai=1\/radius; \/\/ incremental angle\r\n var x,y;\r\n\r\n for(var a = 0 ; a<pi2 ; a+=ai){\r\n x=Math.trunc( radius * Math.cos(a) );\r\n y=Math.trunc( radius * Math.sin(a) );\r\n\r\n plot( cx + x , cy + y ,r,g,b);\r\n }\r\n}<\/pre>\nHere is a sample output using 0..\u03c0\/2 (90 degrees) in order to demonstrate how the sweep works:<\/p>\n
![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Output-trig-90deg.png\")
<\/p>\n
<\/p>\n
This works fine for an outline of a circle, but how do we draw a filled circle?<\/p>\n
At first thought, drawing concentric circles (incrementing the radius) seems like a good idea, but it’s computationally-expensive.<\/p>\n
Instead, we can exploit the symmetrical properties of a circle:<\/p>\n
![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Circle-symmetry.png\")
<\/p>\n
The concept is to do a 90-degree sweep through the (+,+) quadrant to get all of the (x,y) points, but use symmetry to mirror them within the other quadrants.\u00a0 Here is a revised circle-outline function using symmetry:<\/p>\n
const piDiv2=Math.PI\/2;\r\n\r\nfunction XtrigCircle2( cx , cy , radius , r,g,b ){\r\n var ai=1\/radius;\r\n var x,y;\r\n\r\n for( var a=0 ; a<=piDiv2 ; a+=ai ){\r\n x=Math.trunc( radius * Math.cos(a) );\r\n y=Math.trunc( radius * Math.sin(a) );\r\n\r\n plot( cx+x , cy+y , r,g,b ); \/\/ lower-right\r\n plot( cx-x , cy+y , r,g,b ); \/\/ lower-left\r\n plot( cx+x , cy-y , r,g,b ); \/\/ upper-right\r\n plot( cx-x , cy-y , r,g,b ); \/\/ upper-left\r\n }\r\n}<\/pre>\nOutput from the above:<\/p>\n
![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Output-formula-3.png\")
<\/p>\n
To convert this to a filled circle, we loop from the left-half to the right-half:<\/p>\n
function XtrigFillCircle( cx , cy , radius ,r,g,b ){\r\n var ai=1\/radius;\r\n var x,y,x1,x2,y1,y2;\r\n\r\n for(var a=0 ; a<=piDiv2 ; a+=ai) { \/\/ see above for piDiv2\r\n x=Math.trunc( radius * Math.cos(a) );\r\n y=Math.trunc( radius * Math.sin(a) );\r\n\r\n y1=cy-y;\r\n y2=cy+y;\r\n x1=cx-x;\r\n x2=cx+x;\r\n\r\n for(var xx=x1 ; xx<=x2 ; xx++){\r\n plot( xx , y1 , r,g,b ); \/\/ upper half\r\n plot( xx , y2 , r,g,b ); \/\/ lower half\r\n }\r\n }\r\n}<\/pre>\nHere is the output of the trig-fill function:<\/p>\n
![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Output-trig-fill.png\")
<\/p>\n
<\/p>\n
<\/p>\n
<\/span>Quadratic Circles<\/span><\/h2>\nAside from trigonometry, a circle can be defined by this quadratic equation:<\/p>\n
x2<\/sup> + y2<\/sup> = r2<\/sup><\/p><\/blockquote>\n![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Circle-formula.png\")
<\/p>\n
As you can see, this is related to the Pythagorean theorem, where any given radius of the circle is the hypotenuse of a right triangle (similar to trigonometry).<\/p>\n
\n\n\nx2<\/sup> + y2<\/sup> = r2<\/sup><\/td>\n| (x,y) lies on the circumference<\/td>\n<\/tr>\n | \nx2<\/sup> + y2<\/sup> < r2<\/sup><\/td>\n| (x,y) lies on the interior<\/td>\n<\/tr>\n | \nx2<\/sup> + y2<\/sup> > r2<\/sup><\/td>\n| (x,y) lies outside<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Instead of sweeping a range of angles in order to draw the circumference, we can sweep a range of y values { -r .. r }, then for a given y, solve for x:<\/p>\n y = { -r .. r }<\/p>\n x = sqrt( r2<\/sup>\u00a0– y2<\/sup>\u00a0)<\/p><\/blockquote>\nTaking in to account an offset to the center, we can plot the following coordinates:<\/p>\n \n- ( cx – x , cy + y )\u00a0 \/\/ left half<\/li>\n
- ( cx + x , cy + y )\u00a0 \/\/ right half<\/li>\n<\/ul>\n
Further, we can exploit symmetry, as we did above for the trig-based function by cutting the range in half, where y = { 0 .. r }<\/p>\n \n- (cx -x , cy -y ) \/\/ upper-left<\/li>\n
- (cx+x , cy-y)\u00a0 \/\/ upper-right<\/li>\n
- (cx-x , cy+y)\u00a0 \/\/ lower-left<\/li>\n
- (cx+x , cy+y)\u00a0 \/\/lower-right<\/li>\n<\/ul>\n
Here is an example for drawing solid circles using the quadratic equation for a circle:<\/p>\n function XquadFillCircle( cx , cy , radius , r,g,b ){\r\n var x,xx,y,x1,x2,y1,y2;\r\n\r\n var ys, rs=radius * radius;\r\n\r\n for( y=0 ; y<=r ; y++ ){\r\n ys=y*y;\r\n x=Math.trunc( Math.sqrt( rs-ys ) );\r\n\r\n y1=cy-y;\r\n y2=cy+y;\r\n x1=cx-x;\r\n x2=cx+x;\r\n\r\n for( xx=x1 ; xx<=x2 ; xx++ ){\r\n plot( xx , y1 , r,g,b ); \/\/ top half\r\n plot( xx , y2 , r,g,b ); \/\/ bottom half\r\n }\r\n }\r\n}<\/pre>\nThis produces nearly the same filled circle from the trig-fill example above:<\/p>\n <\/p>\n However, if we do just an outline by plotting just x1 and x2 rather than looping, we get the following:<\/p>\n ![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Output-formula-1.png\") <\/p>\n
The gaps at the top and bottom occur because our code assumes there is only one x coord for every given y coord, and we are using y as our independent variable.\u00a0 As the slope increases beyond 45 degrees, we would need to use x as the independent variable in order to maintain single-pixel stepping.<\/p>\n To accomplish this we can exploit another symmetry of circles.<\/p>\n ![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Circle-formula-symmetry.png\") <\/p>\n
If an angle is below 45 degrees ( \u03c0\/\/4 ) we can single-step y (top, partial circle in the diagram above).\u00a0 However, since x and y are symmetrical, we can swap them in order to form the top and bottom of the circle (bottom, partial circle in the diagram above).<\/p>\n The point where 45 degrees ( \u03c0\/\/4 ) intercepts the vertical axis can be found by two different methods:<\/p>\n if \u03b1 = \u03c0\/2 then cos(\u03b1) = sin(\u03b1) = 0.707<\/p>\n and<\/p>\n if right \u0394 with hypotenuse r=1, and sides a=b, then<\/p>\n r2<\/sup> = a2<\/sup>\u00a0+ b2<\/sup><\/p>\nSince a = b,<\/p>\n r2<\/sup>\u00a0= 2a2<\/sup><\/p>\nSince r=1,<\/p>\n a2<\/sup> = 1\/2, and<\/p>\na = 0.707<\/p>\n So, if we want to loop from our intercept point…<\/p>\n r’ = r * 0.707, and our range is<\/p>\n y = { 0 .. r’ }<\/p><\/blockquote>\n In Javascript, it looks like this:<\/p>\n function XquadCircle( cx , cy , radius , r,g,b ){\r\n var x,y,x1,x2,y1,y2;\r\n var rs=radius*radius;\r\n var ys;\r\n var rp=Math.trunc( radius * 0.707 );\r\n\r\n for( y=0 ; y<=rp ; y++){\r\n ys=y*y;\r\n x=Math.trunc( Math.sqrt(rs - ys) );\r\n\r\n plot( cx-x , cy-y ,r,g,b ); \/\/ left-upper\r\n \u00a0plot( cx+x , cy-y ,r,g,b ); \/\/ right-upper\r\n plot( cx-x , cy+y ,r,g,b ); \/\/ left-lower\r\n plot( cx+x , cy+y ,r,g,b ); \/\/ right-lower\r\n }\r\n}<\/pre>\nAnd, the output looks like this:<\/p>\n ![\"\"](\"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-content\/uploads\/Output-formula-2.png\") <\/p>\n
As expected, we see the left and right sides.\u00a0 To get the top and bottom, we need to add four more plots which transpose x and y offsets:<\/p>\n for(y...\r\n ...\r\n plot( cx-y , cy-x ,r,g,b ); \/\/ top-left\r\n plot( cx-y , cy+x ,r,g,b ); \/\/ bottom-left\r\n plot( cx+y , cy-x ,r,g,b ); \/\/ top-right\r\n plot( cx+y , cy+x ,r,g,b ); \/\/ bottom-right\r\n ...\r\n}<\/pre>\nAnd we get a complete circle:<\/p>\n <\/p>\n <\/p>\n <\/span>Conclusion<\/span><\/h2>\nMaking circles using the quadratic formula for a circle is fast and easy, and way more computationally-efficient.<\/p>\n <\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Here is THE fastest and most computationally-efficient circle algorithm.<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-8130","post","type-post","status-publish","format-standard","hentry","category-other-stuff"],"_links":{"self":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/8130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/comments?post=8130"}],"version-history":[{"count":10,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/8130\/revisions"}],"predecessor-version":[{"id":8162,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/8130\/revisions\/8162"}],"wp:attachment":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/media?parent=8130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/categories?post=8130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/tags?post=8130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
| | | |