我有一大组在 html5 画布上绘制的矩形。
我希望能够使用鼠标跟踪与此图像进行交互（我不能使用 SVG，因为它不能缩放到 10-100k 矩形）。是否有任何数据结构/算法，假设鼠标 x,y 坐标能够告诉您鼠标在哪个框上（使用矩形的计算位置）？我在想像 kd 树之类的东西，但不确定。
问问题
301 次
3 回答
6
如果您的数据始终采用所示形式，我认为您应该能够比空间树数据结构做得更好。
由于数据是结构化的，y您应该能够根据时间偏移量计算点所在的矩形“条带” O(1)。
如果您按排序顺序（使用say）将各个矩形存储在每个“条带”中，xmax那么您应该能够使用二分搜索（in O(log(n))）在条带中找到特定的矩形。
希望这可以帮助。
于 2012-10-18T15:39:13.827 回答
0
天真的解决方案是遍历所有矩形并检查您是否在其中。检查单个矩形很容易（如果你愿意，我会明确地写下来）。
如果您有许多矩形并且关心性能，您可以通过将矩形放入一个更快查看的数据结构中来轻松加快速度。查看您发送的图像，您的数据的一个明显属性是有限垂直位置的数量（“行”）。这意味着如果您检查您所在的行，则只需检查该行内的矩形。最后，要选择您所在的行或行内选择哪个矩形，请保持已排序的数据结构（例如某些搜索树）。
因此，您的数据结构可能类似于行的搜索树，其中每个节点都包含沿行的矩形搜索树。
于 2012-10-18T15:40:41.413 回答
0
R-tree适用于提供这种空间访问
但有些问题：
你的矩形设置是静态的还是动态的？
您期望矩形集有多少点查询？
编辑：
因为矩形集是静态的：有方法，用于传统的位图图形（不知道是否适用于html5画布）：
制作与主图片大小相同的附加位图。用相同的坐标绘制每个矩形，但用唯一的颜色填充它（例如，颜色 = 矩形索引）。然后检查鼠标点下的颜色 => 在 O(1) 中获取矩形索引
于 2012-10-18T15:50:21.350 回答