Graphics Developer, Creative Coder, DataViz Cognoscenti
Published
Edited
Mar 30, 2022
3 stars
Point Finding Algorithms Comparison
{
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`
<div>Number of points: ${d3.format(`,.0f`)(numPoints)}</div>
<div>Iterations: ${d3.format(`,.0f`)(iterations.length)}</div>
<div style="height: 2rem;"></div>
<div>Delaunay initialization: ${d3.format(`,.0f`)(delaunayInitTime)}ms</div>
<div>Delaunay search: ${d3.format(`,.0f`)(delaunaySearchTime)}ms</div>
<div style="height: 2rem;"></div>
<div>Bisector initialization (array sort): ${d3.format(`,.0f`)(
arraySortTime
)}ms</div>
<div>Bisector search: ${d3.format(`,.0f`)(bisectorTime)}ms</div>
<div style="height: 2rem;"></div>
<div>Flatbush initialization: ${d3.format(`,.0f`)(flatbushInitTime)}ms</div>
<div>Flatbush search: ${d3.format(`,.0f`)(flatbushTime)}ms</div>
<div style="height: 2rem;"></div>
<div>Array search: ${
arraySearchTime
? d3.format(`,.0f`)(arraySearchTime) + `ms`
: `way too long`
}</div>
`;
}
function fastFinder(data, xAccessor = (d) => d[0], yAccessor = (d) => d[1]) {
const sorted = [...data].sort((a, b) =>
d3.ascending(xAccessor(a), xAccessor(b))
);
const bisect = d3.bisector(xAccessor);
return function find(x, y) {
const index = bisect.left(sorted, x);
let minPoint = null;
let minDist = Infinity;
let lxDist = 0;
let rxDist = 0;
let i = 0;
while (lxDist < minDist && rxDist < minDist) {
lxDist = checkPoint(sorted[index - i]);
rxDist = checkPoint(sorted[index + i]);
i++;
}
function checkPoint(d) {
if (!d) return Infinity;
const dx = d.x - x;
const dy = d.y - y;
const dist = Math.sqrt(dx * dx + dy * dy);
if (dist < minDist) {
minDist = dist;
minPoint = d;
}
return Math.abs(x - d.x);
}
return minPoint;
};
}
Flatbush = require("flatbush@3")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
