确定一个点在2d空间中的哪个矩形

Question

我有一大堆在html5画布上绘制的矩形.

我希望能够使用鼠标跟踪与此图像进行交互(我不能使用SVG,因为它不能扩展到10-100k矩形).有没有任何数据结构/算法,给定鼠标x,y坐标能够告诉你鼠标在哪个框(使用矩形的计算位置)？我在想像kd树,但不确定.

Answer 1

如果您的数据始终是显示的形式,我认为您应该能够比空间树数据结构做得更好.

由于数据的结构是y您应该能够根据时间偏移计算点所在的矩形"条带" O(1).

如果您按照排序顺序存储每个'条带'中的单个矩形(使用xmax说),那么您应该能够使用二进制搜索(in O(log(n)))在条带内找到特定的矩形.

希望这可以帮助.