28:null 29:["$","title",null,{"children":"2D Geometry Utils | Claudio Esperança | Observable"}] 2e:Ta26,/** * My homebrewed 2D Vector class **/ Vector = { // Determinant of a 3x3 matrix let det = (t00, t01, t02, t10, t11, t12, t20, t21, t22) => t00 * (t11 * t22 - t12 * t21) + t01 * (t12 * t20 - t10 * t22) + t02 * (t10 * t21 - t11 * t20); class Vector { constructor(x = 0, y = 0) { [this.x, this.y] = [x, y]; } array() { return [this.x, this.y]; } clone() { // A copy of this vector return new Vector(this.x, this.y); } mag() { // Magnitude (length) return Math.sqrt(this.dot(this)); } set(other) { // Set from another vector [this.x, this.y] = [other.x, other.y]; } add(v) { // Vector sum return new Vector(this.x + v.x, this.y + v.y); } sub(v) { // Vector subtraction return new Vector(this.x - v.x, this.y - v.y); } dist(q) { // Distance to point return this.sub(q).mag(); } dot(q) { // Dot product return this.x * q.x + this.y * q.y; } angle(v) { // Returns the angle between this vector and v return Math.acos( Math.min(Math.max(this.dot(v) / this.mag() / v.mag(), -1), 1) ); } signedAngle(v) { // Returns the _signed_ angle between this vector and v // so that a rotation of this by angle makes it colinear with v let a = this.angle(v); if (new Vector(0, 0).orient(this, v) > 0) return -a; return a; } scale(alpha) { // Multiplication by scalar return new Vector(this.x * alpha, this.y * alpha); } rotate(angle) { // Returns this vector rotated by angle radians let [c, s] = [Math.cos(angle), Math.sin(angle)]; return new Vector(c * this.x - s * this.y, s * this.x + c * this.y); } mix(q, alpha) { // this vector * (1-alpha) + q * alpha return new Vector( this.x * (1 - alpha) + q.x * alpha, this.y * (1 - alpha) + q.y * alpha ); } normalize() { // this vector normalized return this.scale(1 / this.mag()); } distSegment(p, q) { // Distance to line segment var s = p.dist(q); if (s < 0.00001) return this.dist(p); var v = q.sub(p).scale(1.0 / s); var u = this.sub(p); var d = u.dot(v); if (d < 0) return this.dist(p); if (d > s) return this.dist(q); return p.mix(q, d / s).dist(this); } orient(p, q) { // Returns the orientation of triangle (this,p,q) return Math.sign(det(1, 1, 1, this.x, p.x, q.x, this.y, p.y, q.y)); } } return Vector; }2f:T50c,// // A 2D ray // class Ray { constructor (p,v) { // p is the source point and v is the ray direction [this.p,this.v] = [p,v]; } point (t) { // Assuming the ray describes a parametric line p + tv, it returns // the point at the given t return this.p.add(this.v.scale(t)); } intersectRay (other) { // Intersection with another ray. Returns [t,u], i.e., // the parameters for the intersection point in both rays parametric // space. If no intersection, returns false let [p_0, v_0] = [this.p.x, this.v.x]; let [p_1, v_1] = [this.p.y, this.v.y]; let [P_0, V_0] = [other.p.x, other.v.x]; let [P_1, V_1] = [other.p.y, other.v.y]; let den = v_0 * V_1 - v_1 * V_0; if (Math.abs(den) <= Number.EPSILON) return false; let t = (V_1*(P_0 - p_0) + p_1*V_0 - P_1*V_0)/den; let u = (v_1*(P_0 - p_0) + p_1*v_0 - P_1*v_0)/den; return [t,u] } intersectSegment (a,b) { // Intersection with line segment ab. Returns the value // of the parameter for the intersection or a negative // value if no intersection let R = new Ray(a, b.sub(a)); let result = this.intersectRay (R); if (result == false) return false; let [t,u] = result; if (t > 0 && u >= 0 && u <= 1) return t; return -1; } }30:T1136,BinaryHeap = { // // A binary heap (from eloquentjavascript.net). // By default, implements a min heap. By defining scoreFunction // other behaviors can be implemented. For instance function (x) { return -x } can // be used to define a max heap. // function BinaryHeap(scoreFunction){ this.content = []; this.scoreFunction = scoreFunction || function (x) { return x }; } BinaryHeap.prototype = { // // Adds a new element to the heap // push: function(element) { // Add the new element to the end of the array. this.content.push(element); // Allow it to bubble up. this.bubbleUp(this.content.length - 1); }, // // Removes the top of the heap and returns it // pop: function() { // Store the first element so we can return it later. var result = this.content[0]; // Get the element at the end of the array. var end = this.content.pop(); // If there are any elements left, put the end element at the // start, and let it sink down. if (this.content.length > 0) { this.content[0] = end; this.sinkDown(0); } return result; }, // // Removes a given value from the heap. // remove: function(node) { var length = this.content.length; // To remove a value, we must search through the array to find // it. for (var i = 0; i < length; i++) { if (this.content[i] != node) continue; // When it is found, the process seen in 'pop' is repeated // to fill up the hole. var end = this.content.pop(); // If the element we popped was the one we needed to remove, // we're done. if (i == length - 1) break; // Otherwise, we replace the removed element with the popped // one, and allow it to float up or sink down as appropriate. this.content[i] = end; this.bubbleUp(i); this.sinkDown(i); break; } }, // // Returns the number of elements of the heap // size: function() { return this.content.length; }, // // Moves element at position n towards the top as necessary bubbleUp: function(n) { // Fetch the element that has to be moved. var element = this.content[n], score = this.scoreFunction(element); // When at 0, an element can not go up any further. while (n > 0) { // Compute the parent element's index, and fetch it. var parentN = Math.floor((n + 1) / 2) - 1, parent = this.content[parentN]; // If the parent has a lesser score, things are in order and we // are done. if (score >= this.scoreFunction(parent)) break; // Otherwise, swap the parent with the current element and // continue. this.content[parentN] = element; this.content[n] = parent; n = parentN; } }, // // Moves element at position n towards the bottom as necessary sinkDown: function(n) { // Look up the target element and its score. var length = this.content.length, element = this.content[n], elemScore = this.scoreFunction(element); while(true) { // Compute the indices of the child elements. var child2N = (n + 1) * 2, child1N = child2N - 1; // This is used to store the new position of the element, // if any. var swap = null; // If the first child exists (is inside the array)... if (child1N < length) { // Look it up and compute its score. var child1 = this.content[child1N], child1Score = this.scoreFunction(child1); // If the score is less than our element's, we need to swap. if (child1Score < elemScore) swap = child1N; } // Do the same checks for the other child. if (child2N < length) { var child2 = this.content[child2N], child2Score = this.scoreFunction(child2); if (child2Score < (swap == null ? elemScore : child1Score)) swap = child2N; } // No need to swap further, we are done. if (swap == null) break; // Otherwise, swap and continue. this.content[n] = this.content[swap]; this.content[swap] = element; n = swap; } } } return BinaryHeap }31:T18fc,Curve = { // A curve is an array of points class Curve extends Array { constructor(...args) { super(...args); } // Returns an array with the same size as this curve where each element // is the total arc length at that point arcLength() { let q = this[0]; let r = 0; let per = []; per[0] = 0; for (let i = 1; i < this.length; i++) { var p = this[i]; r += p.dist(q); per[i] = r; q = p; } return per; } // Total length of the curve perimeter() { return this.arcLength()[this.length - 1]; } // Returns the area enclosed by the curve area() { let s = 0.0; for (let i = 0; i < this.length; i++) { let j = (i + 1) % this.length; s += this[i].x * this[j].y; s -= this[i].y * this[j].x; } return s; } // Centroid of the curve centroid() { let p = Vec(); for (let q of this) { p.x += q.x; p.y += q.y; } p.x /= this.length; p.y /= this.length; return p; } // A minimum bounding rectangle for the curve mbr() { let r = new MBR(); for (let p of this) r.add(p); return r; } // Returns true if this curve (assuming it represents a closed simple polygon) // contains point p. contains(point) { let n = this.length, { x: x0, y: y0 } = this[n - 1], { x, y } = point, x1, y1, inside = false; for (let { x: x1, y: y1 } of this) { if (y1 > y !== y0 > y && x < ((x0 - x1) * (y - y1)) / (y0 - y1) + x1) inside = !inside; x0 = x1; y0 = y1; } return inside; } // Returns a subsampled version of this curve, where tol is // the maximum allowed Douglas Peucker distance and count is the // maximum number of points allowed subsample(tol = 0, count = 1e10) { let rank = douglasPeuckerRank(this, tol); var r = new Curve(); for (let i = 0; i < this.length; i++) { if (rank[i] != undefined && rank[i] < count) { r.push(this[i]); } } return r; } // Returns a chaikin subsampled version of this curve chaikin(closed = false) { let r = new Curve(); let [q, i] = closed ? [this[this.length - 1], 0] : [this[0], 1]; for (; i < this.length; i++) { let p = this[i]; let e = p.sub(q); if (closed || i != 1) r.push(q.add(e.scale(0.25))); else r.push(q); if (closed || i + 1 < this.length) r.push(q.add(e.scale(0.75))); else r.push(p); q = p; } return r; } // Returns another curve resampled by arc length with n points resample(n, closed = false) { if (closed) { n++; this.push(this[0]); } let per = this.arcLength(); let len = per[per.length - 1]; let dlen = len / (n - 1); let p = this[0]; let r = new Curve(); r.push(p.clone()); let j = 0; for (let i = 1; i < n; i++) { let d = dlen * i; while (j + 1 < this.length - 1 && per[j + 1] < d) j++; let rate = per[j + 1] - per[j]; let alpha = rate == 0 ? 0 : (d - per[j]) / rate; let pt = this[j].mix(this[j + 1], alpha); r.push(pt); } if (closed) { this.pop(); r.pop(); } return r; } // Returns a resampling of this curve with n points where the original points are considered // control points. If not closed, the first and last points are considered twice so that // the catmull-rom spline interpolates them. If closed, the first and last points are also // considered twice, but in the opposite order. The tension parameter controls the spline interpolation splineResample(n, closed = false, tension = 0.5) { let p = (closed ? [] : [this[0]]).concat(this); if (!closed) p.push(this[this.length - 1]); let cr = new CatmullRom(...p); cr.tension = tension; let r = new Curve(); let f = closed ? this.length / (n - 1) : (this.length - 1) / (n - 1); for (let i = 0; i < n; i++) { let u = i * f; r.push(cr.point(u)); } return r; } } // Creates a Douglas Peucker Item, which // represents a span of a polyline and the farthest element from the // line segment connecting the first and the last element of the span. // Poly is an array of points, first is the index of the first element of the span, // and last the last element. function dpItem(first, last, poly) { var dist = 0; var farthest = first + 1; var a = poly[first]; var b = poly[last]; for (var i = first + 1; i < last; i++) { var d = poly[i].distSegment(a, b); if (d > dist) { dist = d; farthest = i; } } return { first: first, last: last, farthest: farthest, dist: dist }; } // Returns an array of ranks of vertices of a polyline according to the // generalization order imposed by the Douglas Peucker algorithm. // Thus, if the i'th element has value k, then vertex i would be the (k+1)'th // element to be included in a generalization (simplification) of this polyline. // Does not consider vertices farther than tol. Disconsidered // vertices are left undefined in the result. function douglasPeuckerRank(poly, tol) { // A priority queue of intervals to subdivide, where top priority is biggest dist var pq = new BinaryHeap(function (dpi) { return -dpi.dist; }); // The result vector var r = []; // Put the first and last vertices in the result r[0] = 0; r[poly.length - 1] = 1; // Add first interval to pq if (poly.length <= 2) { return r; } pq.push(dpItem(0, poly.length - 1, poly)); // The rank counter var rank = 2; // Recursively subdivide up to tol while (pq.size() > 0) { var item = pq.pop(); if (item.dist < tol) break; // All remaining points are closer r[item.farthest] = rank++; if (item.farthest > item.first + 1) { pq.push(dpItem(item.first, item.farthest, poly)); } if (item.last > item.farthest + 1) { pq.push(dpItem(item.farthest, item.last, poly)); } } return r; } return Curve; }32:T512,{ let height = width*9/16; const canvas = DOM.canvas(width, height,1); const ctx = canvas.getContext("2d"); let dragStart = null; canvas.oncontextmenu = function (e) { e.preventDefault(); } canvas.onmousedown = function (e) { let p = Vec(e.offsetX,e.offsetY); if (e.buttons & 1) { curve.length = 0; curve.push(p) } else { if (curve.contains(p)) { dragStart = p; } else { dragStart = null } } } canvas.onmousemove = function (e) { let p = Vec(e.offsetX,e.offsetY); if (e.buttons & 1) { curve.push(p) } else if ((e.buttons & 6) && dragStart) { let v = p.sub(dragStart); for (let q of curve) { q.x += v.x; q.y += v.y; } dragStart = p; } } while(true) { ctx.lineWidth = 1; ctx.clearRect(0,0,width,height) ctx.strokeStyle = "black"; if (curve.length > 0) { ctx.beginPath() ctx.moveTo(curve[0].x,curve[0].y); for (let i = 1; i < curve.length; i++) ctx.lineTo(curve[i].x,curve[i].y) ctx.stroke(); ctx.fillStyle = 'rgba(255,0,0,0.5)'; for (let {x,y} of curve) { ctx.beginPath(); ctx.arc(x,y,4,0,2*Math.PI); ctx.fill() } } yield canvas; } }33:T4cf,{ let height = width*9/16; const canvas = DOM.canvas(width, height); const ctx = canvas.getContext("2d"); let refresh = () => { let bez = new Bezier(...bezierControlPoints); ctx.clearRect(0,0,width,height) ctx.lineWidth = 4; ctx.strokeStyle = "black"; bez.draw(ctx); ctx.lineWidth = 10; ctx.strokeStyle = "green"; for (let q of bez.p) { ctx.beginPath(); ctx.moveTo (q.x-5,q.y); ctx.lineTo (q.x+5,q.y); ctx.stroke(); } ctx.lineWidth = 1; ctx.strokeStyle = "red"; ctx.beginPath(); ctx.moveTo(bez.p[0].x,bez.p[0].y); ctx.lineTo(bez.p[1].x,bez.p[1].y); ctx.lineTo(bez.p[2].x,bez.p[2].y); ctx.lineTo(bez.p[3].x,bez.p[3].y); ctx.stroke(); } let selPoint = null; let mouse = null; canvas.onmousedown = (e) => { let p = Vec(e.offsetX,e.offsetY); selPoint = null; for (let q of bezierControlPoints) { if (q.dist(p)<10) selPoint=q } mouse = p } canvas.onmousemove = (e) => { if (selPoint && e.buttons) { let p = Vec(e.offsetX,e.offsetY); let d = p.sub(mouse) selPoint.x += d.x; selPoint.y += d.y; refresh() mouse = p } } refresh() return canvas; }34:T5d2,{ let height = width*9/16; const canvas = DOM.canvas(width, height); const ctx = canvas.getContext("2d"); let refresh = () => { let bez = new CatmullRom(...catmullControlPoints); bez.tension = tension; ctx.clearRect(0,0,width,height) ctx.lineWidth = 4; ctx.strokeStyle = "black"; let [min,max] = closed ? [0,400]:[0,100]; let p = bez.point(min/100); ctx.beginPath() ctx.moveTo(p.x,p.y); for (let i = min; i < max; i++) { p = bez.point(i/100); ctx.lineTo(p.x,p.y); } ctx.stroke(); ctx.lineWidth = 10; ctx.strokeStyle = "green"; for (let q of bez.p) { ctx.beginPath(); ctx.moveTo (q.x-5,q.y); ctx.lineTo (q.x+5,q.y); ctx.stroke(); } ctx.lineWidth = 1; ctx.strokeStyle = "red"; ctx.beginPath(); ctx.moveTo(bez.p[0].x,bez.p[0].y); ctx.lineTo(bez.p[1].x,bez.p[1].y); ctx.lineTo(bez.p[2].x,bez.p[2].y); ctx.lineTo(bez.p[3].x,bez.p[3].y); ctx.stroke(); } refresh() let selPoint = null; let mouse = null; canvas.onmousedown = (e) => { let p = Vec(e.offsetX,e.offsetY); selPoint = null; for (let q of catmullControlPoints) { if (q.dist(p)<10) selPoint=q } mouse = p } canvas.onmousemove = (e) => { if (selPoint && e.buttons) { let p = Vec(e.offsetX,e.offsetY); let d = p.sub(mouse) selPoint.x += d.x; selPoint.y += d.y; refresh() mouse = p } } yield canvas; }35:T800,class Matrix { // Constructor from elements specified in column-wise order, i.e., a and b are the elements in the first // columnm, c,d are the elements in the second column and e,f the elements in the third column constructor(a = 1, b = 0, c = 0, d = 1, e = 0, f = 0) { [this.a, this.b, this.c, this.d, this.e, this.f] = [a, b, c, d, e, f]; } // Builds a translation matrix static translate(dx = 0, dy = 0) { return new Matrix(1, 0, 0, 1, dx, dy); } // Builds a scale matrix static scale(sx = 1, sy = 1) { return new Matrix(sx, 0, 0, sy); } // Builds a shear (skew) matrix static shear(sx = 0, sy = 0) { return new Matrix(1, sx, sy, 1); } // Builds a rotation matrix static rotate(angle = 0) { let [s, c] = [Math.sin(angle), Math.cos(angle)]; return new Matrix(c, s, -s, c); } // Returns point p transformed by this matrix (assumes p is a point) apply(p) { return Vec( this.a * p.x + this.c * p.y + this.e, this.b * p.x + this.d * p.y + this.f ); } // Returns point p transformed by this matrix (assumes p is a point) applyPoint(p) { return Vec( this.a * p.x + this.c * p.y + this.e, this.b * p.x + this.d * p.y + this.f ); } // Returns vector v transformed by this matrix (assumes p is a point) applyVector(v) { return Vec(this.a * v.x + this.c * v.y, this.b * v.x + this.d * v.y); } // Returns this multiplied by m mult(m) { return new Matrix( this.a * m.a + this.c * m.b, this.b * m.a + this.d * m.b, this.a * m.c + this.c * m.d, this.b * m.c + this.d * m.d, this.a * m.e + this.c * m.f + this.e, this.b * m.e + this.d * m.f + this.f ); } // Returns the inverse matrix inverse() { let { a, b, c, d, e, f } = this; let det = a * d - b * c; if (!det) { return null; } det = 1.0 / det; return new Matrix( d * det, -b * det, -c * det, a * det, (c * f - d * e) * det, (b * e - a * f) * det ); } }36:Tdbc,Transform = { function Slider (options={}) { let {title="", min=-100, max=100, step=1, size="20em", value=0, callback=()=>0 } = options; let input = html``; let output = html`${value}`; input.value = value; input.oninput = (e) => { value = input.value; output.value = value callback(value) } return html`${title}: ${input} ${output}`; } function XYSlider (options) { let {title="", min=-100, max=100, step=1, size="10em", value=Vec(0,0), callback=()=>0 } = options; let xslider = Slider({title:"x", min:min, max:max, step:step, value:value.x, callback : x=> {value.x = +x; callback(value) }}); let yslider = Slider({title:"y", min:min, max:max, step:step, value:value.y, callback : y=> {value.y = +y; callback(value) }}); return html`${title} ${xslider} , ${yslider}`; } function matrixTex (m) { let fmt = (x) => x.toFixed(4) == x ? x : x.toFixed(4); return `\\begin{bmatrix} ${fmt(m.a)} & ${fmt(m.c)} & ${fmt(m.e)} \\\\ ${fmt(m.b)} & ${fmt(m.d)} & ${fmt(m.f)} \\\\ 0 & 0 & 1 \\end{bmatrix}` } class Transform { constructor (callback = (t) => {}) { this.callback = callback; this.matrices = []; this.sliders = []; } reset () { this.matrices = []; this.sliders = []; this.callback(this); return this } addTranslate () { let i = this.matrices.length; this.matrices.push (new Matrix()) this.sliders.push (XYSlider({title : "Translate ", min:-100, max:100, step:1, value:Vec(0,0), callback : t => { this.matrices[i] = Matrix.translate(t.x,t.y); this.callback(this) }})); return this; } addScale() { let i = this.matrices.length; this.matrices.push (new Matrix()) this.sliders.push (XYSlider({title : "Scale ", min:0.2, max:4, step:0.2, value:Vec(1,1), callback: s => { this.matrices[i] = Matrix.scale(s.x,s.y); this.callback(this) }})); return this; } addShear() { let i = this.matrices.length; this.matrices.push (new Matrix()) this.sliders.push (XYSlider({title : "Shear ", min:-4, max:4, step:0.2, value:Vec(0,0), callback: s => { this.matrices[i] = Matrix.shear(s.x,s.y); this.callback(this) }})); return this; } addRotate() { let i = this.matrices.length; this.matrices.push (new Matrix()) this.sliders.push (Slider({title:"Rotate", min:-180, max:180, step:5, value:0, callback : a => { this.matrices[i] = Matrix.rotate(Math.PI*a/180); this.callback(this) }})); return this; } UI () { let ui = html`

`; for (let slider of this.sliders) { ui.append(slider) ui.append(html`
`) } return ui } matrix() { if (this.matrices.length == 0) return new Matrix() if (this.matrices.length == 1) return this.matrices[0]; return this.matrices.reduce((a,b) => a.mult(b)) } tex() { if (this.matrices.length < 2) return tex`${matrixTex(this.matrix())}`; return tex`${(this.matrices.map(matrixTex)).join("\\times")+"="+matrixTex(this.matrix())}`; } } return Transform } 37:T9fb,class MBR { // Minimum Bounding Rectangle constructor() { // MBR for a variable number of points this.min = new Vector(Number.POSITIVE_INFINITY, Number.POSITIVE_INFINITY); this.max = new Vector(Number.NEGATIVE_INFINITY, Number.NEGATIVE_INFINITY); for (let p of arguments) this.add(p); } valid() { // Whether this is a valid MBR return this.min.x <= this.max.x && this.min.y <= this.max.y; } size() { // Size of this box return new Vector(this.max.x - this.min.x, this.max.y - this.min.y); } center() { // Center of the box return this.min.add(this.max).scale(0.5); } add(p) { // Adds a new point to this MBR this.min.x = Math.min(p.x, this.min.x); this.min.y = Math.min(p.y, this.min.y); this.max.x = Math.max(p.x, this.max.x); this.max.y = Math.max(p.y, this.max.y); } contains(p, r = 0) { // Whether MBR contains a point / circle return ( p.x + r >= this.min.x && p.y + r >= this.min.y && p.x - r < this.max.x && p.y - r < this.max.y ); } pointDist(p) { // Distance from box to point let dx = Math.max(this.min.x - p.x, 0, p.x - this.max.x); let dy = Math.max(this.min.y - p.y, 0, p.y - this.max.y); return Math.sqrt(dx * dx + dy * dy); } intersects(other) { // Whether this MBR intersects another MBR let minx = Math.max(other.min.x, this.min.x); let maxx = Math.min(other.max.x, this.max.x); if (minx >= maxx) return false; let miny = Math.max(other.min.y, this.min.y); let maxy = Math.min(other.max.y, this.max.y); return miny < maxy; } intersection(other) { // Returns intersection with another MBR let ret = new MBR(); ret.min.x = Math.max(other.min.x, this.min.x); ret.max.x = Math.min(other.max.x, this.max.x); ret.min.y = Math.max(other.min.y, this.min.y); ret.max.y = Math.min(other.max.y, this.max.y); return ret; } union(other) { // Returns union with another MBR let ret = new MBR(); ret.min.x = Math.min(other.min.x, this.min.x); ret.max.x = Math.max(other.max.x, this.max.x); ret.min.y = Math.min(other.min.y, this.min.y); ret.max.y = Math.max(other.max.y, this.max.y); return ret; } transform(matrix) { // Returns a new MBR transformed by matrix return new MBR(matrix.applyPoint(this.min), matrix.applyPoint(this.max)); } draw(ctx) { // Draw on a canvas let s = this.size(); ctx.beginPath(); ctx.rect(this.min.x, this.min.y, s.x, s.y); ctx.stroke(); } }38:[] 2c:{"id":"9a7362216b9c95fc","slug":"2d-geometry-utils","title":"2D Geometry Utils","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2018-07-02T20:58:41.169Z","update_time":"$D2022-08-08T20:06:44.207Z","view_time":null,"first_public_time":"$D2018-07-02T21:21:42.705Z","has_unpublished_edits":null,"fork":false,"stars":20,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":769,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":12,"collection":{"id":"6d5491418629643c","slug":"libraries","title":"Libraries","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"title":"2D Geometry Utils","cells":[{"id":0,"value":"md`# 2D Geometry Utils`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"md`## Vectors and Points\n\nThese are both represented by instances of class \\`Vector\\``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$2e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"// Convenience function to instantiate vectors \nVec = (x,y)=>new Vector(x,y)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"md`## 2D Rays`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"md`## Binary Heap\n\n(needed for the implementation of the Douglas-Peucker-Ramer curve simplification algorithm)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"md`## Curve`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":321,"value":"md`### Curve demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":304,"value":"{\n let resample = html``;\n resample.onclick = () => {\n curve.splice(0, curve.length, ...curve.resample(vertexCount));\n };\n let subsample = html``;\n subsample.onclick = () => {\n curve.splice(0, curve.length, ...curve.subsample(tolerance, vertexCount));\n };\n let spline = html``;\n spline.onclick = () => {\n curve.splice(0, curve.length, ...curve.splineResample(vertexCount));\n };\n let chaikin = html``;\n chaikin.onclick = () => {\n curve.splice(0, curve.length, ...curve.chaikin());\n };\n return md`${resample} ${spline} ${subsample} ${chaikin}`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"{\n return md`tolerance:${bindSliderNumber({min:1,max:100,step:1},viewof tolerance)}\n vertices:${bindSliderNumber({min:2,max:200,step:1},viewof vertexCount)}`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"mutable curve = new Curve(Vec(100,100),Vec(300,300),Vec(500,200))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"viewof vertexCount = new View (100)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"viewof tolerance = new View (5)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"md`## Cubic Bézier Curves\n\nRepresented by instances of class \\`Bezier\\``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"/** \n * Homebrew cubic Bézier curve in 2D\n **/\nclass Bezier { // Cubic bézier\n \n constructor (p0,p1,p2,p3) { // The four control points\n this.p = [p0,p1,p2,p3]\n }\n \n point (t) { // Point at t\n var [p0,p1,p2,p3] = this.p;\n var [p01,p11,p21] = [p0.mix(p1,t),p1.mix(p2,t),p2.mix(p3,t)];\n var [p02,p12] = [p01.mix(p11,t),p11.mix(p21,t)];\n return p02.mix(p12,t)\n }\n \n tangent(t) { // Unit tangent vector at t\n var [p0,p1,p2,p3] = this.p;\n var [p01,p11,p21] = [p0.mix(p1,t),p1.mix(p2,t),p2.mix(p3,t)];\n var [p02,p12] = [p01.mix(p11,t),p11.mix(p21,t)];\n return p12.sub(p02).normalize()\n }\n \n draw (ctx) { // Draw on a canvas 2D context\n var [p0,p1,p2,p3] = this.p;\n ctx.beginPath();\n ctx.moveTo(p0.x,p0.y);\n ctx.bezierCurveTo(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);\n ctx.stroke();\n }\n \n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":326,"value":"md`### Bézier demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":360,"value":"bezierControlPoints = {\n let height = width*9/16;\n return [Vec(width/5,height/2),\n Vec(2*width/5,height/4),\n Vec(3*width/5,3*height/4),\n Vec(4*width/5,height/2)]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"md`## Catmull-Rom splines`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"class CatmullRom {\n\n set tension(t) {\n this.tau = t; \n }\n \n get tension() {\n return typeof this.tau === 'undefined' ? 0.5 : this.tau\n }\n \n constructor (...controlPoints) {\n this.p = controlPoints;\n }\n \n _blendFactors (u) {\n let u1 = u;\n let u2 = u*u;\n let u3 = u2*u;\n let tau = this.tension;\n return [ -tau * u1 + 2 * tau * u2 - tau * u3,\n 1 + (tau-3) * u2 + (2 - tau) * u3,\n tau * u1 + (3 - 2*tau) * u2 + (tau - 2) * u3,\n -tau * u2 + tau * u3];\n }\n\n point (u) {\n let i = ~~u;\n u = u%1;\n let n = this.p.length;\n let [p0,p1,p2,p3] = [this.p[i%n], this.p[(i+1)%n], \n this.p[(i+2)%n], this.p[(i+3)%n]];\n let [b0,b1,b2,b3] = this._blendFactors (u);\n return new Vector (p0.x*b0+p1.x*b1+p2.x*b2+p3.x*b3,\n p0.y*b0+p1.y*b1+p2.y*b2+p3.y*b3);\n }\n}\n \n ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"md`### Catmull-Rom splines demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"md`Tension: ${bindSliderNumber({min:0,max:1,step:0.1},viewof tension)} \n${bindCheckbox(\"\",viewof closed)} closed`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":372,"value":"catmullControlPoints = {\n let height = width*9/16;\n return [Vec(width/5,height/2),\n Vec(2*width/5,height/4),\n Vec(3*width/5,3*height/4),\n Vec(4*width/5,height/2)]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":382,"value":"viewof closed = new View(true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"viewof tension = new View(0.5)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"md`## Transformation matrices`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":616,"value":"md`### Matrix Demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":546,"value":"matrixDemoUI = T.UI()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":591,"value":"matrixDemoButtons = {\n let reset = html``; \n reset.onclick = () => {\n mutable T = mutable T.reset()\n }\n let translate = html``; \n translate.onclick = () => {\n mutable T = mutable T.addTranslate()\n }\n let scale = html``; \n scale.onclick = () => {\n mutable T = mutable T.addScale()\n }\n let rotate = html``; \n rotate.onclick = () => {\n mutable T = mutable T.addRotate()\n }\n let shear = html``; \n shear.onclick = () => {\n mutable T = mutable T.addShear()\n }\n return html`${translate} ${scale} ${rotate} ${shear} ${reset}`\n}\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":560,"value":"{\n tcount;\n let height = width*9/16;\n const canvas = DOM.canvas(width, height);\n const ctx = canvas.getContext(\"2d\");\n \n ctx.translate(width/2-50,height/2-50);\n ctx.font = '20px serif';\n ctx.clearRect(-width/2+50,-height/2+50,width,height)\n ctx.beginPath()\n ctx.moveTo(0,0);\n ctx.lineTo(100,0)\n ctx.moveTo(0,0)\n ctx.lineTo(0,100)\n ctx.moveTo(0,0)\n ctx.arc (0,0,5,0,Math.PI*2)\n ctx.stroke()\n ctx.fill()\n ctx.fillText('y',-15,110)\n ctx.fillText('x',110, -10)\n let m = T.matrix();\n ctx.transform(m.a, m.b, m.c, m.d, m.e, m.f);\n ctx.beginPath()\n ctx.arc(50,50,40,0,Math.PI*2)\n ctx.stroke()\n ctx.beginPath()\n ctx.arc(50,50,30,Math.PI/4,3*Math.PI/4)\n ctx.stroke()\n ctx.beginPath()\n ctx.arc(35,35,4,0,Math.PI*2)\n ctx.stroke()\n ctx.beginPath()\n ctx.arc(65,35,4,0,Math.PI*2)\n ctx.stroke()\n ctx.globalAlpha = 0.2\n ctx.fillRect (0,0,100,100)\n return ctx.canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"matrix = {\n tcount;\n return html`

Matrix: <\\p> ${T.tex()}`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":521,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":544,"value":"mutable T = new Transform(() => { mutable tcount++ } )","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":645,"value":"mutable tcount = 0","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"md`## Minimum Bounding Rectangles\nRepresented by instances of class \\`MBR\\``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"{\n const canvas = DOM.canvas(width, (width * 9) / 16);\n const ctx = canvas.getContext(\"2d\");\n let a = new MBR(Vec(10, 10), Vec(110, 110));\n let b = new MBR(Vec(50, 50), Vec(260, 260));\n ctx.lineWidth = 6;\n ctx.strokeStyle = \"black\";\n a.draw(ctx);\n ctx.strokeStyle = \"blue\";\n b.draw(ctx);\n ctx.lineWidth = 3;\n ctx.strokeStyle = \"orange\";\n a.union(b).draw(ctx);\n ctx.strokeStyle = \"pink\";\n a.intersection(b).draw(ctx);\n yield canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"md`## Libraries`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"import {View, bindSliderNumber, bindCheckbox} from \"@esperanc/inline-inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1","titling":"auto"}} 2d:"$2c:body"