31:Tb0a,{ const random = d3.randomNormal(); let start; let delaunayInitTime = 0; let delaunaySearchTime = 0; let arraySortTime = 0; let arraySearchTime = 0; let bisectorTime = 0; let flatbushInitTime = 0; let flatbushTime = 0; const data = d3.range(numPoints).map((d) => ({ x: random(), y: random() })); const iterations = d3.range(numIterations); start = performance.now(); const delaunay = d3.Delaunay.from( data, (d) => d.x, (d) => d.y ); delaunayInitTime = performance.now() - start; start = performance.now(); for (const iter of iterations) { const x = random(); const y = random(); const foundIndex = delaunay.find(x, y); } delaunaySearchTime = performance.now() - start; if (numPoints < 50e3) { start = performance.now(); for (const iter of iterations) { const x = random(); const y = random(); var minPoint = d3.least(data, (d) => { const dx = d.x - x; const dy = d.y - y; return dx * dx + dy * dy; }); } arraySearchTime = performance.now() - start; } start = performance.now(); const find = fastFinder( data, (d) => d.x, (d) => d.y ); arraySortTime = performance.now() - start; start = performance.now(); for (const iter of iterations) { const x = random(); const y = random(); const foundPoint = find(x, y); } bisectorTime = performance.now() - start; start = performance.now(); const index = new Flatbush(data.length); for (const point of data) { index.add(point.x, point.y, point.x, point.y); } index.finish(); flatbushInitTime = performance.now() - start; start = performance.now(); for (const iter of iterations) { const x = random(); const y = random(); const foundIndex = index.neighbors(x, y, 1)[0]; const point = data[foundIndex]; } flatbushTime = performance.now() - start; return html`

Number of points: ${d3.format(`,.0f`)(numPoints)}

Iterations: ${d3.format(`,.0f`)(iterations.length)}

Delaunay initialization: ${d3.format(`,.0f`)(delaunayInitTime)}ms

Delaunay search: ${d3.format(`,.0f`)(delaunaySearchTime)}ms

Bisector initialization (array sort): ${d3.format(`,.0f`)( arraySortTime )}ms

Bisector search: ${d3.format(`,.0f`)(bisectorTime)}ms

Flatbush initialization: ${d3.format(`,.0f`)(flatbushInitTime)}ms

Flatbush search: ${d3.format(`,.0f`)(flatbushTime)}ms

Array search: ${ arraySearchTime ? d3.format(`,.0f`)(arraySearchTime) + `ms` : `way too long` }

`; }32:[] 2f:{"title":"Point Finding Algorithms Comparison","cells":[{"id":0,"value":"# Point Finding Algorithms Comparison","pinned":true,"hidden":false,"mode":"md"},{"id":98,"value":"viewof numPoints = Inputs.select([1e3, 50e3, 50e4, 1e6], {\n label: \"Number of points\",\n value: 1e6\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":103,"value":"viewof numIterations = Inputs.select([100, 1e3, 10e3], {\n label: \"Number of iterations\",\n value: 100\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":3,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":58,"value":"function fastFinder(data, xAccessor = (d) => d[0], yAccessor = (d) => d[1]) {\n const sorted = [...data].sort((a, b) =>\n d3.ascending(xAccessor(a), xAccessor(b))\n );\n const bisect = d3.bisector(xAccessor);\n return function find(x, y) {\n const index = bisect.left(sorted, x);\n\n let minPoint = null;\n let minDist = Infinity;\n let lxDist = 0;\n let rxDist = 0;\n let i = 0;\n\n while (lxDist < minDist && rxDist < minDist) {\n lxDist = checkPoint(sorted[index - i]);\n rxDist = checkPoint(sorted[index + i]);\n i++;\n }\n\n function checkPoint(d) {\n if (!d) return Infinity;\n const dx = d.x - x;\n const dy = d.y - y;\n const dist = Math.sqrt(dx * dx + dy * dy);\n if (dist < minDist) {\n minDist = dist;\n minPoint = d;\n }\n return Math.abs(x - d.x);\n }\n\n return minPoint;\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"Flatbush = require(\"flatbush@3\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}