PiF*_*ace 7 language-agnostic algorithm user-interface data-structures
我一直在尝试到处搜索这个问题，但我发现的所有问题都与高级别的问题有关，例如“如何知道正在单击哪个 HTML”。这不是我要找的东西。我正在寻找更底层的细节。
假设有人正在尝试为给定系统编写 GUI 库。另外，假设该程序员已经设法在屏幕上显示图形、文本、按钮等。现在，他们希望实现用户与该界面交互的方法，更具体地说，使用鼠标单击（或者可能是触摸输入）。
GUI 引擎运行的系统能够告诉他们何时发生点击，以及点击发生在屏幕上的哪个 (x, y) 点。要查找屏幕上的哪些元素被单击，一个简单的方法是循环遍历每个元素并测试每个元素。但这是现有 GUI 中通常的做法吗？例如，这是浏览器显示 HTML 页面时所做的事情吗？这就是操作系统对其 GUI 和窗口所做的事情吗？他们是否使用更复杂的数据结构（例如 R 树）？他们如何处理移动元素？
这个问题并不特定于任何软件，我只是想知道在 GUI 开发的背景下通常如何解决这个问题。
有两种基本方法。你已经想到的一个：
测试“每个”对象与鼠标位置
这可以通过使用空间细分结构（类似于 2D 中的 BVH 和八叉树）来加速。然而，这种方法总是比较慢，并且会带来复杂性，例如O(log(n))GUI元素的O(n)数量n。这是一个天真的O(n)例子：
然而，一旦测试的项目数量增加或形状过于复杂，这种方法就很麻烦。
使用索引缓冲区
这种方法在复杂性上是像素完美的，O(1)并且在大多数实现中几乎是免费的、快速的。
这个想法是让索引缓冲区的分辨率与屏幕保持测试元素的 ID（索引）而不是颜色相同。因此，在渲染 GUI 时，除了使用颜色设置元素的每个像素之外，您还可以在索引缓冲区中的相同位置设置渲染项目索引或 ID。
此后检测只是获取鼠标位置处的索引缓冲区值。这里有几个例子：
此方法也适用于 2D 和投影 3D->2D 甚至更高维度。