2

我正在设计一个管理矩形集合的类。每个矩形代表一个按钮，因此包含以下属性：

  • x位置
  • y位置
  • 宽度
  • 高度
  • 按下时发生的回调函数。

这个概念本身相当简单，并通过命令行界面进行管理。尤其是。

如果我键入“100, 125”，它会查找是否有一个包含该点（或多个）的矩形并执行它们的回调函数。

我的建议是遍历这个集合中的所有矩形并执行包含该点的每个矩形的回调，或者在第一个匹配的矩形上停止（模拟 z 顺序）。

然而，我担心这个解决方案是草率的，因为我拥有的矩形越多，这个迭代就越长。这对于控制台应用程序来说很好，因为它可以轻松地遍历 10,000 个矩形并找到匹配的矩形，计算成本很高，但从时间上看，这并不是一个特别的问题。

问题是，如果我要在 GUI 应用程序中实现此算法，每次移动鼠标时都需要执行此检查（以模拟鼠标悬停效果），将鼠标移动 10 像素到具有 10,000 个对象的面板上将需要检查100,000 个对象，甚至不到 1000 像素或超过人们倾向于将鼠标移到上面。

有没有更优雅的解决方案来解决这个问题，或者这样的程序总是需要如此昂贵？

注意：我知道大多数 GUI 不必一次处理 10,000 个活动对象，但这不是我的目标。我选择用按钮来解释这个问题的原因是因为它们更简单。理想情况下，我想要一个能够在 GUI 以及与鼠标交互的粒子系统和其他要求苛刻的系统中工作的解决方案。

在 GUI 中，我可以轻松地使用间接来显着减少检查量，但这并不能缓解每次移动鼠标时都需要执行检查的问题，即使有 25 个按钮，这也可能非常苛刻，因为移动超过 400 个像素和 25 个对象（在理想条件下）与移动 1 个像素和 10,000 个对象一样糟糕。

简而言之，这个问题是双重的：

  1. 我能做些什么来减少从 10,000 个检查的数量（假设有 10,000 个对象）。
  2. 是否可以将此类 GUI 应用程序中所需的每次鼠标移动检查数量减少到更合理的程度。

任何帮助表示赞赏！

4

2 回答 2

4

您可以应用任意数量的二维交叉加速结构。例如，您可以使用四叉树 ( http://en.wikipedia.org/wiki/Quadtree ) 将视口递归地划分为象限。细分不完全落在每个矩形内部或外部的每个象限，并在每个叶子上放置一个指向顶部或矩形列表的指针（或者NULL如果没有矩形落在那里）。该结构并非微不足道，但在概念上相当简单。

于 2013-07-13T16:22:59.197 回答
2

有没有更优雅的解决方案来解决这个问题，或者这样的程序总是需要如此昂贵？

您可以使用四叉树之类的数据结构来有效地找到最近的对象，而不是对所有对象进行线性搜索。

或者，您可以根据算法的预期用途提出一组更现实的要求。一个同时可见 10,000 个按钮的 GUI 是一个糟糕的设计，原因有很多，主要原因是糟糕的用户很难找到正确的按钮。从性能的角度来看，通过多个更典型的 UI 矩形进行线性搜索，比如 2 到 100 之间的某个地方，将没有问题。

于 2013-07-13T16:25:40.727 回答