31:T7e0,{ const context = DOM.context2d(width, height); const canvasWidth = context.canvas.width; const canvasHeight = context.canvas.height; // ---------------------------------------------------------------------------- // Step 1: Build polygons from curves and lines let start = Date.now(); const ctx = newNumericContext(); const curve = drawCurves ? d3shape.curveCatmullRomClosed(ctx) : d3shape.curveLinearClosed(ctx); for (const line of selectedLines) { curve.lineStart(); for (const [x, y] of line) curve.point(x, y); curve.lineEnd(); } ctx.closePath(); // console.log(ctx.rings); const stats = mutable ringsStats = []; const rings = ctx.rings.map(ring => { const before = ring.length; ring = simplifyRing(ring, tolerance); const after = ring.length; stats.push({ before, after }); return ring; }); // ---------------------------------------------------------------------------- // Step 2: Draw and fill polygons const w = context.canvas.width; const h = context.canvas.height; // const input = context.getImageData(0, 0, w, h); const output = context.createImageData(w, h); let color; const geom = newGeometry((x, y) => { const idx = (y * w + x) * 4; output.data[idx + 0] = color[0]; output.data[idx + 1] = color[1]; output.data[idx + 2] = color[2]; output.data[idx + 3] = color[3]; }); for (let ring of rings) { color = [0, 0, 255, 127]; // console.log('???', ring); geom.fillPolygon(ring); color = [255, 0, 0, 255]; geom.plotPolyline(ring); } let stop = Date.now(); console.log('TIME:', (stop - start) + 'ms'); context.putImageData(output, 0, 0); // for (const ring of rings) { // context.beginPath(); // for (const [x, y] of ring) context.lineTo(x, y); // context.closePath(); // context.strokeStyle = 'blue'; // context.stroke(); // context.fillStyle = 'rgba(255,0,0,0.5)'; // context.fill(); // } return context.canvas; }32:T4e5, function newNumericContext(processRing=(ring)=>ring) { let prevDX, prevDY, prevX, prevY; let ring, rings = []; function setPixel(x, y) { let dx, dy; if (!ring) { rings.push(ring = []); } else { if (x === prevX && y === prevY) return ; dx = x - prevX; dy = y - prevY; if (prevDX !== dx || prevDY !== dy) { ring.push([prevX, prevY]); } } prevX = x; prevY = y; prevDX = dx; prevDY = dy; } const geom = newGeometry(setPixel); function closeRing() { if (ring) { ring.push([prevX, prevY]); if (processRing) { ring = processRing(rings.pop()); if (ring) rings.push(ring); } prevDX = prevDY = undefined; ring = null; } } return { rings, moveTo : (x, y) => { closeRing(); setPixel(x, y); }, lineTo : (x, y) => geom.plotLine(prevX, prevY, x, y), bezierCurveTo : (x0, y0, x1, y1, x2, y2) => geom.plotCubicBezier(prevX, prevY, x0, y0, x1, y1, x2, y2), beginPath : () => closeRing(), closePath : () => { if (ring && ring[0]) { geom.plotLine(prevX, prevY, ring[0][0], ring[0][1]); } closeRing(); }, stroke : () => {} } }33:T2b23,function newGeometry(setPixel) { // http://members.chello.at/~easyfilter/bresenham.js function assert(a) { if (!a) throw new Error("Assertion failed in bresenham.js "+a); return a; } function plotLine(x0, y0, x1, y1) { var dx = Math.abs(x1-x0), sx = x0= dy) { err += dy; x0 += sx; } /* x step */ if (e2 <= dx) { err += dx; y0 += sy; } /* y step */ } } function plotQuadBezierSeg(x0, y0, x1, y1, x2, y2) { /* plot a limited quadratic Bezier segment */ var sx = x2-x1, sy = y2-y1; var xx = x0-x1, yy = y0-y1, xy; /* relative values for checks */ var dx, dy, err, cur = xx*sy-yy*sx; /* curvature */ assert(xx*sx <= 0 && yy*sy <= 0); /* sign of gradient must not change */ if (sx*sx+sy*sy > xx*xx+yy*yy) { /* begin with shorter part */ x2 = x0; x0 = sx+x1; y2 = y0; y0 = sy+y1; cur = -cur; /* swap P0 P2 */ } if (cur != 0) { /* no straight line */ xx += sx; xx *= sx = x0 < x2 ? 1 : -1; /* x step direction */ yy += sy; yy *= sy = y0 < y2 ? 1 : -1; /* y step direction */ xy = 2*xx*yy; xx *= xx; yy *= yy; /* differences 2nd degree */ if (cur*sx*sy < 0) { /* negated curvature? */ xx = -xx; yy = -yy; xy = -xy; cur = -cur; } dx = 4.0*sy*cur*(x1-x0)+xx-xy; /* differences 1st degree */ dy = 4.0*sx*cur*(y0-y1)+yy-xy; xx += xx; yy += yy; err = dx+dy+xy; /* error 1st step */ do { setPixel(x0,y0); /* plot curve */ if (x0 == x2 && y0 == y2) return; /* last pixel -> curve finished */ y1 = 2*err < dx; /* save value for test of y step */ if (2*err > dy) { x0 += sx; dx -= xy; err += dy += yy; } /* x step */ if ( y1 ) { y0 += sy; dy -= xy; err += dx += xx; } /* y step */ } while (dy < 0 && dx > 0); /* gradient negates -> algorithm fails */ } plotLine(x0,y0, x2,y2); /* plot remaining part to end */ } function plotCubicBezierSeg(x0, y0, x1, y1, x2, y2, x3, y3) { /* plot limited cubic Bezier segment */ var f, fx, fy, leg = 1; var sx = x0 < x3 ? 1 : -1, sy = y0 < y3 ? 1 : -1; /* step direction */ var xc = -Math.abs(x0+x1-x2-x3), xa = xc-4*sx*(x1-x2), xb = sx*(x0-x1-x2+x3); var yc = -Math.abs(y0+y1-y2-y3), ya = yc-4*sy*(y1-y2), yb = sy*(y0-y1-y2+y3); var ab, ac, bc, cb, xx, xy, yy, dx, dy, ex, pxy, EP = 0.01; /* check for curve restrains */ /* slope P0-P1 == P2-P3 and (P0-P3 == P1-P2 or no slope change) */ assert((x1-x0)*(x2-x3) < EP && ((x3-x0)*(x1-x2) < EP || xb*xb < xa*xc+EP)); assert((y1-y0)*(y2-y3) < EP && ((y3-y0)*(y1-y2) < EP || yb*yb < ya*yc+EP)); if (xa == 0 && ya == 0) /* quadratic Bezier */ return plotQuadBezierSeg(x0,y0, (3*x1-x0)>>1,(3*y1-y0)>>1, x3,y3); x1 = (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)+1; /* line lengths */ x2 = (x2-x3)*(x2-x3)+(y2-y3)*(y2-y3)+1; do { /* loop over both ends */ ab = xa*yb-xb*ya; ac = xa*yc-xc*ya; bc = xb*yc-xc*yb; ex = ab*(ab+ac-3*bc)+ac*ac; /* P0 part of self-intersection loop? */ f = ex > 0 ? 1 : Math.floor(Math.sqrt(1+1024/x1)); /* calc resolution */ ab *= f; ac *= f; bc *= f; ex *= f*f; /* increase resolution */ xy = 9*(ab+ac+bc)/8; cb = 8*(xa-ya); /* init differences of 1st degree */ dx = 27*(8*ab*(yb*yb-ya*yc)+ex*(ya+2*yb+yc))/64-ya*ya*(xy-ya); dy = 27*(8*ab*(xb*xb-xa*xc)-ex*(xa+2*xb+xc))/64-xa*xa*(xy+xa); /* init differences of 2nd degree */ xx = 3*(3*ab*(3*yb*yb-ya*ya-2*ya*yc)-ya*(3*ac*(ya+yb)+ya*cb))/4; yy = 3*(3*ab*(3*xb*xb-xa*xa-2*xa*xc)-xa*(3*ac*(xa+xb)+xa*cb))/4; xy = xa*ya*(6*ab+6*ac-3*bc+cb); ac = ya*ya; cb = xa*xa; xy = 3*(xy+9*f*(cb*yb*yc-xb*xc*ac)-18*xb*yb*ab)/8; if (ex < 0) { /* negate values if inside self-intersection loop */ dx = -dx; dy = -dy; xx = -xx; yy = -yy; xy = -xy; ac = -ac; cb = -cb; } /* init differences of 3rd degree */ ab = 6*ya*ac; ac = -6*xa*ac; bc = 6*ya*cb; cb = -6*xa*cb; dx += xy; ex = dx+dy; dy += xy; /* error of 1st step */ exit: for (pxy = 0, fx = fy = f; x0 != x3 && y0 != y3; ) { setPixel(x0,y0); /* plot curve */ do { /* move sub-steps of one pixel */ if (pxy == 0) if (dx > xy || dy < xy) break exit; /* confusing */ if (pxy == 1) if (dx > 0 || dy < 0) break exit; /* values */ y1 = 2*ex-dy; /* save value for test of y step */ if (2*ex >= dx) { /* x sub-step */ fx--; ex += dx += xx; dy += xy += ac; yy += bc; xx += ab; } else if (y1 > 0) break exit; if (y1 <= 0) { /* y sub-step */ fy--; ex += dy += yy; dx += xy += bc; xx += ac; yy += cb; } } while (fx > 0 && fy > 0); /* pixel complete? */ if (2*fx <= f) { x0 += sx; fx += f; } /* x step */ if (2*fy <= f) { y0 += sy; fy += f; } /* y step */ if (pxy == 0 && dx < 0 && dy > 0) pxy = 1; /* pixel ahead valid */ } xx = x0; x0 = x3; x3 = xx; sx = -sx; xb = -xb; /* swap legs */ yy = y0; y0 = y3; y3 = yy; sy = -sy; yb = -yb; x1 = x2; } while (leg--); /* try other end */ plotLine(x0,y0, x3,y3); /* remaining part in case of cusp or crunode */ } function plotCubicBezier(x0, y0, x1, y1, x2, y2, x3, y3) { /* plot any cubic Bezier curve */ var n = 0, i = 0; var xc = x0+x1-x2-x3, xa = xc-4*(x1-x2); var xb = x0-x1-x2+x3, xd = xb+4*(x1+x2); var yc = y0+y1-y2-y3, ya = yc-4*(y1-y2); var yb = y0-y1-y2+y3, yd = yb+4*(y1+y2); var fx0 = x0, fx1, fx2, fx3, fy0 = y0, fy1, fy2, fy3; var t1 = xb*xb-xa*xc, t2, t = new Array(5); /* sub-divide curve at gradient sign changes */ if (xa == 0) { /* horizontal */ if (Math.abs(xc) < 2*Math.abs(xb)) t[n++] = xc/(2.0*xb); /* one change */ } else if (t1 > 0.0) { /* two changes */ t2 = Math.sqrt(t1); t1 = (xb-t2)/xa; if (Math.abs(t1) < 1.0) t[n++] = t1; t1 = (xb+t2)/xa; if (Math.abs(t1) < 1.0) t[n++] = t1; } t1 = yb*yb-ya*yc; if (ya == 0) { /* vertical */ if (Math.abs(yc) < 2*Math.abs(yb)) t[n++] = yc/(2.0*yb); /* one change */ } else if (t1 > 0.0) { /* two changes */ t2 = Math.sqrt(t1); t1 = (yb-t2)/ya; if (Math.abs(t1) < 1.0) t[n++] = t1; t1 = (yb+t2)/ya; if (Math.abs(t1) < 1.0) t[n++] = t1; } for (i = 1; i < n; i++) /* bubble sort of 4 points */ if ((t1 = t[i-1]) > t[i]) { t[i-1] = t[i]; t[i] = t1; i = 0; } t1 = -1.0; t[n] = 1.0; /* begin / end point */ for (i = 0; i <= n; i++) { /* plot each segment separately */ t2 = t[i]; /* sub-divide at t[i-1], t[i] */ fx1 = (t1*(t1*xb-2*xc)-t2*(t1*(t1*xa-2*xb)+xc)+xd)/8-fx0; fy1 = (t1*(t1*yb-2*yc)-t2*(t1*(t1*ya-2*yb)+yc)+yd)/8-fy0; fx2 = (t2*(t2*xb-2*xc)-t1*(t2*(t2*xa-2*xb)+xc)+xd)/8-fx0; fy2 = (t2*(t2*yb-2*yc)-t1*(t2*(t2*ya-2*yb)+yc)+yd)/8-fy0; fx0 -= fx3 = (t2*(t2*(3*xb-t2*xa)-3*xc)+xd)/8; fy0 -= fy3 = (t2*(t2*(3*yb-t2*ya)-3*yc)+yd)/8; x3 = Math.floor(fx3+0.5); y3 = Math.floor(fy3+0.5); /* scale bounds */ if (fx0 != 0.0) { fx1 *= fx0 = (x0-x3)/fx0; fx2 *= fx0; } if (fy0 != 0.0) { fy1 *= fy0 = (y0-y3)/fy0; fy2 *= fy0; } if (x0 != x3 || y0 != y3) /* segment t1 - t2 */ plotCubicBezierSeg(x0,y0, x0+fx1,y0+fy1, x0+fx2,y0+fy2, x3,y3); x0 = x3; y0 = y3; fx0 = fx3; fy0 = fy3; t1 = t2; } } function plotPolyline(points) { for (let i = 1; i < points.length; i++) { const a = points[i-1]; const b = points[i]; plotLine(a[0], a[1], b[0], b[1]); } } // Copied from http://cssdeck.com/labs/scan-line-algorithm function fillPolygon(points) { // Initialization const lines = []; let minY, maxY; for (let i = 0; i < points.length; i++) { let temp = points[i][1]; if (i === 0) { minY = maxY = temp; } else { lines.push(line(points[i - 1], points[i])); if (temp < minY) minY = temp; else if (temp > maxY) maxY = temp; } } minY = Math.round(minY); maxY = Math.round(maxY); // Scan for (let y = minY; y < maxY; y++) { let intersections = []; for (var i = 0; i < lines.length; i++) { lines[i](intersections, y); } if (!intersections.length) continue; intersections.sort((a, b) => a > b ? 1 : a < b ? -1 : 0); let start = intersections.length % 2 ? 2 : 1; for (let i = start; i < intersections.length; i += 2) { for (let x = intersections[i - 1]; x < intersections[i]; x++) { setPixel(x, y); } } } function line(start, end) { const minY = Math.min(start[1], end[1]); const maxY = Math.max(start[1], end[1]); const m = (end[1] - start[1]) / (end[0] - start[0]) return (list, y) => { if (y < minY || y >= maxY) return ; let x = (y === start[1]) ? start[0] : (1 / m * (y - start[1]) + start[0]); x = Math.round(x); list.push(x); } } } return { plotLine : (...coords) => plotLine(...coords.map(Math.round)), plotCubicBezier : (...coords) => plotCubicBezier(...coords.map(Math.round)), plotPolyline : (points) => plotPolyline(points.map(([x, y]) => ([Math.round(x), Math.round(y)]))), fillPolygon : (points) => fillPolygon(points.map(([x, y]) => ([Math.round(x), Math.round(y)]))), } } 34:[] 2f:{"title":"DataCanvas","cells":[{"id":0,"value":"md`# DataCanvas\n\nThis is a basic implementation of the following canvas context methods:\n* moveTo\n* lineTo\n* bezierCurveTo\n* closePath\n* fill - fills closed paths\n* store - stroke drawn lines\n\nThis combination of methods allows to put data in matrix.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":289,"value":"viewof selectedLinesIds = checkbox({\n title : `Choose lines to draw:`,\n options : lines.map((_, idx) => ({ value : idx, label : `Line ${idx}` })),\n value : [ 0 ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":317,"value":"viewof drawCurves = checkbox({\n title : `Draw curves:`,\n options : [{ value : true, label : 'Yes' }],\n value : [ true ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":217,"value":"selectedLines=selectedLinesIds.map(idx => lines[idx]);","pinned":true,"hidden":false,"mode":"ojs"},{"id":200,"value":"viewof tolerance = {\n const min = 0;\n const max = 5;\n return slider({\n min, \n max, \n step: 0.01, \n value : 1,\n title: \"Tolerance (in pixels):\"\n })\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":305,"value":"{\n \n let avg = (ringsStats && ringsStats.length)\n ? ringsStats.reduce((v, s) => v += s.after / s.before, 0) / ringsStats.length\n : 0;\n return md`\nTolerance defines \"degree of simplification\" for resulting polylines. It means that intermediate points staying almost on the same line are removed. This approach considerably reduces the number of points and simplifies the resulting polygons.\n\nWith the the tolerance of **${tolerance}px** algorithm keeps **${(100 * avg).toFixed(2)}%** of the initial number of points.\n`\n // ${ringsStats.map(s => `\\n* ${s.before} points => ${s.after} points (${Math.round(100 * s.after / s.before)}%)`)} \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"mutable ringsStats = []","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":42,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":333,"value":" function simplifyRing(ring, tolerance=1) {\n ring = simplify(ring.map(([x, y]) => ({x, y})), tolerance)\n .map(({x, y}) => ([Math.round(x), Math.round(y)]));\n if (ring.length) {\n const first = ring[0];\n const last = ring[ring.length - 1];\n if (first[0] !== last[0] || first[1] !== last[1]) {\n ring.push(first);\n }\n }\n return ring;\n }\n","pinned":true,"hidden":false,"mode":"ojs"},{"id":113,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"height = width / 1.6;","pinned":true,"hidden":false,"mode":"ojs"},{"id":19,"value":"lines = Array.from({length: 10}, () => {\n return Array.from({length: 10}, () => {\n return [\n (Math.random() * 0.8 + 0.1) * width, \n (Math.random() * 0.8 + 0.1) * height\n ];\n });\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":9,"value":"d3shape = require(\"d3-shape\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":132,"value":"simplify=require(\"simplify-js\");","pinned":true,"hidden":false,"mode":"ojs"},{"id":198,"value":"import {radio, slider, checkbox, color} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}