31:T523,/** Reorder paths greedily, attempting to minimize the amount of pen-up travel time. */ function reorder(pointLists) { if (pointLists.length === 0) { return pointLists; } const pt = i => i % 2 === 0 ? pointLists[(i / 2)|0][0] : pointLists[(i / 2)|0][pointLists[(i / 2)|0].length - 1] class PointRBush extends RBush { toBBox(i) { const {x, y} = pt(i); return {minX: x, minY: y, maxX: x, maxY: y}; } compareMinX(a, b) { return pt(a).x - pt(b).x; } compareMinY(a, b) { return pt(a).y - pt(b).y; } } const tree = new PointRBush() tree.load([...range(2, pointLists.length * 2)]) const sortedPointLists = []; sortedPointLists.push(pointLists[0]); let cur = pt(1) // end of first segment let n = pointLists.length * 2 - 2 while (n) { const [nn] = knn(tree, cur.x, cur.y, 1) const plId = (nn/2)|0 // path Id tree.remove(plId * 2) tree.remove(plId * 2 + 1) sortedPointLists.push( nn % 2 === 0 ? pointLists[plId] : pointLists[plId].slice().reverse() ) // if nn corresponds to the beginning of a path, next search is from end of the path // if nn corresponds to the end of a path, next search is from beginning of the path cur = pt(nn % 2 === 0 ? nn + 1 : nn - 1) n -= 2 } return sortedPointLists }32:[] 2f:{"title":"saxi paths optimization study","cells":[{"id":0,"value":"# saxi paths optimization study","pinned":false,"hidden":false,"mode":"md"},{"id":6,"value":"- https://github.com/nornagon/saxi\n- https://github.com/nornagon/optimize-paths\n- https://github.com/mourner/rbush\n- https://github.com/mourner/rbush-knn","pinned":false,"hidden":false,"mode":"md"},{"id":35,"value":"___","pinned":false,"hidden":false,"mode":"md"},{"id":64,"value":"## Creating Paths","pinned":false,"hidden":false,"mode":"md"},{"id":8,"value":"paths = {\n const paths = []\n\n const margin = 20\n const N = 10\n for(let i = 0; i < N; i ++) {\n paths.push([{x: margin, y: map(i, 0, N-1, margin, h - margin)}, {x: w/3 - margin, y: map(i, 0, N-1, margin, h - margin)}])\n }\n \n for(let i = 0; i < N; i ++) {\n paths.push([{x: map(i, 0, N-1, w/3+margin, 2*w/3 - margin), y: margin}, {x: map(i, 0, N-1, w/3+margin, 2*w/3 - margin), y: h-margin}])\n }\n\n for(let i = 0; i < N; i ++) {\n paths.push([{x: randInt(2 * w / 3 + margin, w - margin), y: randInt(margin, h - margin)}, {x: randInt(2 * w / 3 + margin, w - margin), y: randInt(margin, h - margin)}])\n }\n \n return paths\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":189,"value":"Taking paths in the order they were created.","pinned":false,"hidden":false,"mode":"md"},{"id":72,"value":"## Reordered Paths using @nornagon/optimize-paths","pinned":false,"hidden":false,"mode":"md"},{"id":20,"value":"optimizePaths = import('https://cdn.skypack.dev/optimize-paths@1.2.1?min')","pinned":true,"hidden":false,"mode":"ojs"},{"id":58,"value":"reorderedPaths = optimizePaths.reorder(paths)","pinned":true,"hidden":false,"mode":"ojs"},{"id":66,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":187,"value":"Only the first pen up is correct, then the next ones are going to closest point from beginning of the path","pinned":false,"hidden":false,"mode":"md"},{"id":84,"value":"## Reordered Paths using custom implementation","pinned":false,"hidden":false,"mode":"md"},{"id":25,"value":"RBush = require('rbush')","pinned":true,"hidden":false,"mode":"ojs"},{"id":91,"value":"knn = require('rbush-knn')","pinned":true,"hidden":false,"mode":"ojs"},{"id":155,"value":"function* range(lo, hi) {\n for (let i = lo; i < hi; i++) yield i\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":103,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":109,"value":"customReorderedPaths = reorder(paths)","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"___\n## Globals","pinned":false,"hidden":false,"mode":"md"},{"id":10,"value":"h = 300","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"w = width","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"___\n## Imports","pinned":false,"hidden":false,"mode":"md"},{"id":15,"value":"import {randInt, map} from '@makio135/utilities'","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}