2f:T632,class Segment { constructor(p1, p2) { this.p1 = p1; this.p2 = p2; const diff = this.p2.subtract(this.p1); this.dir = diff; this.angle = diff.heading(); this.length = diff.length(); } // helper to determine whether three points are listed in a counterclockwise order // see: https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/ ccw(a, b, c) { return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x); } // see: https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/ intersects(other) { return this.ccw(this.p1, other.p1, other.p2) !== this.ccw(this.p2, other.p1, other.p2) && this.ccw(this.p1, this.p2, other.p1) !== this.ccw(this.p1, this.p2, other.p2) } // see: https://stackoverflow.com/a/1501725/943102 distanceFromPoint(p) { const dist2 = (v, w) => (v.x - w.x) ** 2 + (v.y - w.y) ** 2; const length2 = dist2(this.p1, this.p2); if (length2 === 0) { return p.distanceFrom(this.p1); } let t = ( (p.x - this.p1.x) * (this.p2.x - this.p1.x) + (p.y - this.p1.y) * (this.p2.y - this.p1.y) ) / length2; t = Math.max(0, Math.min(1, t)); return Math.sqrt( dist2( p, new Vector( this.p1.x + t * (this.p2.x - this.p1.x), this.p1.y + t * (this.p2.y - this.p1.y) ) ) ); } distanceFromSegment(other) { if (this.intersects(other)) { return 0; } return Math.min( this.distanceFromPoint(other.p1), this.distanceFromPoint(other.p2) ); } }30:T7c7,class Vector { constructor(x, y) { this.x = x; this.y = y; } add(other) { return new Vector(this.x + other.x, this.y + other.y); } subtract(other) { return new Vector(this.x - other.x, this.y - other.y); } multiply(factor) { return new Vector(this.x * factor, this.y * factor); } divide(divisor) { return new Vector(this.x / divisor, this.y / divisor); } rotate(angle) { const cos = Math.cos(angle); const sin = Math.sin(angle); const x = this.x * cos - this.y * sin; const y = this.x * sin + this.y * cos; return new Vector(x, y); } magnitude() { return Math.sqrt(this.x * this.x + this.y * this.y); } withMagnitude(magnitude) { const ratio = magnitude / this.magnitude(); return new Vector(this.x * ratio, this.y * ratio); } normalize() { return this.withMagnitude(1); } length() { return Math.sqrt(this.x * this.x + this.y * this.y); } flipYAxis() { return new Vector(this.x, -this.y); } heading() { const d = this.normalize(); return Math.atan2(d.y, d.x); } translate(center) { return new Vector(this.x - center.x, this.y - center.y); } rotate(phi) { return new Vector( this.y * Math.sin(phi) + this.x * Math.cos(phi), this.y * Math.cos(phi) - this.x * Math.sin(phi) ); } copy() { return new Vector(this.x, this.y); } equals(other) { return this.x === other.x && this.y === other.y; } approxEquals(other, precision) { return Math.abs(this.x - other.x) < precision && Math.abs(this.y - other.y) < precision; } distanceFrom(other) { return Math.sqrt((this.x - other.x) ** 2 + (this.y - other.y) ** 2); } toString() { return `(${toFixedRound(this.x, 3)}, ${toFixedRound(this.y, 3)})`; } }31:T85d,class Figure { constructor({ ctx, scale, origin, width, height }) { this.ctx = ctx; this.scale = scale; this.origin = origin; this.width = width; this.height = height; this.drawGrid(); this.drawAxes(); } canvas() { return this.ctx.canvas; } convert(p) { return new Vector( this.origin.x + p.x * this.scale, this.origin.y - p.y * this.scale ); } drawSegment(s, color) { this.drawPoint(s.p1, color); this.drawPoint(s.p2, color); const cp1 = this.convert(s.p1); const cp2 = this.convert(s.p2); this.ctx.beginPath(); this.ctx.moveTo(cp1.x, cp1.y); this.ctx.lineTo(cp2.x, cp2.y); this.ctx.strokeStyle = color; this.ctx.lineWidth = 1; this.ctx.stroke(); } drawPoint(p, color) { const cp = this.convert(p); this.ctx.beginPath(); this.ctx.arc(cp.x, cp.y, 3, 0, Math.PI * 2, false); this.ctx.fillStyle = color; this.ctx.strokeStyle = color; this.ctx.stroke(); this.ctx.fill(); } drawText(text, p, color) { this.ctx.fillStyle = color; this.ctx.font = "12px Arial"; this.ctx.fillText(text, p.x, p.y); } drawGrid() { this.ctx.beginPath(); for (let x = this.origin.x; x < this.width; x += this.scale) { this.ctx.moveTo(x, 0); this.ctx.lineTo(x, this.height); } for (let x = this.origin.x; x > 0; x -= this.scale) { this.ctx.moveTo(x, 0); this.ctx.lineTo(x, this.height); } for (let y = this.origin.y; y < this.height; y += this.scale) { this.ctx.moveTo(0, y); this.ctx.lineTo(width, y); } for (let y = this.origin.y; y > 0; y -= this.scale) { this.ctx.moveTo(0, y); this.ctx.lineTo(this.width, y); } this.ctx.strokeStyle = '#ccc'; this.ctx.stroke(); } drawAxes() { this.ctx.beginPath(); this.ctx.moveTo(0, this.origin.y); this.ctx.lineTo(this.width, this.origin.y); this.ctx.moveTo(this.origin.x, 0); this.ctx.lineTo(this.origin.x, this.height); this.ctx.strokeStyle = 'black'; this.ctx.lineWidth = 1; this.ctx.stroke(); } }32:[] 2d:{"title":"Line Segment Merging v2","cells":[{"id":0,"value":"md`# Line Segment Merging v2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":96,"value":"md`Let *s₁* and *s₂* be two segments to be merged.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":117,"value":"{ \n const width = 150;\n const height = 75;\n const scale = 10;\n const origin = v(75, 37.5);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(s1, 'green');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":74,"value":"s1 = s(v(-4, -3), v(4, -1))","pinned":true,"hidden":false,"mode":"ojs"},{"id":122,"value":"{ \n const width = 150;\n const height = 75;\n const scale = 10;\n const origin = v(75, 37.5);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(s2, 'blue');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"s2 = s(v(-3, 3), v(3, 2))","pinned":true,"hidden":false,"mode":"ojs"},{"id":108,"value":"md`Merging them results in a new segment that we call *s_m*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"{ \n const width = 300;\n const height = 200;\n const scale = 20;\n const origin = v(width / 2, height / 2);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(s1, 'green');\n fig.drawSegment(s2, 'blue');\n fig.drawSegment(sm, 'red');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"sm = merge(s1, s2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`The algorithm also works for non-overlapping line segments:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":136,"value":"{\n const sa = s(v(-6, -3), v(-1, -1));\n const sb = s(v(0, 3), v(6, 2));\n const smm = merge(sa, sb);\n \n const width = 300;\n const height = 200;\n const scale = 20;\n const origin = v(width / 2, height / 2);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(sa, 'green');\n fig.drawSegment(sb, 'blue');\n fig.drawSegment(smm, 'red');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":143,"value":"md`And for partially overlapping ones:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":148,"value":"{\n const sa = s(v(-5, -3), v(1, -1));\n const sb = s(v(-2, 3), v(6, 2));\n const smm = merge(sa, sb);\n \n const width = 300;\n const height = 200;\n const scale = 20;\n const origin = v(width / 2, height / 2);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(sa, 'green');\n fig.drawSegment(sb, 'blue');\n fig.drawSegment(smm, 'red');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":170,"value":"md`Try moving the sliders below to change the green segment on the next figure.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"viewof sa = xySlider({\n min: -7,\n max: 7,\n xstep: .2,\n ystep: .2,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":229,"value":"sa","pinned":false,"hidden":false,"mode":"ojs"},{"id":220,"value":"viewof sb = xySlider({\n min: -7,\n max: 7,\n xstep: .2,\n ystep: .2,\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":232,"value":"sb","pinned":false,"hidden":false,"mode":"ojs"},{"id":173,"value":"{\n const seg1 = s(v(sa[0], sa[1]), v(sb[0], sb[1]));\n const seg2 = s(v(-2, 3), v(6, 2));\n const smm = merge(seg1, seg2);\n \n const width = 300;\n const height = 200;\n const scale = 20;\n const origin = v(width / 2, height / 2);\n const ctx = DOM.context2d(width, height);\n const fig = new Figure({ ctx, scale, origin, width, height });\n fig.drawSegment(seg1, 'green');\n fig.drawSegment(seg2, 'blue');\n fig.drawSegment(smm, 'red');\n return fig.canvas();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":19,"value":"function v(x, y) {\n return new Vector(x, y);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"function s(p1, p2) {\n return new Segment(p1, p2);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":56,"value":"function merge(s1, s2) {\n const c = centroid(s1, s2);\n const a = mergeAngle(s1, s2);\n const xs = [s1.p1, s1.p2, s2.p1, s2.p2]\n .map(p => p.translate(c).rotate(a))\n .reduce(\n ({ min, max }, p) => ({ min: p.x < min ? p.x : min, max: p.x > max ? p.x : max }),\n { min: s1.p1.x, max: s1.p1.x });\n const tp1 = new Vector(xs.min, 0);\n const tp2 = new Vector(xs.max, 0);\n return new Segment(\n tp1.rotate(-a).add(c),\n tp2.rotate(-a).add(c)\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"function mergeAngle(s1, s2) {\n return Math.abs(s1.angle - s2.angle) <= Math.PI / 2\n ? (s1.angle * s1.length + s2.angle * s2.length) / (s1.length + s2.length)\n : (s1.angle * s1.length + (s2.angle - Math.PI * (s2.angle / Math.abs(s2.angle))) * s2.length) / (s1.length + s2.length);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"function centroid(s1, s2) {\n const sl = s1.length + s2.length;\n const cx = (s1.length * (s1.p1.x + s1.p2.x) + s2.length * (s2.p1.x + s2.p2.x)) / sl;\n const cy = (s1.length * (s1.p1.y + s1.p2.y) + s2.length * (s2.p1.y + s2.p2.y)) / sl;\n return new Vector(cx, cy);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"function toFixedRound(n, fractionDigits) {\n\tconst factor = Math.pow(10, fractionDigits);\n\treturn (Math.round(n * factor) / factor).toFixed(fractionDigits);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"function rad2deg(r) {\n return r * 180 / Math.PI;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"import {xySlider} from \"98bbb19bf9e859ee\";","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}