2d:null 2e:["$","title",null,{"children":"Line interpolator | Tom Kristian Tjemsland | Observable"}] 33:T1948,class LineInterpolator { constructor(points) { const amount = points.length; // Amount of points // Path with pre-defined length const path = new Array(amount); // Set first point path[0] = { point: points[0], distance: 0, relative: 0, } // Total length of line let length = 0; for(let i = 1; i < amount; i++) { const point = points[i]; length += Vector2.dist(point, path[i - 1].point); path[i] = { point, distance: length, // Distance to point along line (in world units) }; } // Re-iterate over path to calculate relative distances for(let i = 1; i < amount; i++) { const p = path[i]; p.relative = length === 0 ? 0 : p.distance / length; } this.amount = amount; this.length = length; // Is the "line" actually a single point this.singlePoint = (length <= 0.001); // Set path for interpolator this.path = path; } // Get point at relative position // NB: Relative has to be between 0 and 1. GetPoint(relative) { // Return first point if line has no length if(this.singlePoint) { return { pos: this.path[0].point, dir: Vector2.Up, dist: 0 }; } let base = 0; let range = this.amount; let idx = Math.floor(range / 2); // Find target sub-section using divide-and-conquer algorithm while(range > 10) { if(relative < this.path[idx].relative) { range = Math.floor(range / 2); idx = base + Math.floor(range / 2); } else { base += Math.floor(range / 2); range = Math.ceil(range / 2); idx = base + Math.floor(range / 2); } } const target = base + range; for(let i = base + 1; i <= target; i++) { const cur = this.path[i]; if (cur.relative >= relative) { // Between points const prev = this.path[i - 1]; const dist = cur.relative - prev.relative; const frac = (relative - prev.relative) / dist; return { pos: Vector2.lerp(prev.point, cur.point, frac), dir: Vector2.sub(cur.point, prev.point).normalized, dist: prev.distance * (1 - frac) + cur.distance * frac, }; } } } // Get section at relative position // NB: Relative has to be between 0 and 1. // Each point have position, direction and distance to point. { pos: __, dir: __, dist: __ } GetSection(relativeStart, relativeEnd) { // Return two points if line has no length if(this.singlePoint) { return [ { pos: this.path[0].point, dir: Vector2.Up, dist: 0 }, { pos: this.path[0].point, dir: Vector2.Up, dist: 0 }, ]; } let base = 0; let range = this.amount; let idx = Math.floor(range / 2); // Find target sub-section using divide-and-conquer algorithm while(range > 10) { if(relativeStart < this.path[idx].relative) { range = Math.floor(range / 2); idx = base + Math.floor(range / 2); } else { base += Math.floor(range / 2); range = Math.ceil(range / 2); idx = base + Math.floor(range / 2); } } const points = []; let started = false; for(let i = base + 1; i < this.amount; i++) { const cur = this.path[i]; if (!started && cur.relative >= relativeStart) { // Between points const prev = this.path[i - 1]; const dist = cur.relative - prev.relative; const frac = (relativeStart - prev.relative) / dist; const prevDir = this.GetDirection(i - 1); const curDir = this.GetDirection(i); points.push({ pos: Vector2.lerp(prev.point, cur.point, frac), dir: Vector2.rotationLerp(prevDir, curDir, frac).normalized, // Interpolate direction dist: prev.distance * (1 - frac) + cur.distance * frac, // Interpolate distance }); // Push first point started = true; } if(!started) continue; // Don't continue if not started if (cur.relative >= relativeEnd) { // Between points const prev = this.path[i - 1]; const dist = cur.relative - prev.relative; const frac = (relativeEnd - prev.relative) / dist; const prevDir = this.GetDirection(i - 1); const curDir = this.GetDirection(i); points.push({ pos: Vector2.lerp(prev.point, cur.point, frac), dir: Vector2.rotationLerp(prevDir, curDir, frac).normalized, // Interpolate direction dist: prev.distance * (1 - frac) + cur.distance * frac, // Interpolate distance }); // Push last point break; } points.push({ pos: cur.point, dir: this.GetDirection(i), dist: cur.distance, }); // Add points between } return points; } // Get point with given distance from start in world space GetPointFromStart(distance) { let relative = distance / this.length; if (relative < 0) relative = 0; if (relative > 1) relative = 1; return this.GetPoint(relative); } // Get point with given distance from the end in world space GetPointFromEnd(distance) { let relative = 1 - (distance / this.length); if (relative < 0) relative = 0; if (relative > 1) relative = 1; return this.GetPoint(relative); } // Get collection of equally space points with given width in real distance GetRangeFromStart(relative, width, resolution = 10) { const relativeEnd = relative + (width / this.length); const relativeDisp = (relativeEnd - relative) / resolution; const points = []; for(let i = 0; i <= resolution; i++) { points.push(this.GetPoint(relative + relativeDisp * i)); } return points; } // Get direction at index GetDirection(idx) { const end = this.amount - 1; if (idx === 0) { // If first return Vector2.sub(this.path[1].point, this.path[0].point).normalized; } // If last else if (idx === end) { return Vector2.sub(this.path[end].point, this.path[end - 1].point).normalized; } else { const cur = this.path[idx].point; // Current point const to = Vector2.sub(cur, this.path[idx - 1].point); // Direction to current const from = Vector2.sub(this.path[idx + 1].point, cur); // Direction from current return Vector2.rotationLerp(to, from, 0.5).normalized; // Rotate halfway } } }34:T6f2,{ const points = []; const center = new Vector2(250, 250); // Generate a set of points along a circle for(let i = 0; i <= 260; i += 20) { points.push( Vector2.Right .rotate(i) .rescale(200) .add(center) ); } // Create the line interpolator const interp = new LineInterpolator(points); const svg = d3.create('svg') // .style('background-color', 'red').style('opacity', .5) .attr('width', '500px') .attr('height', '500px') const line = interp.GetSection(0.5, 0.75); for (let i = 1; i < line.length; i++) { // Iterate over line points const cur = line[i]; const prev = line[i - 1]; svg.append('line') .attr('x1', prev.pos.x) .attr('y1', prev.pos.y) .attr('x2', cur.pos.x) .attr('y2', cur.pos.y) .attr('stroke', 'OliveDrab') .attr('stroke-width', 2) } line.forEach(l => { if (!l.dir) return; const nrm =l.dir.rotate90(); svg.append('line') .attr('x1', l.pos.x) .attr('y1', l.pos.y) .attr('x2', l.pos.x + nrm.x * 30) .attr('y2', l.pos.y + nrm.y * 30) .attr('opacity', 0.4) .attr('stroke', 'FireBrick') .attr('stroke-width', 2) }); // Draw general points points.forEach(p => { svg.append('circle') .attr('cx', p.x) .attr('cy', p.y) .attr('r', 5) .attr('fill', 'DimGrey') }); const point2 = interp.GetPoint(0.25).pos; svg.append('circle') .attr('cx', point2.x) .attr('cy', point2.y) .attr('r', 5) .attr('fill', 'SteelBlue'); const point3 = interp.GetPointFromEnd(100).pos; svg.append('circle') .attr('cx', point3.x) .attr('cy', point3.y) .attr('r', 5) .attr('fill', 'FireBrick'); return svg.node(); }35:T4f7,{ const points = []; // Generate a set of points along a circle for(let i = 20; i <= 780; i += 40) { points.push(new Vector2(i, 100 + 30 * Math.sin(i * .02))); } // Create the line interpolator const interp = new LineInterpolator(points); const svg = d3.create('svg') // .style('background-color', 'red').style('opacity', .5) .attr('width', '800px') .attr('height', '200px') // Draw general points points.forEach(p => { svg.append('circle') .attr('cx', p.x) .attr('cy', p.y) .attr('r', 5) .attr('fill', 'DimGrey') }); for(let i = 0.1; i <= 0.9; i += 0.1) { const point = interp.GetPoint(i); const pos = point.pos; const dir = point.dir.rescale(2); const norm = dir.rotate90().rescale(40); // Rotate direction and rescale // Calculate points const ll = pos.sub(dir).sub(norm); // Lower left const lr = pos.add(dir).sub(norm); // Lower right const ur = pos.add(dir).add(norm); // Upper right const ul = pos.sub(dir).add(norm); // Upper left svg.append('polygon') .attr('points', `${ll.x},${ll.y} ${lr.x},${lr.y} ${ur.x},${ur.y} ${ul.x},${ul.y}`) .attr('fill', 'White') .attr('fill', 'OliveDrab') } return svg.node(); }36:T432,{ const points = []; // Generate a set of points along a circle for(let i = 20; i <= 780; i += 20) { points.push(new Vector2(i, 100 + 30 * Math.sin(i * .02))); } // Create the line interpolator const interp = new LineInterpolator(points); const svg = d3.create('svg') // .style('background-color', 'red').style('opacity', .5) .attr('width', '800px') .attr('height', '200px') const range = interp.GetRangeFromStart(0.1, 300, 21); range.forEach(p => { svg.append('circle') .attr('cx', p.pos.x) .attr('cy', p.pos.y - 40) .attr('r', 5) .attr('fill', 'OliveDrab') }) const range2 = interp.GetRangeFromStart(0.52, 300, 7); range2.forEach(p => { svg.append('circle') .attr('cx', p.pos.x) .attr('cy', p.pos.y - 40) .attr('r', 5) .attr('fill', 'FireBrick') }) // Draw general points points.forEach(p => { svg.append('circle') .attr('cx', p.x) .attr('cy', p.y) .attr('r', 5) .attr('fill', 'DimGrey') }); return svg.node(); }37:[] 31:{"id":"0dce7214a7a7f214","slug":"line-interpolator","title":"Line interpolator","thumbnail":"49420aabfaa3c4cb548d85d2f716aacc5f50e786f0eddec3066f636e43541516","access_level":"public","create_time":"$D2019-09-16T12:59:25.857Z","update_time":"$D2019-11-12T13:42:36.972Z","view_time":null,"first_public_time":"$D2019-09-16T13:02:12.738Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"a49ab297471727ef","login":"tomktjemsland","name":"Tom Kristian Tjemsland","avatar_url":"https://avatars-next.observableusercontent.com/271d0fc197b9153a9c5a4aa29d3f170cbe6d604ab2969e36da2635c2ea6021dd","tier":"starter_2024"},"version":605,"publish_version":605,"role":null,"authored":false,"authors":[{"type":"individual","id":"e44acfdca79f4aeb","login":"tomktjemsland","name":"Tom Kristian Tjemsland","avatar_url":"https://avatars-next.observableusercontent.com/271d0fc197b9153a9c5a4aa29d3f170cbe6d604ab2969e36da2635c2ea6021dd","tier":null}],"members":[{"type":"individual","id":"e44acfdca79f4aeb","login":"tomktjemsland","name":"Tom Kristian Tjemsland","avatar_url":"https://avatars-next.observableusercontent.com/271d0fc197b9153a9c5a4aa29d3f170cbe6d604ab2969e36da2635c2ea6021dd","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Line interpolator","cells":[{"id":0,"value":"md`# Line interpolator`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"md`Get points or subsections of a line defined through an array of points. Utilized the divide-and-conquer algorithm to speed up search.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"md`## To import:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"GetClipboardNode(\"import { LineInterpolator } from '@tomktjemsland/line-interpolator'\", 'SteelBlue');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"md`## Class:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"md`## Example:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"md`Drawing a blue point at 25% of path and a green line between 50%-75%. Red lines shows normals of line. The last red point is approximately 200 pixels away from the end of the path.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":513,"value":"md`Apply ticks along a sinus curve using point and direction read from the interpolator.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":458,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":585,"value":"md`Selection of approximately 300px along line with linear spacing. Green points have three times higher resolution as the red ones. Section have been drawn above line for visibility.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md`## Imports:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"import { Vector2 } from '@tomktjemsland/vector2'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"import { GetClipboardNode } from '@tomktjemsland/copy-to-clipboard'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"d3 = require('d3@5');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 32:"$31:body"