在 Booking.com，我们热衷于通过提供最佳的住宿搜索功能让用户的生活更轻松。我们希望我们的用户拥有选择最佳住宿的所有信息。众所周知，酒店的位置是选择住宿时最重要的标准之一，因为它是旅行体验的重要组成部分。
Booking.com 地图功能是一个强大的工具，因为它以非常直观的方式提供位置信息。只需几秒钟，用户就可以确定该物业是否位于他们的首选位置。但是，通常仅查看属性本身的位置是不够的。显示旅途中最有趣的景点的位置也很重要。他们有多远？从酒店找到他们有多容易？
为了帮助我们的用户回答这些问题，除了属性标记之外，我们还显示所谓的兴趣点 (POI) 标记。顾名思义，这些标记突出了旅行者感兴趣的地方，例如海滩、滑雪胜地、地标以及城市和机场，所有这些都可以让用户更好地了解酒店的位置。
地图上的城市、景点和机场标记
如何在地图上搜索？
当用户打开地图时，通常会看到一个称为边界框 (BBox) 的特定区域。从技术上讲，BBox 是一个矩形，其角由 4 个地理点表示：
- 西北（NW）；
- 东北（NE）；
- 东南（SE）；
- 西南 (SW)。
因为它是一个矩形，所以只知道彼此成对角线的 2 个地理点就足以派生出一个 BBox。例如东北和西南。
边界框——可见的地图区域。
从逻辑上讲，仅显示此 BBox 内的那些 POI 标记就足够了，因为用户看不到世界其他地方。因此，我们可以在搜索地图内容时使用 BBox 作为搜索关键字。
用户可能会通过平移和缩放地图来更改可见区域，并且此类交互的数量可能相对较高。我们想要提供最好的用户体验，我们想要尽快提供在地图上显示的信息，这将需要一个高效的搜索机制，可以与 BBox 不寻常的搜索键一起工作。
说到key搜索，搜索树就是一个经典的解决方案，当然本例也不例外！但首先我们需要找到一种利用这种树的方法，并弄清楚如何将 BBox 用作键。为了解决这个问题，我们将使用四叉树。
四叉树
四叉树是一种搜索树，其中每个内部节点恰好有四个子节点。你问为什么是四个？具有两个子节点的简单搜索树通常在每一层将搜索集一分为二。地图是由纬度和经度组成的二维结构，在每一层上我们需要将每个维度分成两块，从而产生四个象限。这棵树的每个节点也是一个 BBox。根节点将是包含整个世界的 BBox，每个子节点将是父 BBox 的一个象限。
用四叉树搜索。
由于我们的主要目标是找到要在地图上显示的标记，因此树的每个节点也将包含一些（通常相对较少）数量的标记。最简单的四叉树节点的代码表示如下所示：
类 QuadTreeNode {
private Set<Marker> 标记；
私有边界框 bbox；
私人QuadTreeNode[] 孩子；// 大小始终为 4
private final int maxEntryCount;
...
}搜索
让我们看看我们如何使用四叉树来查找，例如，包含在 BBox 中的五个地标。假设我们树的每个节点都包含 10 个地标，它们位于代表当前节点的 BBox 内。我们应用 BFS，并且像往常一样，我们从根节点开始：
- 遍历此节点中的所有标记，并检查是否有任何标记与作为搜索键的 BBox 相交。知道地标的坐标非常简单，我们只需要检查这些坐标是否在 BBox 矩形内。如果条件
(SW lat <= Marker lat <= NE lat) && (SW lon <= Marker lon <= NE lon)
为真，则标记位于 BBox 内。我们将 BBox 边缘上的标记视为相交。 - 保存相交的标记。
- 如果我们找到五个地标，我们的搜索就结束了。
- 如果我们需要找到更多地标，我们检查哪些子节点与给定的搜索键 BBox 相交，并将它们保存在队列中以供进一步检查。它可能是一到四个节点。
- 从队列中选择下一个节点并转到步骤 1。
在代码中我们可以这样表达搜索过程：
类 QuadTree {
私有QuadTreeNode 根；
...
public Set<Marker> findMarkers (BoundingBox bbox, int n) {
Set<Marker> foundEntries = new HashSet <>();
Queue<QuadTreeNode> nextNodesToCheck = new LinkedList <>();
nextNodesToCheck.add(root);
while (foundEntries.size() < n && !nextNodesToCheck.isEmpty()) {
int stillToFind = n - foundEntries.size();
四叉树节点 nodeToCheck = nextNodesToCheck.poll();
列表<标记> currentEntries = nodeToCheck.getIntersectingEntries(bbox, stillToFind);
foundEntries.addAll(currentEntries);
如果(foundEntries.size() < n) {
nextNodesToCheck.addAll(
nodeToCheck.getIntersectingChildren(bbox)
);
}
}
返回找到的条目；
}
}当我们搜索 X 标记时，我们从树的顶部到底部搜索。这意味着将最先找到距离根节点最近的标记。由于我们希望向用户展示与他们的搜索最相关的标记，因此我们也需要考虑标记的重要性。
最重要的标记将保留在根节点中，如果将地图比例减小到整个世界可见时的级别，您就会看到它们。当用户缩放地图时，他们将看到对可见区域最重要的标记，即使它们在较低的缩放级别可能不可见。
标记的重要性基于可以由业务需求定义的自定义标准。例如，我们可能会根据用户评论确定地标标记的重要性。
边缘案例
我们还应该提到一个有趣的边缘案例。想象一下简单的纸质世界地图是什么样子的：它是一个矩形，其侧边在右侧为 180 度经线，在左侧为 -180 度经线。所以想象一下，用户在这里搜索财产。
边界框与地图的“边缘”相交。
在这种情况下，BBox 的 SW 经度将大于 NE 经度。在检查 BBox 矩形内的标记时，我们需要考虑这种情况。例如：
- 假设 BBox 坐标是SW (160, 60), NE (-160, 70). 这是一个有效的 BBox。
- 带有坐标的标记(-162, 62)不会被视为与 BBox 相交，因为.SW lon > Marker lon
解决这个问题的一种方法是将我们的 BBox 拆分为 2 个 BBox（如果我们知道的话）SW lon > NE lon。我们可以将 BBox 一分为二，使用 -180/180 子午线作为分隔符：
- BBox1：SW (160, 60), NE (180, 70)
- BBox2：SW (-180, 60), NE (-160, 70)
我们的标记(-162, 62)现在将匹配 BBox2。
将 BBox 分成两部分。
四叉树大厦
幸运的是，搜索树不会凭空出现，所以这就是软件工程师仍然有工作的原因之一。让我们看看如何实现满足我们用例的四叉树。
一开始，我们的树只有一个根节点，它是整个世界，它不包含任何标记，它是空的。
为了用标记填充树，我们需要遍历我们拥有的所有标记并将每个标记插入树中。假设每个节点最多可以包含 10 个标记。然后，在每次插入时我们做：
- 将当前标记放入当前节点的标记集中。
- 如果标记的大小设置 <= 10，我们就完成了——标记找到了它的位置。迭代到下一个标记。
- 如果标记的大小设置 > 10，我们需要获取该节点最不重要的标记并将其推送给其中一个子节点。（记住：节点离根越近，节点中标记的重要性越高）。
- 如果尚未创建当前节点的子节点，则通过将节点的 BBox 拆分为四个子 BBox 来创建它们。
- 搜索与最低优先级标记相交的子 BBox。
- 递归地将此标记放入子节点（即以最不重要的标记和子节点作为输入转到上面的步骤 1）。
为了确保我们可以找到节点的最不重要的标记，我们可以使用 PriorityQueue 作为标记的容器。该集合中的标记将按重要性排序，因此我们可以轻松找到最不重要的标记。这也意味着在标记查找中，我们将首先找到节点最重要的标记。
这是插入实现的样子：
class QuadTreeNode {
// 将最低优先级标记保持在队列顶部
private PriorityQueue<Marker> markers;
私有边界框 bbox；
私人QuadTreeNode[] 孩子；// 大小始终为 4
private final int maxEntryCount;
...
public void insert (Marker marker) {
markers.add(marker);
if (markers.size() > maxEntryCount) {
if (children == null ) {
children = initializeChildren(); // 创建 4 个四叉树节点
}
Marker entryToPassToChild = markers.poll(); // 获取最低优先级标记
List<QuadTreeNode> intersectingChildren =
getIntersectingChildren(entryToPassToChild.getBoundingBox());
// 标记可以在节点的边缘。
// 由于边缘是多个节点之间的共享区域，
// 标记可以属于多个节点。
对于(QuadTreeNode intersectingChild : intersectingChildren) {
intersectingChild.insert(entryToPassToChild);
}
}
}
...
}我们在标记搜索服务启动期间构建四叉树并将其保存在内存中，不时刷新它。幸运的是，新城市不会经常建立，机场、地标等也是如此。但是，标记的重要性可能会发生变化，因此建议定期刷新树。
结论
四叉树是一个相对简单且（同时）强大的概念，它完美地解决了 BBox 任务的标记搜索。我们还发现该解决方案具有高度可扩展性，因为我们应对不断增加的负载所需要做的就是水平扩展我们的服务。
例如，存储超过 300k 标记的四叉树，（取决于服务负载）99% 的查找时间不到 1 到 ~5.5 毫秒，这对我们的目的来说非常快。
存储至少 300k 标记的四叉树中的查找时间
感谢您阅读本文并祝您搜索愉快！
致谢：感谢Gregory Zak的后期创意和技术编辑，以及Al-Jerreau Davids的精美插图。vids的精美插图。
作者：Igor Dotsenko
出处：https://medium.com/booking-com-development/how-to-search-point-of-interest-poi-markers-on-a-map-efficiently-b5f3f37a914a