28:null 29:["$","title",null,{"children":"Shape matching | Claudio Esperança | Observable"}] 2e:T42b,viewof demo1 = { reset1; let dsp = new Display(); let a = rectanglePoints([300, 300], [100, 100]); let M = rigidTransf(centerOfMass(a), Math.PI / 3, [100, 0]); let b = transformPoints(a, M); function refresh() { dsp.clear(); dsp.drawPoints(a); dsp.drawPolygon(a); dsp.drawPoints(b, { fill: null, stroke: 'blue', radius: 6 }); let c = transformPoints(a, shapeMatch(a, b)); dsp.drawPoints(c, { fill: 'red' }); dsp.drawPolygon(c, { stroke: 'red', dash: [2, 2] }); } let mouse = null; let selected = null; dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = null; for (let p of b) { if (vec2.dist(p, mouse) <= 5) { selected = p; break; } } }; dsp.canvas.onmousemove = e => { let newmouse = [e.offsetX, e.offsetY]; if (selected) { vec2.add(selected, selected, vec2.sub([], newmouse, mouse)); refresh(); } mouse = newmouse; }; dsp.canvas.onmouseup = e => { selected = null; }; refresh(); return dsp.canvas; }2f:T442,viewof demo2 = { reset2; let dsp = new Display(); let a = rectanglePoints([300, 300], [100, 100]); let b = a.slice(); function refresh() { dsp.clear(); dsp.drawPoints(a); dsp.drawPolygon(a); dsp.drawPoints(b, { fill: null, stroke: 'blue', radius: 6 }); } let mouse = null; let selected = null; let iselected = -1; dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = null; iselected = -1; b.forEach((p, i) => { if (vec2.dist(p, mouse) <= 5) { selected = p; iselected = i; return; } }); }; dsp.canvas.onmousemove = e => { let newmouse = [e.offsetX, e.offsetY]; if (selected) { vec2.add(selected, selected, vec2.sub([], newmouse, mouse)); for (let n = relaxIterations; n > 0; n--) { b = b.map((p, i) => (i == iselected ? selected : a[i])); a = transformPoints(a, shapeMatch(a, b)); } refresh(); } mouse = newmouse; }; dsp.canvas.onmouseup = e => { selected = null; }; refresh(); return dsp.canvas; }30:T7ec,viewof demo4 = { reset4; let dsp = new Display(); let a = rectanglePoints([300, 300], [100, 100]); let mouse = null; let selected = null; let nudgeDistance = 15; function refresh() { dsp.clear(); dsp.drawPoints(a); dsp.drawPolygon(a); if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); } // Find the point on polygon poly's boundary closest to p and its distance function findPivot(poly, mouse) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(mouse, p, q); let d = vec2.dist(candPivot, mouse); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); if (dist < minDist) { poly.push(pivot); for (let n = relaxIterations; n > 0 && dist < minDist; n--) { let p = pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly[last] = pivot; copy[last] = p; let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); [pivot, dist] = findPivot(poly.slice(0, last), mouse); } poly.pop(); } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }31:T90a,viewof demo5 = { reset5; let dsp = new Display(); let a = rectanglePoints([300, 300], [100, 100]); let mouse = null; let selected = null; let nudgeDistance = 5; let debug; function refresh() { dsp.clear(); dsp.drawPoints(a); dsp.drawPolygon(a); if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); //if (debug) dsp.drawPoints (debug, {fill:'red', radius:3} } // Find the point on polygon poly's boundary closest to mouse and its distance function findPivot(poly, mouse) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(mouse, p, q); let d = vec2.dist(candPivot, mouse); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { for ( let n = relaxIterations; n > 0 && (inside || dist < minDist * 0.99); n-- ) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); debug = [pivot, p]; let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }32:Ta62,viewof demo6 = { reset6; let dsp = new Display(); let a = rectanglePoints([300, 300], [100, 100]); let mouse = null; let selected = null; let nudgeDistance = 5; function refresh() { dsp.clear(); dsp.drawPoints(a); dsp.drawPolygon(a); if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); } // Projects back points outside the canvas function projectHalfspaces(poly) { for (let i = 0; i < poly.length; i++) { let p = poly[i]; for (let [a, b, c] of [ [-1, 0, 0], [1, 0, -dsp.canvas.width], [0, -1, 0], [0, 1, -dsp.canvas.height] ]) { if (a * p[0] + b * p[1] + c >= 0) p = projectPointLine(p, a, b, c); } poly[i] = p; } } // Find the point on polygon poly's boundary closest to mouse and its distance function findPivot(poly, mouse) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(mouse, p, q); let d = vec2.dist(candPivot, mouse); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { for ( let n = relaxIterations; n > 0 && (inside || dist < minDist * 0.99); n-- ) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); projectHalfspaces(copy); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; a = nudgePoly(a, mouse, nudgeDistance); refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }33:Tb62,viewof demo7 = { reset7; let dsp = new Display(); let polygons = [ rectanglePoints([200, 200], [100, 100]), regularPolygonPoints([400, 300], 50, 5), regularPolygonPoints([500, 200], 50, 3) ]; let mouse = null; let selected = null; let nudgeDistance = 20; function refresh() { dsp.clear(); for (let a of polygons) { dsp.drawPoints(a); dsp.drawPolygon(a); } if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); } // Projects back points outside the canvas function projectHalfspaces(poly) { for (let i = 0; i < poly.length; i++) { let p = poly[i]; for (let [a, b, c] of [ [-1, 0, 0], [1, 0, -dsp.canvas.width], [0, -1, 0], [0, 1, -dsp.canvas.height] ]) { if (a * p[0] + b * p[1] + c >= 0) p = projectPointLine(p, a, b, c); } poly[i] = p; } } // Find the point on polygon poly's boundary closest to mouse and its distance function findPivot(poly, mouse) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(mouse, p, q); let d = vec2.dist(candPivot, mouse); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { for ( let n = relaxIterations; n > 0 && (inside || dist < minDist * 0.99); n-- ) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); projectHalfspaces(copy); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }34:Tc6a,viewof demo7a = { reset7a; let dsp = new Display(); let polygons = [ rectanglePoints([200, 200], [100, 100]), regularPolygonPoints([400, 300], 50, 5), regularPolygonPoints([500, 200], 50, 3) ]; let mouse = null; let selected = null; let nudgeDistance = 20; let projectedPolys = []; function refresh() { dsp.clear(); for (let a of polygons) { dsp.drawPoints(a); dsp.drawPolygon(a); } if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); for (let pp of projectedPolys) { if (pp) dsp.drawPolygon(pp, { stroke: 'red', lineWidth: 2, dash: [5, 5] }); } } // Projects back points outside the canvas function projectHalfspaces(poly) { for (let i = 0; i < poly.length; i++) { let p = poly[i]; for (let [a, b, c] of [ [-1, 0, 0], [1, 0, -dsp.canvas.width], [0, -1, 0], [0, 1, -dsp.canvas.height] ]) { if (a * p[0] + b * p[1] + c >= 0) p = projectPointLine(p, a, b, c); } poly[i] = p; } } // Find the point on polygon poly's boundary closest to mouse and its distance function findPivot(poly, mouse) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(mouse, p, q); let d = vec2.dist(candPivot, mouse); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { for ( let n = relaxIterations; n > 0 && (inside || dist < minDist * 0.99); n-- ) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); projectHalfspaces(copy); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); projectedPolys = projectCollisions(polygons); refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); projectedPolys = projectCollisions(polygons); refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }35:Tfc7,viewof demo8 = { reset8; let dsp = new Display(); let polygons = [ rectanglePoints([200, 200], [100, 100]), regularPolygonPoints([400, 300], 50, 5), regularPolygonPoints([500, 200], 50, 3) ]; let mouse = null; let selected = null; let nudgeDistance = 20; function refresh() { dsp.clear(); for (let a of polygons) { dsp.drawPoints(a); dsp.drawPolygon(a); } if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); } // Projects back points outside the canvas. // Returns true if projection was performed on poly, in which case, // the vertices of poly are modified in place. function projectHalfspaces(poly) { let projected = false; for (let i = 0; i < poly.length; i++) { let p = poly[i]; for (let [a, b, c] of [ [-1, 0, 0], [1, 0, -dsp.canvas.width], [0, -1, 0], [0, 1, -dsp.canvas.height] ]) { if (a * p[0] + b * p[1] + c >= 0) { p = projectPointLine(p, a, b, c); projected = true; } } poly[i] = p; } return projected; } // Performs one step of the polygon separation algorithm. Changes // the 'polygons' array in place, moving them using the shape matching approach. // Returns true iff collision was detected function separatePolygons(polygons) { let newPolys = projectCollisions(polygons); let collide = false; for (let i = 0; i < polygons.length; i++) { if (newPolys[i]) { projectHalfspaces(newPolys[i]); let M = shapeMatch(polygons[i], newPolys[i]); polygons[i] = transformPoints(polygons[i], M); collide = true; } else { let copy = polygons[i].slice(); if (projectHalfspaces(copy)) { let M = shapeMatch(polygons[i], copy); polygons[i] = transformPoints(polygons[i], M); collide = true; } } } return collide; } // Find the point on polygon poly's boundary closest to pt and its distance function findPivot(poly, pt) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(pt, p, q); let d = vec2.dist(candPivot, pt); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' // Returns the (possibly modified) polygon. function nudgePoly(poly, mouse, minDist) { let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; for (let irelax = 0; irelax < relaxIterations; irelax++) { polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); separatePolygons(polygons); } refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; for (let irelax = 0; irelax < relaxIterations; irelax++) { polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); separatePolygons(polygons); } refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }36:T118e,viewof demo9 = { reset9; await visibility(); let dsp = new Display(); let polygons = []; let size = 30; for (let x = size; x < dsp.w - size; x += size * 1.5) { for (let y = size; y < dsp.h - size; y += size * 1.5) { polygons.push(rectanglePoints([x, y], [size, size])); } } let mouse = null; let selected = null; let nudgeDistance = 60; function refresh() { dsp.clear(); for (let a of polygons) { dsp.drawPolygon(a); } if (selected) dsp.drawPoints([selected], { fill: null, stroke: 'blue', radius: nudgeDistance }); } // Projects back points outside the canvas. // Returns true if projection was performed on poly, in which case, // the vertices of poly are modified in place. function projectHalfspaces(poly) { let projected = false; for (let i = 0; i < poly.length; i++) { let p = poly[i]; for (let [a, b, c] of [ [-1, 0, 0], [1, 0, -dsp.canvas.width], [0, -1, 0], [0, 1, -dsp.canvas.height] ]) { if (a * p[0] + b * p[1] + c >= 0) { p = projectPointLine(p, a, b, c); projected = true; } } poly[i] = p; } return projected; } // Performs one step of the polygon separation algorithm. Changes // the 'polygons' array in place, moving them using the shape matching approach. // Returns true iff collision was detected function separatePolygons(polygons) { //sanityCheck(polygons); let newPolys = projectCollisions(polygons); //sanityCheck(polygons); let collide = false; for (let i = 0; i < polygons.length; i++) { if (newPolys[i]) { projectHalfspaces(newPolys[i]); let M = shapeMatch(polygons[i], newPolys[i]); if (Number.isNaN(M[0])) { // Probably degenerate polygon - ignore it and hopefully // further iterations will fix it console.log("Degenerate", i, M, polygons[i], newPolys[i]); continue; } polygons[i] = transformPoints(polygons[i], M); collide = true; } else { let copy = polygons[i].slice(); if (projectHalfspaces(copy)) { let M = shapeMatch(polygons[i], copy); polygons[i] = transformPoints(polygons[i], M); //checkCoords(polygons[i]); collide = true; } } } return collide; } // Find the point on polygon poly's boundary closest to pt and its distance function findPivot(poly, pt) { let pivot = null; let pivotDistance = Number.MAX_VALUE; let q = poly[poly.length - 1]; for (let p of poly) { let candPivot = closestSegmentPoint(pt, p, q); let d = vec2.dist(candPivot, pt); if (d < pivotDistance) { pivotDistance = d; pivot = candPivot; } q = p; } return [pivot, pivotDistance]; } // Nudges polygon 'poly' so that it is at least 'minDist' units away from 'mouse' // Returns the (possibly modified) polygon. function nudgePoly(poly, mouse, minDist) { //checkCoords(poly); let last = poly.length; let [pivot, dist] = findPivot(poly, mouse); let inside = pointInPolygon(mouse, poly); if (dist < minDist || inside) { let p = inside ? pointAtDist(mouse, pivot, -minDist) : pointAtDist(mouse, pivot, minDist); let copy = poly.slice(); // A copy of a poly.push(pivot); copy.push(p); let M = shapeMatch(poly, copy); poly = transformPoints(poly, M); poly.pop(); [pivot, dist] = findPivot(poly, mouse); inside = pointInPolygon(mouse, poly); } //checkCoords(poly); return poly; } dsp.canvas.onmousedown = e => { mouse = [e.offsetX, e.offsetY]; selected = [e.offsetX, e.offsetY]; for (let irelax = 0; irelax < relaxIterations; irelax++) { polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); separatePolygons(polygons); } refresh(); }; dsp.canvas.onmousemove = e => { if (selected) { selected = mouse = [e.offsetX, e.offsetY]; for (let irelax = 0; irelax < relaxIterations; irelax++) { polygons.forEach( (a, i) => (polygons[i] = nudgePoly(a, mouse, nudgeDistance)) ); separatePolygons(polygons); } refresh(); } }; dsp.canvas.onmouseup = e => { selected = null; refresh(); }; refresh(); return dsp.canvas; }37:T4b3,// // Given an array of source points and an array of destination points as in Fig 3 // of the paper, returns a rigid transformation matrix that best approximates the // transformation from source to destination points. // function shapeMatch(srcPoints, dstPoints) { // The center of mass of the src points let srcCenter = centerOfMass(srcPoints); // src displacement vectors wrt center of mass let srcVectors = srcPoints.map((p) => vec2.sub([], p, srcCenter)); // destination points center of mass let dstCenter = centerOfMass(dstPoints); // dst displacement vectors wrt center of mass let dstVectors = dstPoints.map((p) => vec2.sub([], p, dstCenter)); // Compute rotation and compose with the two translations let [[a, b], [c, d]] = shapeMatchRotation(srcVectors, dstVectors); let det = glmatrix.mat2.determinant([a, b, c, d]); if (isNaN(det) || det < 0.9 || det > 1.1) { console.log("BUG shapeMatch", { det, a, b, c, d, srcPoints, dstPoints }); a = d = 1; b = c = 0; //throw "BUG shapeMatch"; } return mat2d.mul( [], mat2d.fromValues(a, b, c, d, dstCenter[0], dstCenter[1]), mat2d.fromTranslation([], [-srcCenter[0], -srcCenter[1]]) ); }38:T59b,// Tests collisions among polygons and returns projected points for those // in collision. Returns an array 'newPolygons' where newPolygons [i] is a // projected copy of polygons[i] if it is in collision or null otherwise. function projectCollisions(polygons) { let npoly = polygons.length; let newPolygons = []; // Enhance performance using sweep and prune let pairs = sap(polygons, [1, 0]); for (let i = 0; i < npoly; i++) { let a = polygons[i]; //for (let j = i + 1; j < npoly; j++) { for (let j of pairs[i]) { let b = polygons[j]; let hit = gjk(a, b); if (hit) { let { p, q, n } = epa(a, b, ...hit); let ptsA = supportEdge(a, n); console.assert(ptsA.length > 0); let ptsB = supportEdge(b, [-n[0], -n[1]]); console.assert(ptsB.length > 0); let center = centerOfMass(ptsA.concat(ptsB)); let [ha, hb, hc] = halfSpace(center, n); let acopy = newPolygons[i] || a.slice(); acopy.forEach((pt, i) => { if (ha * pt[0] + hb * pt[1] + hc > 0) acopy[i] = projectPointLine(pt, ha, hb, hc); }); newPolygons[i] = acopy; let bcopy = newPolygons[j] || b.slice(); bcopy.forEach((pt, i) => { if (ha * pt[0] + hb * pt[1] + hc < 0) bcopy[i] = projectPointLine(pt, ha, hb, hc); }); newPolygons[j] = bcopy; } } } return newPolygons; }39:T585,class Display { constructor (w = 640, h = 480) { [this.w,this.h] = [w,h]; this.canvas = html`