javascript - 算法 - O(1) 检查鼠标是否悬停在圆圈数组之一上

Question

通常检查 mouse move 事件 x 和 y 是否拦截多边形数组中的任何多边形是:

on mousemove (e)->
  for c in circles
     if intercept(e.x, e.y, c)
        ...

只是想知道我是否可以在没有 for 循环的情况下检查它，例如:

on mousemove (e)->
  i = calidx(e.x, e.y)
  if intercept(e.x, e.y, circles[i])

似乎通过所有数组项的每个 mousemove 事件循环都不是高效的

是否可以使用 O(1) 的复杂度来找出哪个数组项正在悬停？

Answer 1

使用查找表使其摊销 O(1)(但设置/更新很痛苦)

摊销 O(1) 的一种方法是使用表查找。这意味着您需要像这样存储每个像素坐标及其所属的圆圈 ID:

pixel(0,0) --> no circle

pixel(0,1) --> circle#1

pixel(0,2) --> circle#1,circle#2

...

因此您可以快速查找具有特定像素坐标的表格并检索它所属的圆。这种查找可以用分摊的 O(1) 完成。

但是，设置/更新表格很麻烦

设置查找表的算法很痛苦，非常复杂。您需要填充您拥有的每个圆圈的所有像素坐标并制作完整的表格。这非常复杂，更新现有圈子的新位置更糟。更新查找表需要一些计算。

这种方法在以下情况下是负担得起的:

• 您的圈子是静态的。设置圈子后，它们将不会移动或调整大小。
• 你有一 block 小 Canvas 。

相反，在以下情况下这是邪恶的，甚至更糟:

• 您的圈子是动态的。它们一直在移动、调整大小、添加或删除。这使更新阶段付出了巨大的开销。
• 你有一个大 Canvas 。