2d:null 2e:["$","title",null,{"children":"Line reducer | Tom Kristian Tjemsland | Observable"}] 33:T464,{ const width = 500; const height = 500; const root = d3.create('div'); const reduced = ReduceLine(data, targetMaxDeviation, targetDistanceWeight); const output = root.append('div') .style('height', '25px') .text(`Points: ${reduced.length}`); const svg = root.append('svg') .style('width', `${width}px`) .style('height', `${height}px`) .style('border', '2px dotted DimGrey') let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity; reduced.forEach(d => { if (d.x < minX) minX = d.x; if (d.y < minY) minY = d.y; if (d.x > maxX) maxX = d.x; if (d.y > maxY) maxY = d.y; }); const xRange = maxX - minX; const yRange = maxY - minY; for (let i = 0; i < reduced.length; i++) { const entry = reduced[i]; const x = (width - 50) * (entry.x - minX) / xRange + 25; const y = (height - 50) * (entry.y - minY) / yRange + 25; svg.append('circle') .attr('cx', x) .attr('cy', y) .attr('r', 2) .attr('fill', d3.interpolateRainbow(i / reduced.length)); } return root.node(); }34:T911,{ const width = 500; const height = 500; const root = d3.create('div'); const output = root.append('div') .style('height', '25px'); const deviation = root.append('div') .style('height', '25px'); const performanceNode = root.append('div') .style('height', '25px'); const svg = root.append('svg') .style('width', `${width}px`) .style('height', `${height}px`) .style('border', '2px dotted DimGrey') .on("wheel", () => d3.event.preventDefault()) .call(d3.zoom() .extent([[0, 0], [width, height]]) .scaleExtent([1, 8]) .on("zoom", zoomed)); const container = svg.append('g'); function zoomed() { container.attr("transform", d3.event.transform); } let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity; data.forEach(d => { if (d.x < minX) minX = d.x; if (d.y < minY) minY = d.y; if (d.x > maxX) maxX = d.x; if (d.y > maxY) maxY = d.y; }); const xRange = maxX - minX; const yRange = maxY - minY; const a = data.map(d => new Vector2( (width - 50) * (d.x - minX) / xRange + 25, (height - 50) * (d.y - minY) / yRange + 25, )); for (let i = 1; i < a.length; i++) { const {x: x1, y: y1} = a[i - 1]; const {x: x2, y: y2} = a[i]; container.append('line') .attr('x1', x1) .attr('y1', y1) .attr('x2', x2) .attr('y2', y2) .attr('stroke', 'Red'); } const t0 = performance.now(); const reduced = ReduceLineWithStats(data, targetMaxDeviation, targetDistanceWeight); const t1 = performance.now(); reduced.points = reduced.points.map(d => new Vector2( (width - 50) * (d.x - minX) / xRange + 25, (height - 50) * (d.y - minY) / yRange + 25, )); for (let i = 1; i < reduced.points.length; i++) { const {x: x1, y: y1} = reduced.points[i - 1]; const {x: x2, y: y2} = reduced.points[i]; container.append('line') .attr('x1', x1) .attr('y1', y1) .attr('x2', x2) .attr('y2', y2) .attr('stroke', 'Blue'); } output.text(`Compression: ${(reduced.compression).toFixed(2)} %`); deviation.text(`Total deviation: ${reduced.deviation.toFixed(5)}`); performanceNode.text(`Performance: ${(t1 - t0).toFixed(4)} ms`); return root.node(); }35:T97f,{ const width = 500; const height = 500; const root = d3.create('div'); const output = root.append('div') .style('height', '25px'); const deviation = root.append('div') .style('height', '25px'); const performanceNode = root.append('div') .style('height', '25px'); const pointsNode = root.append('div') .style('height', '25px'); const svg = root.append('svg') .style('width', `${width}px`) .style('height', `${height}px`) .style('border', '2px dotted DimGrey') .on("wheel", () => d3.event.preventDefault()) .call(d3.zoom() .extent([[0, 0], [width, height]]) .scaleExtent([1, 8]) .on("zoom", zoomed)); const container = svg.append('g'); function zoomed() { container.attr("transform", d3.event.transform); } let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity; data.forEach(d => { if (d.x < minX) minX = d.x; if (d.y < minY) minY = d.y; if (d.x > maxX) maxX = d.x; if (d.y > maxY) maxY = d.y; }); const xRange = maxX - minX; const yRange = maxY - minY; const a = data.map(d => new Vector2( (width - 50) * (d.x - minX) / xRange + 25, (height - 50) * (d.y - minY) / yRange + 25, )); for (let i = 1; i < a.length; i++) { const {x: x1, y: y1} = a[i - 1]; const {x: x2, y: y2} = a[i]; container.append('line') .attr('x1', x1) .attr('y1', y1) .attr('x2', x2) .attr('y2', y2) .attr('stroke', 'Red'); } const t0 = performance.now(); const reduced = ReduceLineOptimalWithStats(data, 0.001); const t1 = performance.now(); reduced.points = reduced.points.map(d => new Vector2( (width - 50) * (d.x - minX) / xRange + 25, (height - 50) * (d.y - minY) / yRange + 25, )); for (let i = 1; i < reduced.points.length; i++) { const {x: x1, y: y1} = reduced.points[i - 1]; const {x: x2, y: y2} = reduced.points[i]; container.append('line') .attr('x1', x1) .attr('y1', y1) .attr('x2', x2) .attr('y2', y2) .attr('stroke', 'Blue'); } output.text(`Compression: ${(reduced.compression).toFixed(2)} %`); deviation.text(`Total deviation: ${reduced.deviation.toFixed(5)}`); performanceNode.text(`Performance: ${(t1 - t0).toFixed(4)} ms`); pointsNode.text(`Amount of points: ${reduced.points.length}`); return root.node(); }36:T5fe,ReduceLineOptimal = (points, maxAbsoluteDeviation) => { let idx = 0; // Original index const _points = points.map(d => { return { point: d, index: idx++, consumed: [], // Points consumed. Increases deviation } }); let curDeviation = 0; while (_points.length > 3) { let minDeviation = Infinity; let minIndex = -1; // Index of point to remove // Get point in current line with the smallest deviation for (let i = 0; i < _points.length - 2; i++ ) { const lineStart = _points[i].point; const lineEnd = _points[i + 2].point; const middle = _points[i + 1].point; // Point in the middle let deviation = DistanceToVector(middle, lineStart, lineEnd); // Deviation of removing point _points[i + 1].consumed.forEach(idx => { // Also add deviation of all consumed points deviation += DistanceToVector(points[idx], lineStart, lineEnd); }) if (deviation < minDeviation) { minDeviation = deviation; minIndex = i + 1; } } curDeviation += minDeviation; if (curDeviation > maxAbsoluteDeviation) break; const originalIndex = _points[minIndex].index; const allConsumed = _points[minIndex].consumed; _points[minIndex - 1].consumed.push(originalIndex, ...allConsumed); // Push point and all consumed _points[minIndex + 1].consumed.push(originalIndex, ...allConsumed); // Push point and all consumed _points.splice(minIndex, 1); // Remove point } return _points.map(d => d.point); }37:T459,ReduceLineWithStats = (points, maxDeviation, distanceWeight) => { const output = [ points[0], points[1], ] let deviation = 0; // Initial direction let lineStart = points[0]; let lineEnd = points[1]; let endIndex = 1; // Index of end of current line for (let i = 2; i < points.length - 1; i++) { const cur = points[i]; // Also consider distance from vector origin const minDisp = DisplacementToVectorOrigin(cur, lineStart, lineEnd); if (minDisp.y > maxDeviation + minDisp.x * distanceWeight) { output.push(cur); lineStart = new Vector2(lineEnd.x, lineEnd.y); lineEnd = new Vector2(cur.x, cur.y); // Calculate deviation of omitted points for (let j = endIndex + 1; j < i - 1; j++) { deviation += DisplacementToVectorOrigin(points[j], lineStart, lineEnd).y; } endIndex = i; // Set index of end of new line } } output.push(points[points.length - 1]); // Add last return { points: output, compression: 100 * (points.length - output.length) / points.length, deviation }; }38:T690,ReduceLineOptimalWithStats = (points, maxAbsoluteDeviation) => { let idx = 0; // Original index const _points = points.map(d => { return { point: d, index: idx++, consumed: [], // Points consumed. Increases deviation } }); let curDeviation = 0; while (_points.length > 3) { let minDeviation = Infinity; let minIndex = -1; // Index of point to remove // Get point in current line with the smallest deviation for (let i = 0; i < _points.length - 2; i++ ) { const lineStart = _points[i].point; const lineEnd = _points[i + 2].point; const middle = _points[i + 1].point; // Point in the middle let deviation = DistanceToVector(middle, lineStart, lineEnd); // Deviation of removing point _points[i + 1].consumed.forEach(idx => { // Also add deviation of all consumed points deviation += DistanceToVector(points[idx], lineStart, lineEnd); }) if (deviation < minDeviation) { minDeviation = deviation; minIndex = i + 1; } } if (curDeviation + minDeviation > maxAbsoluteDeviation) break; curDeviation += minDeviation; const originalIndex = _points[minIndex].index; const allConsumed = _points[minIndex].consumed; _points[minIndex - 1].consumed.push(originalIndex, ...allConsumed); // Push point and all consumed _points[minIndex + 1].consumed.push(originalIndex, ...allConsumed); // Push point and all consumed _points.splice(minIndex, 1); // Remove point } return { points: _points.map(d => d.point), compression: 100 * (points.length - _points.length) / points.length, deviation: curDeviation, }; }39:Tfaa, data = [ [3.4367499974301623, 60.86898037484667], [3.436748235842518, 60.86898621640885], [3.436785246806324, 60.86898618602434], [3.436828483788195, 60.868983621510836], [3.4368935829390965, 60.86897739469481], [3.4372314148932936, 60.86893275271583], [3.437553744801757, 60.868885646407804], [3.438448465023187, 60.868738273647864], [3.4388390311491204, 60.86867235691149], [3.439105551107254, 60.8686243515381], [3.439974719225965, 60.86845433709043], [3.4410048301864036, 60.86825909935776], [3.4413692185832034, 60.86819173476462], [3.442172841759794, 60.8680504718452], [3.4425809544399995, 60.86797631633937], [3.4430029228452175, 60.86790561546882], [3.4438541194792704, 60.86777029098142], [3.4442956402610716, 60.867702484339944], [3.4447380510523353, 60.86763260830973], [3.445605498320151, 60.86748851009261], [3.446031340093747, 60.867419223372686], [3.446459415755324, 60.86735181331349], [3.4469064763415256, 60.867285954896346], [3.447790586191785, 60.86716288601697], [3.4490857145893115, 60.86697837538793], [3.4499964865511292, 60.866853945998784], [3.450411966200838, 60.86679536412269], [3.4508387442795434, 60.86672857290135], [3.453059214028834, 60.86637347533044], [3.4534666173143944, 60.86630449643786], [3.453925636396249, 60.8662140637208], [3.454318916276577, 60.86612322300243], [3.4547857864034044, 60.8660025939482], [3.455207968005576, 60.86588588536035], [3.4554094699002795, 60.86582657542475], [3.455623200207999, 60.86575977182935], [3.4558188946543633, 60.86569356770447], [3.4559961941054254, 60.8656285928231], [3.4562228587764414, 60.865539388609086], [3.456404772964813, 60.86546245647654], [3.456582403122878, 60.86538212690645], [3.45675556383816, 60.86529831076285], [3.456923145324603, 60.86521065270312], [3.457084971160165, 60.86511969204173], [3.4572430844632493, 60.865026678807496], [3.457408247245172, 60.86492457339127], [3.4575780518250285, 60.864812396350345], [3.4577111151813487, 60.86471883929095], [3.4578510464320518, 60.86461637026281], [3.457987086226828, 60.864512208469925], [3.4581075523975398, 60.86441339673828], [3.4582395507568844, 60.8642971278232], [3.458357087889058, 60.86418674390989], [3.4584774295405163, 60.86406656404884], [3.458582576347891, 60.863952451302296], [3.4586812570965, 60.863836834218844], [3.4587747656733123, 60.8637200675292], [3.458867026039251, 60.86359333918138], [3.4589295641029754, 60.86349948276192], [3.4594506337833977, 60.8626571608391], [3.4598661719935695, 60.8620057159268], [3.4602694559013543, 60.8613993823541], [3.4606753485117268, 60.86082185871659], [3.4608631998313664, 60.86055905037312], [3.4610426487206807, 60.86031377813448], [3.4613726590245997, 60.85983751762278], [3.4615292217872033, 60.85958864211474], [3.4622362224019647, 60.85836131152967], [3.462510214514949, 60.857858036417284], [3.462890425442742, 60.85712706578874], [3.463019198212786, 60.856892918586134], [3.4631717733234284, 60.856624751476424], [3.4635874968000584, 60.85590775222027], [3.463682806785015, 60.8557529976553], [3.464087784432352, 60.85514691521877], [3.4644015509602717, 60.85468686359269], [3.464581819019507, 60.85441339171813], [3.464686712152235, 60.85426012958213], [3.4650750920460567, 60.85371766737113], [3.4652553946057534, 60.853472655489426], [3.465419595807141, 60.853234342989815], [3.4659730248467637, 60.85238766192515], [3.466537352451611, 60.85153312950666], [3.4666011819895868, 60.85143001715089], [3.4667453552384497, 60.85117004500807], [3.466992802654715, 60.85067277769758], [3.467122859461902, 60.85042955370075], [3.4675668661478456, 60.84966979606049], [3.4677069611941027, 60.84944664785258], [3.4678822830949976, 60.84919123472215], [3.4680642620820366, 60.84893822230587], [3.4682200266923884, 60.848730012683326], [3.4687916696401495, 60.84793110983396], ].map(d => new Vector2(d[0], d[1]));3a:[] 31:{"id":"1c48660909ebdf52","slug":"line-reducer","title":"Line reducer","thumbnail":"89d607ef4f55fa96640965d227a7a8f262814ae524e65cc731b3114a87e9fa2d","access_level":"public","create_time":"$D2019-09-23T13:03:27.960Z","update_time":"$D2020-02-14T11:03:06.048Z","view_time":null,"first_public_time":"$D2019-10-03T18:45:25.406Z","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":516,"publish_version":516,"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 reducer","cells":[{"id":0,"value":"md`# Line reducer`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"md`**Before** reduction:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"{\n const width = 500;\n const height = 500;\n \n const svg = new SimpleSVG(width, height, {\n border: '2px dotted DimGrey', \n });\n \n svg.addStaticLabel(`Points: ${data.length}`);\n \n let minX = Infinity;\n let minY = Infinity;\n let maxX = -Infinity;\n let maxY = -Infinity;\n \n data.forEach(d => {\n if (d.x < minX) minX = d.x;\n if (d.y < minY) minY = d.y;\n if (d.x > maxX) maxX = d.x;\n if (d.y > maxY) maxY = d.y;\n });\n \n const xRange = maxX - minX;\n const yRange = maxY - minY;\n \n svg.addStaticCircles(data, {\n x: d => (width - 50) * (d.x - minX) / xRange + 25,\n y: d => (height - 50) * (d.y - minY) / yRange + 25,\n r: 2,\n color: (d, i) => d3.interpolateRainbow(i / data.length),\n });\n \n return svg.node;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"md`**After** reduction:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":306,"value":"Slider({\n header: 'Max Deviation',\n min: 0.00001,\n max: 0.001,\n step: 0.00001,\n value: 0.00001,\n dualInput: true,\n},\n d => mutable targetMaxDeviation = d, \n);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"Slider({\n header: 'Distance weight',\n min: -1,\n max: 0.1,\n step: .01,\n value: 0,\n dualInput: true,\n},\n d => mutable targetDistanceWeight = d, \n);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"md`Overlapping:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":477,"value":"md`Compression with optimal solution. O(n^2).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":390,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"md`## Function:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"ReduceLine = (points, maxDeviation, distanceWeight) => {\n \n const output = [\n points[0],\n points[1],\n ]\n \n // Initial direction\n let lineStart = points[0];\n let lineEnd = points[1];\n \n for (let i = 2; i < points.length - 1; i++) {\n const cur = points[i];\n \n const minDisp = DisplacementToVectorOrigin(cur, lineStart, lineEnd);\n if (minDisp.y > maxDeviation + minDisp.x * distanceWeight) {\n output.push(cur);\n lineStart = new Vector2(lineEnd.x, lineEnd.y);\n lineEnd = new Vector2(cur.x, cur.y);\n }\n }\n \n output.push(points[points.length - 1]); // Add last\n \n return output;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"md`Finds the best possible solution under given max absolute deviation.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"md`## Extra Function:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"md`Returns statistics with generated line.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":248,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"md`## Example data:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":311,"value":"md`## Mutables:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"mutable targetMaxDeviation = 0;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":354,"value":"mutable targetDistanceWeight = 10;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"md`## Imports:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"import { Vector2 } from '@tomktjemsland/vector2'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"import { DistanceToVector, DisplacementToVectorOrigin } from '@tomktjemsland/distance-from-point-to-line'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":303,"value":"import { Slider } from '@tomktjemsland/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":155,"value":"import { SimpleSVG } from '@tomktjemsland/simple-svg'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"d3 = require('d3@5');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 32:"$31:body"