Published
Edited
Sep 25, 2019
1 fork
Importers
selectedLines=selectedLinesIds.map(idx => lines[idx]);
{
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;
}
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 : () => {}
}
}
function simplifyRing(ring, tolerance=1) {
ring = simplify(ring.map(([x, y]) => ({x, y})), tolerance)
.map(({x, y}) => ([Math.round(x), Math.round(y)]));
if (ring.length) {
const first = ring[0];
const last = ring[ring.length - 1];
if (first[0] !== last[0] || first[1] !== last[1]) {
ring.push(first);
}
}
return ring;
}
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<x1 ? 1 : -1;
var dy = -Math.abs(y1-y0), sy = y0<y1 ? 1 : -1;
var err = dx+dy, e2; /* error value e_xy */
for (;;){ /* loop */
setPixel(x0,y0);
if (x0 == x1 && y0 == y1) break;
e2 = 2*err;
if (e2 >= 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)]))),
}
}
height = width / 1.6;
lines = Array.from({length: 10}, () => {
return Array.from({length: 10}, () => {
return [
(Math.random() * 0.8 + 0.1) * width,
(Math.random() * 0.8 + 0.1) * height
];
});
})
d3shape = require("d3-shape")
simplify=require("simplify-js");
import {radio, slider, checkbox, color} from "@jashkenas/inputs"
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
