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

Question

3

我目前在进行一个宠物项目，允许用户在Java屏幕上创建图形（顶点/边）。我已经将顶点实现为JComponents，但将边实现为Line2D。当用户在画布上移动鼠标时，如果其在接近某个边缘（或Line2D）的一定距离范围内，则会突出显示该边缘（最接近鼠标的边缘）。

我的问题涉及我如何实现哪个边缘最靠近鼠标。现在，我有一个鼠标侦听器来检测移动；每次鼠标移动时，我的程序循环遍历所有的线条（边缘），并使用Line2D的ptDistSeg（）函数确定最接近的线条。如果在阈值内，则会突出显示（在paintcomponent中使用更粗的笔划）。

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

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

谢谢。

- M.Sullivan

你是否真的在这里看到了性能问题，还是纯理论上的推测？ - templatetypedef

程序似乎处理得很好。当我有大量的边（例如26个顶点的完全图）时，它会有些滞后，但并不过分。我现在只想尽可能地使其高效，而不是让它成为程序未来的问题。 - M.Sullivan

3

这似乎可以用在游戏中用于碰撞检测的技术来解决。您可以将几何形状存储在专门的数据结构（例如四叉树）中，以获得比完整线性搜索更好的性能。 - trooper

我快速浏览了一下关于四叉树的维基百科，发现它非常有趣。谢谢您的回复，我会更详细地研究它们（以及您提到的碰撞检测）。 - M.Sullivan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

也许在某个地方有更好的数据结构可用，但其中一种选项是计算每个边的轴对齐边界框，以获得每个边一个矩形，然后将所有这些矩形存储在空间数据结构中，例如R 树。 R 树支持形式为“给我所有与某点重叠的矩形”的有效查询，因此您可以使用它来过滤所有直线段，仅保留那些可能击中鼠标点的直线段，然后进行测试。

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

希望这可以帮到你！