У меня есть плоский список прямоугольников в следующем формате (идентификатор, координата x, координата y, высота и ширина):
[ { id: 4206, x: 360, y: 700, width: 60, height: 50 } ,
{ id: 6621, x: 1260, y: 1100, width: 60, height: 50 } ]
Я хочу проиндексировать это по диапазону значений X, а затем использовать этот индексированный объект, чтобы ускорить поиск точки внутри.
Мой полный код здесь:
// arbitrary setup, no need to review
const grid = [];
const height = 50;
const width = 60;
let index = 0;
for (let row = 0; row < 300; row++) {
for (let col = 0; col < 300; col++) {
grid[index] = {
id: index,
x: width * col,
y: height * row,
width,
height
};
index++;
}
}
// try and find these points
const points = [{
x: 400,
y: 700
}, {
x: 1300,
y: 1105
}]
// body - please review approach, style less important
const indexedGrid = grid.reduce((acc, curr) => {
if (curr.x === undefined) return acc;
if (acc[curr.x]) {
acc[curr.x].shapes.push(curr);
acc[curr.x].endEdge = Math.max(acc[curr.x].endEdge, curr.width + curr.x)
} else acc[curr.x] = {
shapes: [curr],
startEdge: curr.x,
endEdge: curr.width + curr.x
};
return acc;
}, {})
const indexedEdges = Object.values(indexedGrid).map(val => ({
start: val.startEdge,
end: val.endEdge
}));
const shapesContainingPoints = points.map(
(point) => ({
point,
xRange: indexedEdges.filter(
edge => (point.x >= edge.start && point.x < edge.end)
)
})
).map(
pointWithRange => indexedGrid[pointWithRange.xRange[0].start].shapes.filter(
shape => {
return (pointWithRange.point.y >= shape.y && (pointWithRange.point.y < (shape.y + shape.height)))
}
)
);
//footer - purely to show results in the this question, no need to review
console.log(shapesContainingPoints)Я полностью осознаю, что этот код можно сильно привести в порядок, но главное, что я надеялся выяснить, это то, подходит ли этот шаблон «индекс и поиск» для следующего варианта использования.
Я рисую кучу прямоугольников в html canvas элемент, и я хочу найти, какой прямоугольник был нажат, используя x, y коорды мыши. Поэтому я планирую создать плоский список квадратов, а затем проиндексировать их по значению X. И от этого значения X просмотрите строку, фильтруя по значению Y.
В настоящее время данные включают только идеально расположенные прямоугольники, но в будущем мне, возможно, придется обрабатывать чередующееся смещение (каждая вторая строка смещается на небольшое значение) или другие менее стандартные макеты.
Но это кажется очень неуклюжим, и что должен быть лучший подход к этой проблеме? Если нет, можно ли как-нибудь улучшить мой нынешний подход?