25:["$","title",null,{"children":"Pixelated circle | Change Is Coming (Gramsavers) | Observable"}] 49:Teaa,{ const size = 200; const pixels = cfg.pixels; const ctx = DOM.context2d(pixels, pixels); const ctx2 = DOM.context2d(size, size); ctx.canvas.width = ctx.canvas.height = pixels; ctx2.canvas.width = ctx2.canvas.height = size; const div = document.createElement('div'); div.append(ctx.canvas, ctx2.canvas); div.style.width = div.style.height = ctx.canvas.style.width = ctx.canvas.style.height = size + 'px'; ctx.canvas.style.position = ctx2.canvas.style.position = "absolute"; ctx.canvas.style.imageRendering = "pixelated"; const d = cfg.fullSizeCircle ? pixels : pixels - 1; const r = d / 2; const center = pixels / 2; const scale = size / pixels; div.value = drawCircle(pixels, ctx); function drawCircle(pixels, ctx) { let d = cfg.fullSizeCircle ? pixels : pixels - 1; let r = d / 2; let x = -r; let y = (r % 1 == 0) ? 0 : 0.5; // non-integer radius, move y half down if (cfg.fullSizeCircle) y -= 0.5, x += 0.5; let img = ctx.createImageData(pixels, pixels); let exy = error(x+1,y+1,r); let steps = []; let i = 0; do { // draw current pixels let cx = r, cy = r; if (cfg.fullSizeCircle) cx = cy -= 0.5; drawPixel(cx + x, cy + y, img); // quadrant 3 drawPixel(cx - x, cy - y, img); // quadrant 1 drawPixel(cx - y, cy + x, img); // quadrant 2 drawPixel(cx + y, cy - x, img); // quadrant 4 // get error values for each possible next step let e = error(x , y , r); let ex = error(x+1, y , r); let ey = error(x , y+1, r); let exy = error(x+1, y+1, r); steps.push({ x, y, e, ex, ey, exy }); // choose option with smallest error // long, clear version if (Math.abs(exy) < Math.abs(ex) && Math.abs(exy) < Math.abs(ey)) x++, y++; else if (Math.abs(ex) < Math.abs(exy) && Math.abs(ex) < Math.abs(ey)) x++; else if (Math.abs(ey) < Math.abs(exy) && Math.abs(ey) < Math.abs(ex)) { y++; // spurious pixel removal (radius 4, 7.5, 11...). Move to the right now if next move will be right. if (cfg.spuriousPixel && Math.abs(error(x+1,y+1,r)) > Math.abs(error(x+1,y,r)) && Math.abs(error(x+1,y,r)) < Math.abs(error(x,y+1,r))) x++; } // can be simplified because ex <= exy <= ey (seems to work, don't fully understand) //let exyOld = exy; //if (exyOld + ex < 0) y++, exy += 2*y+1; // if abs(exy) < abs(ex), i.e. if not going right, at least go up //if (exyOld + ey > 0) x++, exy += 2*x+1; // if abs(exy) < abs(ey), i.e. if not going up, at least go right // final simplification //let exyOld = exy; //if (exyOld <= y) y++, exy += 2*y+1; //if (exyOld > x || (cfg.spuriousPixel && exy > y)) x++, exy += 2*x+1; } while(x < 0) ctx.putImageData(img, 0, 0); return steps; function error (x, y, r) { return x*x + y*y - r*r; } function drawPixel(x, y, img) { const idx = (y*pixels+x)*4; console.log(idx); img.data[idx] = 128; img.data[idx+1] = 128; img.data[idx+2] = 128; img.data[idx+3] = 255; } } if (cfg.showAACircle) { ctx.beginPath(); ctx.arc(center,center,r,0,2*Math.PI); ctx.strokeStyle = "#f008"; ctx.stroke(); } if (cfg.showGrid) { ctx2.beginPath() for (let i = 0; i <= pixels; i+=1) { ctx2.moveTo(scale*i, 0); ctx2.lineTo(scale*i, size); ctx2.moveTo(0, scale*i); ctx2.lineTo(size, scale*i); } ctx2.strokeStyle = '#ccc'; ctx2.stroke(); } if (cfg.showCircle) { ctx2.beginPath(); ctx2.arc(center*scale,center*scale,r*scale,0,2*Math.PI); ctx2.strokeStyle = '#333'; ctx2.stroke(); } return div; }4a:T5b6,md` ## Explanation Below is the implicit function for a circle with its center in origin ${tex`(0,0)`}. Variables ${tex`x`} and ${tex`y`} are coordinates and ${tex`r`} is the circle radius. You might recognize Pythagoras' theorem in it. ${tex`0 = x^2 + y^2 - r^2`}
We can use this as an error function, to find out how close a coordinate is to the circle: ${tex`e = x^2 + y^2 - r^2`}
For a point (x,y) on the circle, e will be 0. For points outside the circle, e will be > 0, for points inside, e will be < 0. We cut up our circle in four quadrants. We only have to calculate one quadrant and can draw the rest using the symmetry the circle. To start drawing, we choose a pixel we're sure is on the circle. This algorithm supports circles with integer diameters. We'll choose the quadrant where each pixel drawn is a step forward on either the x or y axis or both. In the case of the web, that's quadrant 3, as the y-axis increments downwards. \`\`\` 0 1 2 +--------- x 0| 1| 2| y \`\`\` We'll start with the point (-r, 0). If the radius is a integer, this is coordinates to the first pixel. If the radius is not an integer (i.e. an odd diameter), we'll incrase the y coordinate by 0.5. For size=8, d=7, this gives the starting point (-3.5,0.5) and for d=6 it gives (-3,0). Since we translate the circle by the radius to fit it in the canvas viewport, we'll end up with integer pixel coordinates: (-3.5 + 3.5, 0.5 + 3.5) = (0,4). `4b:[] 29:{"id":"67d20e0f4d717530","slug":null,"title":"Pixelated circle","thumbnail":"f44dee3d2c90eab47177044118d3290454880493266691848097c20dee5b95d0","access_level":"public","create_time":"$D2023-09-28T17:43:07.051Z","update_time":"$D2023-09-28T17:44:52.684Z","view_time":null,"first_public_time":"$D2023-09-28T17:43:07.051Z","has_unpublished_edits":null,"fork":{"id":"113738275b9cf1c3","slug":"pixelated-circle","title":"Pixelated circle","owner":{"id":"c3958e18dab4ac29","login":"jheeffer","name":"Jasper"}},"stars":0,"starred":false,"owner":{"type":"team","id":"cbc0cae7b25c9697","login":"change-is-coming-gramsavers","name":"Change Is Coming (Gramsavers)","avatar_url":"https://avatars-next.observableusercontent.com/39694508aa75f4cf4f00ed47a916a67d2f4ccd4ea9308f5f87bf1edcc558b65d","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":552,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"2fe1f24d68dfec17","login":"change-is-coming-gramsavers","name":"Change Is Coming (Gramsavers)","avatar_url":"https://avatars-next.observableusercontent.com/39694508aa75f4cf4f00ed47a916a67d2f4ccd4ea9308f5f87bf1edcc558b65d","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"2fe1f24d68dfec17","login":"change-is-coming-gramsavers","name":"Change Is Coming (Gramsavers)","avatar_url":"https://avatars-next.observableusercontent.com/39694508aa75f4cf4f00ed47a916a67d2f4ccd4ea9308f5f87bf1edcc558b65d","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Pixelated circle","cells":[{"id":0,"value":"md`# Pixelated circle`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":427,"value":"md`Draws a pixelated circle where raster \\`size\\` is given and circle diameter is \\`size - 1\\`. Context2D drawing API only draws anti-aliased paths. For a pixelated path you need to use the lower level ImageData API to draw individual pixels.\n\nEven raster sizes (2, 4, 6, ...) do not have a mid-point and thus can't be perfectly centered on integer coordinates (e.g. from click). You could draw with 0.5px offset, disallow even sizes or make diameter equal raster size and go one raster size down. The latter will result in a less circular, but perfectly centerable shape.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"canvas","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"canvas","database":"$undefined"},{"id":12,"value":"viewof cfg = form(html`\n

\nRaster size
\nDiameter equals raster size
\nRemove spurious pixel
\nShow AA canvas circle
\nShow aim circle
\nShow raster
\nAlgorithm
\n Plot quadrants
\n Plot octants
\n Plot from rect
\n Brute Force\n\ndiameter: ${cfg.pixels-1}
\nradius: ${(cfg.pixels-1)/2}
\ncenter: ${(cfg.pixels)/2}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null