有没有办法优化管理单元对象算法？

Question

所以我能在舞台上拖n个对象，我希望他们当你拖动他们足够接近扣（LOCK，磁铁...）给对方。这意味着计算每个鼠标移动事件中从拖动的对象到舞台上的每个其他对象的距离。这可以优化吗？比如仅将距离与关闭对象进行比较，但是如何知道哪些是关闭而不先计算所有距离？

感谢

Answer 1

可以使用k-d tree。 K-d树具有高效的“寻找最近邻居”功能。只要确保每一个已经“到位”的对象是你的树，当你移动一个元素 - 发现其最近的邻居，并检查是否足够或不紧密。

---

替代方案（主要用于网格）使用observer pattern。每当你放置一个物体时 - 在其影响开始的地方绘制线条。将这一行上的每个“单元格”与观察者连接起来，当你将一个对象移动到一个单元格时，如果有任何观察者附加到它上面 - 调用它们。

Answer 2

在古典解决这类问题是递归削减空间成区域。您只能在密切区域搜索neigboors。对此的经典数据结构是QuadTree，其中正方形被切割成四个正方形。

Answer 3

两个想法：

1. 您可以将您的舞台为一些大小 '砖'（比如，64×64像素？）。如果您知道哪些瓷砖会（部分或完全）重叠给定瓷砖，则可以将检测到的检测限制为这些瓷砖。

2. 你可以保持一个（排序！）地图，映射给定的“Y”坐标对“Y”位置的所有对象（或多个）。在每个对象列表中y坐标分类为好，让他们通过X顺序排序的对象。通过使用下限/上限（这对于在排序的序列上计算是有效的），您可以快速获取特定边界矩形内的所有对象的句柄。