class CurveLCR { constructor() { this.pts = []; this.closed = false; this.curveAutoClose = true; this.curveAutoCloseDelta = 5; this.min = Vec(1e10,1e10); this.max = Vec(-1e10,-1e10); this.extremes = [null,null]; this.flag = 0; } // Appends point p to the curve add(p) { this.pts.push(p); if (this.curveAutoClose && this.pts.length > 1) { this.closed = p.dist (this.pts[0]) <= this.curveAutoCloseDelta; } if (p.x < this.min.x) this.min.x = p.x; if (p.y < this.min.y) this.min.y = p.y; if (p.x > this.max.x) this.max.x = p.x; if (p.y > this.max.y) this.max.y = p.y; } // Applies function f to each point forEach(f) { this.pts.forEach(f); } // Reverses the order of the points in the curve reverse() { this.pts.reverse(); } // Returns the number of points in the curve count() { return this.pts.length; } // Returns a deep copy of this curve clone() { var copy = new CurveLCR(); this.pts.forEach (function (p) { copy.pts.push (p.clone()); }); return copy; } // Draws the curve. If close, draws a last segment between the first // and the last point. draw(ctx, close) { close = close == undefined ? this.closed : close; ctx.beginPath() ctx.moveTo(this.pts[0].x, this.pts[0].y); this.pts.forEach(function(p) { ctx.lineTo(p.x,p.y); ctx.moveTo(p.x,p.y); }); ctx.stroke(); //endShape(close ? CLOSE : undefined); } // Draws the points using ellipses of diameter d (8 by default) drawPoints (d) { d = d || 8; /* this.pts.forEach(function(p) { ellipse(p.x,p.y,d,d); });*/ } // Returns the perimeter of the curve. If array per is passed, per[i] will contain the // partial perimeter at point i perimeter(per) { var q = this.pts[0]; var r = 0; per = per || []; per [0] = 0; for (var i = 1; i < this.pts.length; i++) { var p = this.pts[i]; r += p.dist(q); per [i] = r; q = p; } return r; } // Assuming the curve is closed and 2D, returns the area enclosed by the curve area() { var s = 0.0; for (var i = 0; i < this.pts.length; i++) { var j = (i+1)%this.pts.length; s += this.pts[i].x * this.pts[j].y; s -= this.pts[i].y * this.pts[j].x; } return s; } // Returns an array with the min and max corner of the minimum bounding box bbox () { if (this.pts.length == 0) return null; var min = this.pts[0].clone(); var max = min.clone(); for (let p in this.pts) { if (p.x < min.x) { min.x = p.x } else if (p.x > max.x) { max.x = p.x }; if (p.y < min.y) { min.y = p.y } else if (p.y > max.y) { max.y = p.y }; if (p.z < min.z) { min.z = p.z } else if (p.z > max.z) { max.z = p.z }; } return [min, max]; } // Returns the centroid of the curve centroid() { var sum = Vec(0,0,0); for (var i = 0; i < this.pts.length; i++) { var p = this.pts[i]; sum.x += p.x; sum.y += p.y; sum.z += p.z; } sum.x /= this.pts.length; sum.y /= this.pts.length; sum.z /= this.pts.length; return sum; } // Returns another curve resampled by arc length with n points resample (n) { var per = []; var len = this.perimeter(per); var dlen = len / (n-1); var p = this.pts[0]; var r = new CurveLCR(); r.add ( Vec ( p.x, p.y, p.z )); var j = 0; for (var i = 1; i < n; i++) { var d = dlen*i; while (j+1 < this.pts.length-1 && per[j+1]0) { var p = this.pts[item.index-1]; var q = this.pts[item.index]; for (var k = 0; k < item.insertions; k++) { newCurve.add (interpPoints (p,q,0,1,(k+1)/(item.insertions+1))); } } } newCurve.add (this.pts[m-1].clone()); return newCurve; } // Returns a adaptively resampled copy of this curve with exactly n points. // Uses Douglas-Peucker for subsampling and point insertion for supersampling adaptiveResample (n) { if (n == this.pts.length) return this.clone(); if (n < this.pts.length) { // Subsample var dpr = douglasPeuckerRank (this.pts); var r = new CurveLCR(); for (var i = 0; i < this.pts.length; i++) { if (dpr[i] != undefined && dpr[i] < n) { r.add(this.pts[i].clone()) } } return r; } // Supersample return this.insert (n-this.pts.length); } // Returns the distance from point p to this curve distPoint (p) { var dmin = 1e100; for (var i = 1; i < this.pts.length; i++) { dmin = Math.min (dmin, distPointLineSegment (this.pts[i-1], this.pts[i], p)); } return dmin; } // Assuming the curve is closed and 2D (i.e., represents a polygon), // returns true iff point p is inside the polygon insidePoint (p) { var n = this.pts.length; if (n<3) return false; var qprev = this.pts[n-1]; var inf = 1.0e20; var right = inf, nright = 0; var left = -inf, nleft = 0; for (let q of this.pts) { if ((qprev.y < p.y) != (q.y < p.y)) { var x = qprev.x + (q.x - qprev.x) * (p.y - qprev.y) / (q.y - qprev.y) - p.x; if (x < 0) { nleft++; if (x > left) left = x; } else { nright++; if (x < right) right = x; } } qprev = q; } console.assert ((nright+nleft)%2 == 0); return (nright%2 != 0); } // Translates the curve by v (a vector) translate (v) { this.pts.forEach (function (p) { p.x += v.x; p.y += v.y; p.z += v.z; }) } // Scales the curve by v (a vector) scale (v) { this.pts.forEach (function (p) { p.x *= v.x; p.y *= v.y; p.z *= v.z; }) } orientation2D (p) { let dmin = 1e100; let [i1,i2] = [0,1]; for (var i = 1; i < this.pts.length; i++) { let d = distPointLineSegment (this.pts[i-1], this.pts[i], p); if (d < dmin) { dmin = d; i1 = i-1; i2 = i; } } let n = this.pts.length; if (n<2) return 1; return orientation2D (this.pts[i1], this.pts[i2], p); } }