31:[] 2f:{"title":"Corner cutting","cells":[{"id":0,"value":"# Corner cutting","pinned":false,"hidden":false,"mode":"md"},{"id":590,"value":"*inspired by [“A Note On Subdivision Curves”](https://www.maplesoft.com/applications/view.aspx?SID=7066&view=html) by Wieslaw Kotarski and Agnieszka Lisowska*","pinned":false,"hidden":false,"mode":"md"},{"id":208,"value":"context.canvas","pinned":false,"hidden":false,"mode":"ojs"},{"id":550,"value":"html`Corner cutting with ${tex`u=v=\\frac{i}{20}`}.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"viewof i = Inputs.range([0, 20], {label: \"i\", value: 14.5, step: 0.1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"viewof animation = Inputs.toggle({label: \"Animation\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":344,"value":"viewof history = Inputs.toggle({label: \"Show history\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":462,"value":"## The algorithm","pinned":false,"hidden":false,"mode":"md"},{"id":467,"value":"md`The corner cutting algorithm was invented by *Georges De Rham* in 1947 [1]. A polygon is refined by subdividing each segment into three parts. Depending on the ratios ${tex`(u:1-u-v:v)`}, an iterative refinement converges to a smooth limit curve.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":80,"value":"viewof u = Inputs.range([0, 1], {label: \"u\", value: 1/3})","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"viewof v = Inputs.range([0, 1], {label: \"v\", value: 1/3})","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"viewof steps = Inputs.range([0, 10], {label: \"subdivision steps\", value: 1, step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":578,"value":"viewof showPoints = Inputs.toggle({label: \"Show points\", value: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"{\n const context = DOM.context2d(width, height);\n\n context.lineEnd = \"round\";\n context.lineJoin = \"round\";\n\n const line = d3.line()\n .x(d => xScale(d.x))\n .y(d => yScale(d.y))\n .context(context);\n\n const polygon = (pts, color, strokeWidth, points) => {\n context.save();\n \n context.strokeStyle = color;\n context.lineWidth = strokeWidth;\n context.beginPath();\n line(pts);\n context.stroke()\n\n if (points) {\n context.fillStyle = color\n for (const pt of pts) {\n context.beginPath();\n context.arc(xScale(pt.x), yScale(pt.y), 3, 0, 2 * Math.PI);\n context.fill();\n }\n }\n\n context.restore();\n };\n \n polygon(controlPolygon, colors.red, 1, showPoints);\n \n let refined = controlPolygon;\n \n for (let i = 0; i < steps; i++) {\n refined = deRham(refined, u, v);\n\n if (history) {\n polygon(refined, colors.gray, 1, showPoints);\n }\n }\n\n polygon(refined, colors.black, 2, showPoints);\n \n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":505,"value":"md`By choosing ${tex`u=v=\\frac{1}{3}`} we obtain a ${tex`C^0`} and with ${tex`u=v=\\frac{1}{4}`} a ${tex`C^1`} curve.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":565,"value":"Inputs.button([\n [\"u=1/3 v=1/3\", () => setUV(1 / 3, 1 / 3)],\n [\"u=1/4 v=1/4\", () => setUV(1 / 4, 1 / 4)],\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":563,"value":"md`With other ratios, the algorithm might not converge to a smooth curve. E.g. with ${tex`u=\\frac{1}{7}, v=\\frac{6}{7}`} we obtain a simple polyline and with ${tex`u=\\frac{4}{5}, v=\\frac{2}{3}`} a fractal curve.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":113,"value":"Inputs.button([\n [\"u=1/7 v=6/7\", () => setUV(1 / 7, 6 / 7)],\n [\"u=4/5 v=2/3\", () => setUV(4 / 5, 2 / 3)],\n])","pinned":false,"hidden":false,"mode":"ojs"},{"id":496,"value":"md`*George Chaikin* reinvented the algorithm in 1974 [2] for the application in *computer aided design* (CAD). He proved that the limit curve for ${tex`u=v=\\frac{1}{4}`} is a quadratic B-Spline.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":519,"value":"## References","pinned":false,"hidden":false,"mode":"md"},{"id":508,"value":"footnote(1, `Un peu de mathématiques à propos d'une courbe plane. Georges De Rham, Elemente der Mathematik, Volume: 2, page 89-97 (1947)`, `https://eudml.org/doc/140466#:~:text=%C2%A0-,Access%20to%20full%20text,-How%20to%20cite`)","pinned":false,"hidden":false,"mode":"ojs"},{"id":514,"value":"footnote(2, `An algorithm for high-speed curve generation. George Merrill Chaikin. Computer Graphics and Image Processing, Volume 3, Issue 4 (1974)`, `https://www.sciencedirect.com/science/article/abs/pii/0146664X74900288`)","pinned":false,"hidden":false,"mode":"ojs"},{"id":406,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"controlPolygon = [{x: 0, y: 0}, {x: 0.5, y: 1}, {x: 1, y: 0}, {x: 1.5, y: 1}, {x: 2, y: 0}]","pinned":false,"hidden":false,"mode":"ojs"},{"id":42,"value":"lerp = function (a, b, t) {\n const x = t * b.x + (1 - t) * a.x;\n const y = t * b.y + (1 - t) * a.y;\n\n return {x, y};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":50,"value":"deRham = function (polygon, u, v) {\n const refined = [];\n\n for (let i = 1; i < polygon.length; i++) {\n const a = polygon[i - 1];\n const b = polygon[i];\n \n const p1 = lerp(a, b, u);\n const p2 = lerp(b, a, v);\n\n refined.push(p1, p2);\n }\n\n return refined;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":420,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":159,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"xScale = d3.scaleLinear().domain([0, 2]).range([10, width - 10])","pinned":false,"hidden":false,"mode":"ojs"},{"id":163,"value":"yScale = d3.scaleLinear().domain([1, 0]).range([10, height - 10])","pinned":false,"hidden":false,"mode":"ojs"},{"id":200,"value":"context = DOM.context2d(width, height)","pinned":false,"hidden":false,"mode":"ojs"},{"id":194,"value":"{\n const line = d3.line().x(d => xScale(d.x)).y(d => yScale(d.y)).context(context);\n \n context.clearRect(0, 0, context.canvas.width, context.canvas.height);\n \n context.fillStyle = \"rgba(255,255,255,0.2)\";\n\n let refined = controlPolygon;\n\n for (let k = 0; k < 10; k++) {\n refined = deRham(refined, i / 20, i / 20);\n \n if (history) {\n context.fillRect(0, 0, context.canvas.width, context.canvas.height);\n context.beginPath();\n line(refined);\n context.stroke();\n }\n }\n \n context.beginPath();\n line(refined);\n context.stroke();\n\n return \"draw\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":225,"value":"{\n const input = viewof i;\n\n let step = 0.1;\n \n while (animation) {\n input.value += step;\n \n if (input.value <= 0 || input.value >= 20) {\n step *= -1;\n }\n \n input.dispatchEvent(new Event(\"input\"));\n \n await Promises.delay(100);\n \n if ((viewof animation).value == false) {\n break;\n }\n\n yield \"run animation\";\n }\n\n yield \"stop animation\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":154,"value":"line = d3.line().x(d => xScale(d.x)).y(d => yScale(d.y));","pinned":false,"hidden":false,"mode":"ojs"},{"id":104,"value":"function set(input, value) {\n input.value = value;\n input.dispatchEvent(new Event(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":447,"value":"setUV = function (u, v) {\n set(viewof u, u);\n set(viewof v, v);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":601,"value":"footnote = (number, text, link) => {\n if (link === undefined) {\n return html`

${text}

`;\n } else {\n return html`

${text}

`;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"d3 = require(\"d3@7.3\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":379,"value":"import {colors} from '@oberbichler/colors'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}