2b:null 2c:["$","title",null,{"children":"Drawing Circles | T.J. Jankun-Kelly | Observable"}] 31:Ta0e,viewof mid_grid = { const mid = raster_grid({size: grid_size, grid_width: ewidth, grid_height: height, mousedown: () => null}); mid.append(html`

Midpoint Circle Algorithm. Drag center to move; change radius below.

`); let svg = mid.getElementsByTagName("svg")[0]; svg.style.margin = "auto"; svg.style.display = "block"; svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "mid" + (grid_count*j+i)); svg.append("circle") .attr("class", "circle") .attr("fill", "none") .attr("stroke", "black") .attr("stroke-width", 3) .attr("cx", (ewidth + grid_size) / 2).attr("cy", height - (ewidth + grid_size) / 2) .attr("r", grid_size * 5); svg.append("rect") .attr("class", "center_pixel") .attr("width", grid_size).attr("height", grid_size) .attr("fill-opacity", 0) .attr("stroke", "black") .attr("stroke-width", 3) .attr("x", grid_size*Math.trunc((ewidth + grid_size) / 2 / grid_size)) .attr("y", grid_size*Math.trunc(((height - grid_size) / 2) / grid_size)) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "center") .attr("stroke", "black") .attr("r", 4) .style("cursor", "move") .attr("cx", (ewidth + grid_size) / 2).attr("cy", height - (ewidth + grid_size) / 2) .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); function clear() { svg.selectAll(".raster_grid").style("fill", "none"); } function dragging() { if(d3.event.x < 0 || d3.event.x > ewidth || d3.event.y < 0 || d3.event.y > height) return; if(Math.trunc(mutable center_grid[0]/grid_size) != Math.trunc(d3.event.x/grid_size) || Math.trunc(mutable center_grid[1]/grid_size) != Math.trunc(d3.event.y/grid_size)) { mutable center_grid = [grid_size * Math.trunc(d3.event.x/grid_size) + 0.5 * grid_size, grid_size * Math.trunc(d3.event.y/grid_size) + 0.5 * grid_size]; mutable center_grid = mutable center_grid; } } function update() { mutable center = [Math.round((mutable center_grid[0]) / grid_size - 0.5), Math.round(grid_count - (mutable center_grid[1]) / grid_size - 0.5)]; } return mid; }32:T53a,md`Drawing circles on a raster display can take approaches similar to [line drawing](https://observablehq.com/@infowantstobeseen/drawing-lines "Drawing Lines"): By using an explicit form or by using an implicit form of the cricle equation. The former suffers from having to correct for range issues (as each point generates two, not one, point) and potential floating point inaccuracies; the latters address these issues in trade for some implementation complexity. While neither are particularly suited to current graphics hardware, they are interesting from a historical perspective. ## Explicit: ${tex`y=y_c\pm\sqrt{r^2-\left(x-x_c\right)^2}`} When we solve for one of our two variables directly, we run into the fact that it is a multi-valued function, and thus must be evaluated twice: Once for the positive square root and the other for the negative. This is more annoying than problematic and can be easily implemented. More an issue is the accumulation of floating point error, which cannot be avoided and is exacerbated by the square root calculation. Finally, unlike the Digital Difference Analyzer used for lines, we do not have a constant passive axis update value per driving axis update as the derivative of of the circle is linear, not constant. We can calculate the passive axis directly, but that is not without issue:`33:Ta36,viewof gappy_grid = { const gappy = raster_grid({size: grid_size, grid_width: ewidth, grid_height: height, mousedown: () => null}); gappy.append(html`

Uncorrected Explicit Circle Algorithm. Note the increasing gaps as the tangent approaches vertical.

`); let svg = gappy.getElementsByTagName("svg")[0]; svg.style.margin = "auto"; svg.style.display = "block"; svg = d3.select(svg); svg.selectAll(".raster_grid") .style("transition", "fill .4s ease") .style("fill", "none") .attr("id", ([i,j]) => "gappy" + (grid_count*j+i)); svg.append("circle") .attr("class", "circle") .attr("fill", "none") .attr("stroke", "black") .attr("cx", (ewidth + grid_size) / 2).attr("cy", height - (ewidth + grid_size) / 2) .attr("r", grid_size * 5) .attr("stroke-width", 3); svg.append("rect") .attr("class", "center_pixel") .attr("width", grid_size).attr("height", grid_size) .attr("fill", "none") .attr("stroke", "black") .attr("stroke-width", 3) .attr("x", grid_size*Math.trunc((ewidth + grid_size) / 2 / grid_size)) .attr("y", grid_size*Math.trunc(((height - grid_size) / 2) / grid_size)) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); svg.append("circle") .attr("class", "center") .attr("stroke", "black") .attr("r", 4) .attr("cx", (ewidth + grid_size) / 2).attr("cy", height - (ewidth + grid_size) / 2) .style("cursor", "move") .call(d3.drag() .on("start", clear) .on("drag", dragging) .on("end", update)); function clear() { svg.selectAll(".raster_grid").style("fill", "none"); } function dragging() { if(d3.event.x < 0 || d3.event.x > ewidth || d3.event.y < 0 || d3.event.y > height) return; if(Math.trunc(mutable center_grid[0]/grid_size) != Math.trunc(d3.event.x/grid_size) || Math.trunc(mutable center_grid[1]/grid_size) != Math.trunc(d3.event.y/grid_size)) { mutable center_grid = [grid_size * Math.trunc(d3.event.x/grid_size) + 0.5 * grid_size, grid_size * Math.trunc(d3.event.y/grid_size) + 0.5 * grid_size]; mutable center_grid = mutable center_grid; } } function update() { mutable center = [Math.round((mutable center_grid[0]) / grid_size - 0.5), Math.round(grid_count - (mutable center_grid[1]) / grid_size - 0.5)]; } return gappy; }34:T95e,{ let fig = html`

Click octant to see midpoint decision. Pixel is last plotted; pixels are the two candidates.

` let clicked = () => { let [x,y] = d3.mouse(d3.event.target).map(i=>(i<0?0:i>160?160:i)); mutable octant = ((Math.floor(Math.atan2(x-80,80-y)*4/Math.PI))%8+8)%8; } d3.select(fig).select("svg").on("click", clicked); const above_below = raster_grid({numberH: 2, grid_width: 160, grid_height: 160, mousedown: () => null}); d3.select(above_below).style("display", "inline"); d3.select(above_below).select("div").style("display", "inline"); let svg = d3.select(above_below).select("svg"); svg.style("display", "inline"); svg.selectAll(".raster_grid").attr("id", ([i,j]) => "above_below" + (2*j+i)); svg.append("path") .attr("class", "inner_circ") .attr("stroke", "black") .attr("fill", "none") .attr("stroke-dasharray", "6 3"); svg.append("path") .attr("class", "outer_circ") .attr("stroke", "black") .attr("fill", "none") .attr("stroke-dasharray", "6 3"); svg.append("circle") .attr("class", "midpoint") .attr("stroke", "black") .attr("fill", "none") .attr("r", 4); svg.append("text") .attr("class", "midpoint_text") .text("M"); fig.querySelectorAll("div")[0].appendChild(above_below); mutable octant = mutable octant; return fig; }35:T914,md`To be concise, we will only consider the octant ${tex`\frac{\pi}{2} \leq \theta \leq \frac{\pi}{4}`} starting at ${tex`\left(0,r\right)`} and ending at ${tex`\left(\left\lceil\frac{r}{\sqrt{2}}\right\rceil, \left\lceil\frac{r}{\sqrt{2}}\right\rceil\right)`} by increasing ${tex`i`} as our driving axis; other octants swap the role of ${tex`i`} and ${tex`j`} and change direction as appropriate, but we always go from a horizontal/vertical extreme and work towards the diagonal. In this octact, the passive access decreases or stays the same. We also ignore the center of the circle, using the origin instead; the points can be translated to the center as needed. Once again, we begin with the decision variable ${tex`d`} at midpoint ${tex`M=\left(i+1, j-\frac{1}{2}\right)`}: ${tex.block`d=f(M(i,j))=\left(i+1\right)^2+\left(j-\frac{1}{2}\right)^2-r^2`} If ${tex`d\ge 0`}, the passive axis remains unchanged and the new decision value is ${tex`f(M(i+1,j))`}; the incremental update is then: ${tex.block`\begin{aligned} \Delta d&=f(M(i+1,j))-f(M(i,j))\\ &=\left(i+2\right)^2+\left(j-\frac{1}{2}\right)^2-r^2-f(M(i,j))\\ &=2i+3+\left(i+1\right)^2+\left(j-\frac{1}{2}\right)^2-r^2-f(M(i,j))\\ &=2i+3=2\left(i+1\right)+1 \end{aligned}`} Similarly, if ${tex`d< 0`}, the passive axis decreases and the new decision value is ${tex`f(M(i+1,j-1))`}; the incremental update is then: ${tex.block`\begin{aligned} \Delta d&=f(M(i+1,j-1))-f(M(i,j))\\ &=\left(i+2\right)^2+\left(j-\frac{3}{2}\right)^2-r^2-f(M(i,j))\\ &=2i-2j+5+\left(i+1\right)^2+\left(j-\frac{1}{2}\right)^2-r^2-f(M(i,j))\\ &=2i-2j+5=2\left(i+1\right)-2\left(j-1\right)+1 \end{aligned}`} Thus we can use the old ${tex`i,j`} values or the updated ones when updating the decision values. All we need now is the initial decision variable: ${tex.block`\begin{aligned} d&=f(M(0,r))\\ &=\left(1\right)^2+\left(r-\frac{1}{2}\right)^2-r^2\\ &=1+r^2-r+\frac{1}{4}-r^2\\ &=\frac{5}{4}-r \end{aligned}`} We can perform a bit of mathematicaly chicanery here, noting that we can start the decision variable at ${tex`1-r`} to integerize the algorithm as none of the update factors change ${tex`d`} by a fractional value, and thus the ignored error will not affect the result. `36:T452,function midpoint_circle([xc, yc], r) { const pixel = (x,y) => [x,y].map(Math.round); // Initial condition let [ic, jc] = pixel(xc, yc); r = Math.round(r); let [i,j] = [0, r]; // Find the error let d = 1 - r; // Rasterize by octant; start w/ four cardinal points const pixels = [pixel(ic, jc + r), pixel(ic, jc - r), pixel(ic + r, jc), pixel(ic - r, jc)]; while(i < j) { // Update midpoint/error term if(d >= 0) { j -= 1; d -= 2 * j; } i += 1; d += 2 * i + 1; pixels.splice(pixels.length, 0, ...[pixel(ic + i, jc + j), pixel(ic + i, jc - j), pixel(ic - i, jc + j), pixel(ic - i, jc - j), pixel(ic + j, jc + i), pixel(ic + j, jc - i), pixel(ic - j, jc + i), pixel(ic - j, jc - i)]); } return pixels; }37:T75b,md`### Bresenham Circle Algorithm Like the line algorithm, there is a Bresenham version for circles. It measures the difference in error of the pixel centers for the above and below pixels (for local version of above and below) instead of the error with respect to the midpoint. The algorithm thus has slightly different decision variable update terms, though they are still proportional to the current pixel location. There is no major difference in pixels for circles; however, [the Bresenham approach has more error for ellipses](https://ieeexplore.ieee.org/abstract/document/4055918/ "Van Aken: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter"). n.b. [The "Midpoint Algorithm" description on Wikipedia](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm "Wikipedia: Midpoint circle algorithm") is actually a discussion of Bresenham's. There is general confusion on the Internet in general, so a purpoted description may not match the title. ## Summary The Midpoint Circle Algorithm is ideal if you are drawing pixel by pixel sequentially, but is not well suited to modern parallel GPU hardware. In practice, a signed distance field rendering in the fragment shader or a control polygon that instantiates the circle in a tesselation shader are better choices, with the added benefit of easier interpolation of circle attributes such as color. But the Midpoint Circle Algorithm will work in a pinch for serial plotters or other such devices. ## Appendix: Implementation The implementations are exactly as specified in these notes. Some implementations appear not to have Midpoint updates that depend on ${tex`i/j`}, but they use repeated adds of a temporary, an optimization from [Van Aken](https://ieeexplore.ieee.org/abstract/document/4055918/ "Van Aken: Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter"), as best I can tell. ` 38:T96f,{ const decisions = [{'M': [120, 80], 'set': 2, 'lower': 1, 'upper': 3, 'circ': [0, 160]}, {'M': [80, 40], 'set': 1, 'lower': 2, 'upper': 3, 'circ': [0, 160]}, {'M': [80, 120], 'set': 3, 'lower': 0, 'upper': 1, 'circ': [0, 0]}, {'M': [120, 80], 'set': 0, 'lower': 1, 'upper': 3, 'circ': [0, 0]}, {'M': [40, 80], 'set': 1, 'lower': 0, 'upper': 2, 'circ': [160, 0]}, {'M': [80, 120], 'set': 2, 'lower': 0, 'upper': 1, 'circ': [160, 0]}, {'M': [80, 40], 'set': 0, 'lower': 2, 'upper': 3, 'circ': [160, 160]}, {'M': [40, 80], 'set': 3, 'lower': 2, 'upper': 0, 'circ': [160, 160]}]; const decision_info = decisions[mutable octant]; d3.select(".midpoint").attr("cx", decision_info.M[0]).attr("cy", decision_info.M[1]); d3.select(".midpoint_text").attr("x", decision_info.M[0] + 4).attr("y", decision_info.M[1] - 4); d3.select("#above_below0").attr("fill", decision_info.lower == 0 || decision_info.upper == 0 ? "lightsteelblue" : decision_info.set == 0 ? "steelblue" : "none"); d3.select("#above_below1").attr("fill", decision_info.lower == 1 || decision_info.upper == 1 ? "lightsteelblue" : decision_info.set == 1 ? "steelblue" : "none"); d3.select("#above_below2").attr("fill", decision_info.lower == 2 || decision_info.upper == 2 ? "lightsteelblue" : decision_info.set == 2 ? "steelblue" : "none"); d3.select("#above_below3").attr("fill", decision_info.lower == 3 || decision_info.upper == 3 ? "lightsteelblue" : decision_info.set == 3 ? "steelblue" : "none"); d3.select(".pie") .attr("transform", "translate(80, 80)") .attr("d", d3.arc().innerRadius(0).outerRadius(80).startAngle(octant * Math.PI / 4).endAngle((octant + 1) * Math.PI / 4)()); d3.select(".inner_circ") .attr("transform", "translate(" + decision_info.circ.join() + ")") .attr("d", d3.arc().innerRadius(0).outerRadius(160).startAngle(0).endAngle(2*Math.PI)()); d3.select(".outer_circ") .attr("transform", "translate(" + decision_info.circ.join() + ")") .attr("d", d3.arc().innerRadius(0).outerRadius(120).startAngle(0).endAngle(2*Math.PI)()); return md`Update the decision figures` }39:[] 2f:{"id":"16794eaf76b62354","slug":"drawing-circles","title":"Drawing Circles","thumbnail":"2a1735e4c9f1acd5e214bd52b2483a81671dc1dcccbab10575ceb99ccf92b12d","access_level":"public","create_time":"$D2019-10-01T20:49:19.072Z","update_time":"$D2020-08-29T15:49:11.289Z","view_time":null,"first_public_time":"$D2019-10-03T14:47:28.670Z","fork":false,"stars":10,"starred":false,"owner":{"type":"team","id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":"starter_2024"},"version":417,"publish_version":417,"role":null,"authored":false,"authors":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null}],"members":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":4,"collection":{"id":"fa97e7eb1e9d2163","slug":"computer-graphics","title":"Computer Graphics","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"title":"Drawing Circles","cells":[{"id":0,"value":"md`# Drawing Circles\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":94,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":83,"value":"viewof radius = slider({\n min: 1, \n max: 10, \n step: 1, \n value: 5, \n title: \"Radius\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":33,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"function gappy_circle([xc, yc], r)\n{\n const pixel = (x,y) => [x,y].map(Math.round);\n \n const pixels = [pixel(xc, yc+r), pixel(xc, yc-r)];\n for(let i = 1; i <= r; ++i)\n {\n // Four pixels: [xc+i, y+sqrt], [xc+i, y-sqrt], and the xc-i versions of same\n let sqrt_disc = Math.sqrt(r**2 - i**2);\n pixels.splice(pixels.length, 0, ...[pixel(xc+i, yc+sqrt_disc), \n pixel(xc+i, yc-sqrt_disc), \n pixel(xc-i, yc+sqrt_disc), \n pixel(xc-i, yc-sqrt_disc)]);\n }\n return pixels;\n}\n ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":74,"value":"md`As the circle's tanget approaches vertical (near ${tex`\\left(x_c\\pm r, y_c\\right)`}), more columnar pixels are needed—one per pixel is insuffient, unlike lines. These gaps occur in the range ${tex`-\\frac{\\pi}{4} < \\theta < \\frac{\\pi}{4}`} where ${tex`\\theta`} is the polar angle measured from ${tex`\\mathbf{\\hat{i}}`} (the first and last octants of the circle). Effectively, *the driving and passive axes swap* (or we change directions only those axes) as we change octants. While we could fix the above algorithm by rendering eight pixels per pass, mirroring for each octant, we can instead take an approach that removes the need for the the repeated discriminant calculation entirely.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":125,"value":"md`## Implicit: ${tex`\\left(x-x_c\\right)^2 + \\left(y-y_c\\right)^2 - r^2 = 0`} \n\nLike [the Midpoint algorithm for lines](https://observablehq.com/@infowantstobeseen/drawing-lines \"Drawing Lines\"), the pertinent question we need to ask while marching along our driving axis is whether the passive axis value changes are not. As noted above, we do not have a fixed driving axis; instead we have eight cases to consider: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":138,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":317,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":101,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":35,"value":"import {raster_grid} from \"@infowantstobeseen/raster-grid\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":79,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":38,"value":"d3 = require(\"d3-selection@1.4\", \"d3-drag@1.2\", \"d3-shape\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":41,"value":"ewidth = Math.min(width, 400)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":44,"value":"height = ewidth","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":47,"value":"grid_count = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":50,"value":"grid_size = Math.min(ewidth, height) / grid_count","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":53,"value":"mutable center = [grid_count / 2, grid_count / 2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":55,"value":"mutable center_grid = [ (ewidth + grid_size) / 2, (height - grid_size) / 2]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":204,"value":"mutable octant = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":58,"value":"{\n for(let grid of [viewof mid_grid, viewof gappy_grid])\n d3.select(grid).selectAll(\".raster_grid\").style(\"fill\",\"none\");\n \n for(const pt of gappy_circle(center, radius).filter(([i,j]) => (i >= 0 && j >= 0 && i < grid_size && j < grid_size)))\n {\n const rect = d3.select(viewof gappy_grid).select(\"rect#gappy\" + (grid_count * pt[1] + pt[0]));\n rect.style(\"fill\", \"coral\"); \n }\n for(const pt of midpoint_circle(center, radius).filter(([i,j]) => (i >= 0 && j >= 0 && i < grid_size && j < grid_size)))\n {\n const rect = d3.select(viewof mid_grid).select(\"rect#mid\" + (grid_count * pt[1] + pt[0]));\n rect.style(\"fill\", \"lightsteelblue\"); \n }\n \n return md`Update the points`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":60,"value":"{\n d3.selectAll(\".circle\")\n .attr(\"cx\", center_grid[0]).attr(\"cy\", center_grid[1])\n .attr(\"r\", radius * grid_size);\n d3.selectAll(\".center\")\n .attr(\"cx\", center_grid[0]).attr(\"cy\", center_grid[1]);\n d3.selectAll(\".center_pixel\")\n .attr(\"x\", grid_size*Math.trunc(center_grid[0]/grid_size))\n .attr(\"y\", grid_size*Math.trunc(center_grid[1]/grid_size));\n\n return md`Update the centers`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":208,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 30:"$2f:body"