我正在开发一个交互式web应用程序,目前正在实现一个多选功能,类似于windows允许您通过拖动矩形来选择多个桌面图标的方式。
由于我需要使用的库的限制,实现这一点已经变得相当耗费资源:
- 首次单击时,存储鼠标光标的位置
-
在鼠标光标移动的每个像素上,执行以下操作:
- 销毁以前的选择矩形(如果存在),这样它就不会再出现在屏幕上
-
使用当前光标位置和当前光标位置计算新选择的重新角度的宽度和高度。
-
使用原始光标位置、宽度和高度创建一个新的选择矩形
- 在屏幕上显示此矩形
正如您所看到的,每次光标移动一个像素时都会发生很多事情。我已经尽我所能地研究了这个问题,我不可能让它变得更高效或更快。
我的下一步是当选择矩形在屏幕上移动时,实际选择屏幕上的对象。我需要自己实现这个算法,这样我就可以自由地使它尽可能高效/快速。我需要做的是遍历屏幕上的对象,并检查每个对象是否位于矩形中。所以这里的循环将消耗更多的资源。因此,我需要尽可能有效地进行检查。
可以选择的每个对象都可以由一个点p(x,y)表示。
如何以最快/最有效的方式检查p(x,y)是否在我创建的矩形内
以下是相关信息:
- 可以是任意数量的对象,可以在任何时候在屏幕上选择
- 选择矩形将始终与轴对齐
- 我所掌握的关于矩形的信息是它们的原点、高度和宽度
我如何才能尽快完成我需要做的事情?
检查点p是否位于矩形R内简单快捷
(在原点位于左上角的坐标系中)
(P.X >= R.Left) and (P.X <= R.Right) and (P.Y >= R.Top) and (P.Y <= R.Bottom)
(预先计算矩形的右下坐标)
如果对象满足某些条件,也许你可以加速整个算法,这允许不要在每一步都检查所有对象。
示例:按X坐标对对象列表进行排序,然后只检查那些位于左侧的对象。。右侧
更高级的方法:在一些空间划分数据结构(如kd树)中组织对象,并快速执行范围搜索
您可以遍历屏幕上的每个对象,并使用以下条件检查它是否位于笛卡尔坐标系中的矩形中:
p.x >= rect.left && p.x <= rect.right && p.y <= rect.top && p.y >= rect.bottom
如果屏幕上的点不超过1000个,只需使用简单的O(n)
方法迭代每个点即可。如果你完全确定你需要进一步优化,请继续阅读。
根据更新点的频率和每帧更新的点的数量,您可能希望使用可能涉及数据结构(如Range Trees)的不同方法,或者选择简单的O(n)
方法。
如果点不会移动太多并且稀疏(即彼此相距很远),则可以使用范围树或类似工具进行
O(log n)
检查。不过,请记住,更新这样的空间分区结构是资源密集型的,如果你有很多点要移动很长一段时间,你可能想看看其他的东西。如果几个点将在大距离内移动,您可能需要考虑将屏幕划分为"桶"网格,并只检查矩形中包含的桶。每当一个点从一个桶移动到另一个桶时,网格都必须更新受影响的桶。
- 如果内存是一个约束,如果网格方法不够有效,您可能需要考虑使用受树深度而非桶大小限制的修改的四叉树
如果每帧都有很多点在移动,我认为你可能更适合使用网格方法或简单的O(n)
方法。尝试并选择一种最适合您问题的方法。