关于树搜索算法，特别是四叉树和 r-tree，它们在寻找最近邻居时如何解决边缘错误。我不擅长用文字来解释，所以我做了一些图片。
对于图片，查找最近邻居的输入坐标为绿色，我假设最终成为“找到的”最近邻居的是红色。实际最近的邻居是蓝色的。
在这个四叉树中，蓝色的右下象限将仅使用一个红色点进行搜索，而实际上，输入坐标（绿色）非常靠近边缘，实际上更靠近蓝色点。
如果坐标在一个矩形内但非常靠近边缘，则与 R-tree 类似，它更靠近另一个矩形中的点，如下所示，其中白点被赋予坐标：
它完全在红色框中，但更接近洋红色框中的一个点。
在这两种情况下，都需要在元素之间进行细粒度的距离检查——框或分区只是帮助找到真正距离检查的候选对象。
一种看待它的方法是，使用这些框来告诉您不要检查的内容。如果整个框比你已经知道的更远，你不需要检查那个框里的任何东西。如果某些框很接近，最好检查其中的元素。
如果您愿意阅读 R-tree 出版物...
它使用查询点到相邻页面的最小距离。
如果mindist(query, rectangle) <= dist(query, known neighbor)那么搜索需要在另一个矩形中继续，因为那里可能有更好的邻居。
它实际上非常简单，应该在任何关于 R-trees 和类似索引的书中进行解释。