javascript - 检查对象数组中的值是否适合某个范围？

Question

我有一个对象数组。每个对象代表一个正在屏幕上绘制的正方形 - x/y 用于放置，s 用于大小，c 用于颜色)。

const elements = [
  { x: 0, y: 0, s: 20, c: 'red' },
  { x: 110, y: 55, s: 7, c: 'blue' },
  { x: 250, y: 250, s: 50, c: 'green' },
  { x: 400, y: 400, s: 30, c: 'pink' }
]

这就是它们在 Canvas 上或仅在页面上的样子(不必真的是 Canvas ):

现在假设我有一个 25x25 像素的黑色方 block ，而不是我的光标。当我将光标移到其中一个彩色方 block 上时 - 因此方 block 被完全覆盖 - 我的指针“吞噬”了它们，因此它们从数组和 Canvas 中消失了。就像在老蛇吃食物一样!

const pointer = { x: event.pageX, y: event.pageY, s: 25, c: 'black' }

这样做:

将删除 elements[1] 又名 { x: 110, y: 55, s: 7, c: 'blue' }。因为我的光标覆盖了整个蓝色方 block 。我显然不能吃掉绿色方 block ，因为它比我的光标大。

我的问题是 - 考虑到我可能有 很多 彩色方 block (让我们说超过 1000)？

我一直在尝试像这样过滤覆盖的项目:

let squareCovered = elements.filter(square => square.x == pointer.x && square.y == pointer.y);

但这还不够好，因为不能同时考虑正方形和光标的大小，所以我总是必须将光标准确地放在正方形的中心。当我尝试在这种过滤方法中引入尺寸时，我的项目变得非常快。

有什么提示吗？是否有针对此的高性能算法？

随意编辑问题标题，不知道我到底在问什么。

Answer 1

接触 DOM 是代价高昂的部分；如果您尽可能多地使用源数据而不是呈现的页面，您将能够通过暴力破解达到数量惊人的方 block 。

除了初始化布局之外，下面唯一的 DOM 操作是在鼠标移动时重新定位黑色方 block 并移除“吃掉”的元素；遍历 elements 数组比遍历它们作为 DOM 节点要快得多。

这是一个包含 10,000 个正方形的演示；它在大约 25,000 个方格处开始变得迟钝:

const colors = ['red', 'blue', 'green', 'violet', 'indigo', 'pink', 'orange', 'bisque', 'chocolate', 'gold', 'fuschia', 'firebrick', 'peru'];

// make a lot of squares.
const elements = []
for (let i = 0; i < 10000; i++) {
  elements.push({
    x: Math.floor(Math.random() * window.innerWidth),
    y: Math.floor(Math.random() * window.innerHeight),
    s: Math.floor(Math.random() * 10), // keeping them small or the screen gets too crowded with uneatable squares
    c: colors[Math.floor(Math.random() * colors.length)]
  });
}

// quick and dirty way to draw the squares:
let squaresHTML = "";
for (let i = 0; i < elements.length; i++) {
  let el = elements[i];
  squaresHTML += `<div id="square${i}" style="position:absolute; left:${el.x}px; top: ${el.y}px; width: ${el.s}px; height: ${el.s}px; background-color: ${el.c}"></div>`;
}

// This is *much* faster than a lot of createElement() appendChild() stuff
document.getElementById('container').innerHTML = squaresHTML;

// handle mousemove:
const cursor = document.getElementById('cursor');
const apothem = cursor.clientWidth / 2;
document.body.addEventListener('mousemove', e => {

  // position the black square:
  [cursor.style.left, cursor.style.top] = [`${e.clientX - apothem}px`, `${e.clientY - apothem}px`];


  // brute force search for overlaps:
  for (let i = 0; i < elements.length; i++) {
    let el = elements[i];
    if (
      (el.x >= e.clientX - apothem) &&
      (el.y >= e.clientY - apothem) &&
      (el.x + el.s <= e.clientX + apothem) &&
      (el.y + el.s <= e.clientY + apothem)
    ) {
      // found a sqare that is completely covered; "eat" it (if we haven't already):
      if (document.getElementById(`square${i}`)) {
        document.getElementById(`square${i}`).remove()
        // Do not modify the elements array here! The indexes are hardcoded!
      }
    }
  }
})

body {
  overflow: hidden
}

#container {
  width: 100vw;
  height: 100vh
}

#cursor {
  width: 25px;
  height: 25px;
  position: absolute;
  background-color: black
}

<div id="container"></div>

<div id="cursor"></div>

如果我必须进一步优化它，我可能会将页面分成“区域”并预先计算哪些方 block 在哪个“区域”中；这样，当鼠标移动时，您可以快速识别需要迭代的元素子集。 (重叠区域边界的正方形会增加一些复杂性，但您可以通过复制每个相关区域的正方形条目，或者将它们的区域和“我正在搜索哪个区域”基于任何一致的东西来解决这个问题，比如说，正方形' 左上角像素。)