2d:null 2e:["$","title",null,{"children":"Line Dictionary | Tom Kristian Tjemsland | Observable"}] 33:T10a0,{ const root = d3.create('div') root.append('div') .style('height', '25px') .style('font-weight', 'bold') .text('Using line dictionary:'); const segmentsDiv = root.append('div') .style('height', '25px'); const initializationDiv = root.append('div') .style('height', '25px'); const foundSegmentsDiv = root.append('div') .style('height', '25px') .text('Found segments: ---'); const lookupPerformanceDiv = root.append('div') .style('height', '25px') .text('Look-up performance: ---'); const getClosestDiv = root.append('div') .style('height', '25px') .text('Get closest performance: ---'); // Lines with ID to segments const fullLines = []; // List of line segments const lineSegments = []; let prevSelection = null; const init0 = performance.now(); // Init timer start const dict = new LineDictionary(-2); const firstLine = lines[0]; for (let n = 0; n < lines.length; n++) { const d = lines[n]; const segmentIDs = []; for (let i = 1; i < d.length; i++) { const p1 = d[i - 1]; const p2 = d[i]; // Append new line segments const segmentID = lineSegments.length; segmentIDs.push(segmentID); lineSegments.push({ segmentID, lineID: n, geometry: {x1: p1.x, y1: p1.y, x2: p2.x, y2: p2.y}, line: null, // Set later }); dict.add(p1.x, p1.y, p2.x, p2.y, segmentID); } fullLines.push(segmentIDs); }; const init1 = performance.now(); // Init timer end segmentsDiv.text(`Total segments: ${lineSegments.length}`); initializationDiv.text(`Initialization: ${(init1 - init0).toFixed(2)} ms`); const svg = root.append('svg') .style('width', `${width}px`) .style('height', `${height}px`) .style('border', '2px dotted DimGrey') .on('mouseout', () => { if (prevSelection) { prevSelection.forEach(d => { lineSegments[d].line.attr('stroke', 'SteelBlue'); }); } prevSelection = null; }) .on('mousemove', () => { // Undo previous selection if (prevSelection) { prevSelection.forEach(d => { lineSegments[d].line.attr('stroke', 'SteelBlue'); }); } const mousePos = d3.mouse(d3.event.target); const t0 = performance.now(); const linesOnTile = dict.getLinesOn3Grid(mousePos[0], mousePos[1]); const t1 = performance.now(); foundSegmentsDiv.text(`Found segments: ${linesOnTile.length}`); lookupPerformanceDiv.text(`Look-up performance: ${(t1 - t0).toFixed(2)} ms`); if(!linesOnTile) return; // Position as point const point = new Vector2(mousePos[0], mousePos[1]); const t2 = performance.now(); let minDist = Infinity; let minLineID = null; linesOnTile.forEach(d => { const seg = lineSegments[d]; const dist = DistanceToLine( point, new Vector2(seg.geometry.x1, seg.geometry.y1), new Vector2(seg.geometry.x2, seg.geometry.y2), ); if (dist < minDist) { minDist = dist; minLineID = seg.lineID; } }); const t3 = performance.now(); getClosestDiv.text(`Get closest performance: ${(t3 - t2).toFixed(2)} ms`); // Color all segments fullLines[minLineID].forEach(d => { lineSegments[d].line.attr('stroke', 'Tomato'); }); prevSelection = fullLines[minLineID]; }); // Line function function appendLine(x1, y1, x2, y2, color) { svg.append('line') .attr('x1', x1).attr('y1', y1) .attr('x2', x2).attr('y2', y2) .attr('stroke', color) .attr('pointer-events', 'none'); } // Append grid for (let x = 100; x < width; x+=100) appendLine(x, 0, x, height, 'LightGrey'); for (let y = 100; y < height; y+=100) appendLine(0, y, width, y, 'LightGrey'); lineSegments.forEach(d => { d.line = svg.append('line') .attr('x1', d.geometry.x1).attr('y1', d.geometry.y1) .attr('x2', d.geometry.x2).attr('y2', d.geometry.y2) .attr('stroke', 'SteelBlue') .attr('pointer-events', 'none'); }); return root.node(); }34:Tb5f,class LineDictionary { constructor(decimals = 0) { this.resolution = 10 ** decimals; this.lineSegments = []; // List of line segments } // Add a line section to the dictionary by start and end points add(x1, y1, x2, y2, val) { var tiles = {}; // Is line going down let downwards; // Coordinates for possible cross sections let xMin, xMax, yMin, yMax; // Line variables let m, y0; // Ensure data line is calculated left to right if(x1 < x2) { xMin = Math.floor(x1 * this.resolution); xMax = Math.floor(x2 * this.resolution); const deltaX = x2 - x1; const deltaY = y2 - y1; m = deltaY / deltaX; y0 = this.resolution * (y1 - x1 * m); downwards = y2 < y1; // Add first tiles[[Math.floor(x1 * this.resolution), Math.floor(y1 * this.resolution)]] = val; } else { xMin = Math.floor(x2 * this.resolution); xMax = Math.floor(x1 * this.resolution); const deltaX = x1 - x2; const deltaY = y1 - y2; m = deltaY / deltaX; y0 = this.resolution * (y2 - x2 * m); downwards = y1 < y2; // Add first tiles[[Math.floor(x2 * this.resolution), Math.floor(y2 * this.resolution)]] = val; } // Calculate y range if (y1 < y2) { yMin = Math.floor(y1 * this.resolution); yMax = Math.floor(y2 * this.resolution); } else { yMin = Math.floor(y2 * this.resolution); yMax = Math.floor(y1 * this.resolution); } // Iterate over x-crossing for (let x = xMin + 1; x <= xMax; x++) { const y = y0 + x * m; tiles[[x, Math.floor(y)]] = val; } // Iterate over y-crossing for (let y = yMin + 1; y <= yMax; y++) { const x = (y - y0) / m; tiles[[Math.floor(x), downwards ? y - 1 : y]] = val; } for (const key of Object.keys(tiles)) { // Attempt to get tile const tile = this[key]; // Append to tile if (tile) { tile.push(val); } else { this[key] = [val]; } } } // Get all lines registered on tile getLinesOnTile(x, y) { const key = [Math.floor(x * this.resolution), Math.floor(y * this.resolution)]; return this[key]; } // Get unique lines within a 3 x 3 grid getLinesOn3Grid(x, y) { const unique = {}; const lines = []; const keyX = Math.floor(x * this.resolution); const keyY = Math.floor(y * this.resolution); for (x = -1; x <= 1; x++) { for (y = -1; y <= 1; y++) { const key = [keyX + x, keyY + y]; const tile = this[key]; if (!tile) continue; tile.forEach(val => { // Iterate over values if(!unique.hasOwnProperty(val)) { lines.push(val); unique[val] = true; } }); } } return lines; } }35:[] 31:{"id":"76591f39836f0ead","slug":"line-dictionary","title":"Line Dictionary","thumbnail":"80e2f4e0761b7356db9bc0e84dc4d191041c058d3fb20fb694c7d152254973c3","access_level":"public","create_time":"$D2019-09-24T09:53:17.066Z","update_time":"$D2019-11-18T08:41:53.401Z","view_time":null,"first_public_time":"$D2019-10-03T18:42:31.920Z","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":404,"publish_version":404,"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 Dictionary","cells":[{"id":0,"value":"md`# Line Dictionary`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`Generates a dictionary with specified resolution. By default, x-y pairs, without decimals, are assigned as keys.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"md`## To import:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"GetClipboardNode(\"import { LineDictionary } from '@tomktjemsland/line-dictionary'\", 'SteelBlue');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"md`## Example:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"md`## Example data:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"singleLine = [\n [\n new Vector2(150, 640),\n new Vector2(520, 220),\n ],\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"lines = {\n \n // Simplex noise with random seed\n const simplexNoise = new SimplexNoise();\n \n const lines = [];\n \n // 100 perlin worms\n for (let i = 0; i < 100; i++) {\n \n // Random start position\n const baseX = Math.floor(10 + Math.random() * (width - 20));\n const baseY = Math.floor(10 + Math.random() * (height - 20));\n let pos = new Vector2(baseX, baseY);\n \n // Random direction\n let dir = Vector2.Right\n .rescale(10)\n .rotateRad(Math.random() * Math.PI * 2);\n \n // Add first\n const line = [\n pos\n ];\n \n // 50 iterations\n for (let j = 0; j < 50; j++) {\n pos = pos.add(dir);\n dir = dir.rotateRad(simplexNoise.noise2D(pos.x * 0.1, pos.y * 0.1));\n // Don't add line sections outside\n if (pos.x < 0 || pos.y < 0 || pos.x >= width || pos.y >= height) break; \n line.push(pos);\n }\n \n lines.push(line);\n }\n \n return lines;\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"md`## Class:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"md`## Mutables:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"mutable width = 700;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"mutable height = 700;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`## Imports:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"d3 = require('d3@5');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"import { Vector2 } from '@tomktjemsland/vector2'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"import { DistanceToLine } from '@tomktjemsland/distance-from-point-to-line'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"import { GetClipboardNode } from '@tomktjemsland/copy-to-clipboard'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"SimplexNoise = require('simplex-noise@2.4.0');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"