java - 确定最接近鼠标的元素的最有效方法是什么？

Question

我目前正在开发一个宠物项目，该项目允许用户使用 Java 在屏幕上创建图形(顶点/边)。我将顶点实现为 JComponents，但将边实现为 Line2D。当用户在 Canvas 上移动鼠标时，如果它在某个边缘(或 Line2D 的)附近的某个阈值内，则该边缘(最靠近鼠标)将突出显示。

我的问题涉及我实现哪条边最接近鼠标的方式。现在我有一个可以检测运动的鼠标监听器；每次移动鼠标时，我的程序都会循环遍历所有线(边)并使用 Line2D 的 ptDistSeg() 函数确定最接近的线。如果这在阈值内，则它会突出显示(在 paintcomponent 中使用较粗的笔划)。

对我来说，这似乎非常低效，因为每次移动鼠标时它都必须重新计算与鼠标的所有边缘距离。对于顶点来说，这不是问题，因为鼠标监听器与每个顶点相关联，因此顶点知道它们何时需要处理事件。不幸的是，我无法对边缘执行此操作，因为它们表示为无法实现 mouseListener 的 Line2D。

那么有没有更有效的方法来找到最近的边缘，或者我应该以不同的方式实现边缘？

谢谢。

Answer 1

在某处可能有更好的数据结构，但一种选择是计算每条边的轴对齐边界框以获得每条边一个矩形，然后将所有这些矩形存储在空间数据结构中像一个R-tree . R 树支持“给我所有重叠某个点的矩形”形式的高效查询，因此您可以使用它来过滤所有线段，只筛选出可能击中鼠标点的线段，然后只测试这些线段。

这里的缺点是，由于更改边界框的成本，四处移动节点将需要大量的 R 树重建，并且您需要找到一个好的 R 树库，因为 R 树不是从头开始实现非常容易。

希望这对您有所帮助!