标记是一件好事。有用数量合理。当它们太多时，好处就消失了。如果要在地图上标记成千上万个对象的搜索结果怎么办？在本文中，我将告诉您如何在WebGL卡上解决此问题而不影响其外观和性能。

背景知识

2GIS在2016年启动了第一个WebGL项目，即“楼层：建筑物的3D楼层平面图”。

新西伯利亚购物中心Aura的楼层

Floors发布后，我们的团队立即开始在WebGL上开发成熟的三维制图引擎。该引擎是与新版本2gis.ru一起开发的，目前处于公开Beta状态。

在WebGL上绘制的红色正方形。 现在，建筑图则直接集成到地图中。

签名归纳任务

任何想要编写自己的地图引擎的人，迟早都会面临在地图上放置签名的问题。地图上有很多对象，并且不可能对每个对象进行签名以使签名不会重叠。

如果在新西伯利亚同时对所有对象进行签名会发生什么

为了解决这个问题，需要对签名进行一般化。一般而言，泛化是对地图数据的转换，因此适合于小规模显示。可以通过不同的方法来完成。对于签名，通常使用选择方法：从总数中选择不重叠的最优先签名的子集。

签名优先级由其类型以及当前地图比例确定。例如，在小规模上，需要城市和国家的签名，而在大规模上，道路签名和门牌号变得更加重要。通常，定居点名称的优先级取决于其人口规模。它越大，签名越重要。

不仅对于签名，而且对于在地图上标记搜索结果的标记，都需要通用化。例如，在莫斯科搜索“商店”时，有超过15,000个结果。同时在地图上全部标记它们显然是一个坏主意。

地图上所有莫斯科的商店 没有概括就没有办法

用户与地图的任何交互（移动，缩放，旋转和倾斜）都将导致屏幕上标记的位置发生变化，因此您需要能够即时重新计算归纳。因此，它必须快速。

在本文中，以标记归纳为例，我将展示解决此问题的不同方法，这些方法在我们项目中的不同时间使用。

一般化方法

将每个标记投影到屏幕的平面上，并为其计算边界-它在屏幕上占据的矩形区域。
按优先级对标记进行排序。
顺序检查每个标记并将其放置在屏幕上（如果它不与放置在其前面的其他标记相交）。

对于第1点，一切都很清楚-只是计算而已。对于项目2，我们也很幸运：来自后端的标记列表已经按搜索算法按优先级进行了排序。用户最可能感兴趣的最相关结果位于结果顶部。

主要问题在第3段中：计算泛化的时间在很大程度上取决于实现方式。

为了搜索标记之间的交点，我们需要一些数据结构，该结构：

存储添加到屏幕上的标记的边界。
具有insert(marker)方法以将标记添加到屏幕。
它具有collides(marker)方法，可以检查标记与已经添加到屏幕的标记是否相交。

考虑此结构的几种实现。所有其他示例将用TypeScript编写，我们在大多数项目中都使用了TypeScript。在所有示例中，标记将由以下形式的对象表示：

 interface Marker { minX: number; maxX: number; minY: number; maxY: number; }

所考虑的所有方法将是以下接口的实现：

 interface CollisionDetector { insert(item: Marker): void; collides(item: Marker): boolean; }

为了比较性能，将测量以下代码的执行时间：

 for (const marker of markers) { if (!impl.collides(marker)) { impl.insert(marker); } }

markers数组将包含100,000个30x50元素，这些元素随机放置在1920x1080尺寸的平面上。

性能将在2012 Macbook Air上进行评估。

文章中提供的测试和代码示例也发布在GitHub上。

天真的实现

首先，请考虑最简单的选项，即在一个简单的周期中检查标记是否与其他标记相交。

 class NaiveImpl implements CollisionDetector { private markers: Marker[]; constructor() { this.markers = []; } insert(marker: Marker): void { this.markers.push(marker); } collides(candidate: Marker): boolean { for (marker of this.markers) { if ( candidate.minX <= marker.maxX && candidate.minY <= marker.maxY && candidate.maxX >= marker.minX && candidate.maxY >= marker.minY ) { return true; } } return false; } }

100,000个标记的通用计算时间： 420毫秒 。太多了即使泛化计算是在Web工作者中完成的，并且不会阻塞主线程，这种延迟也将是显而易见的，特别是因为此操作必须在每次移动卡后执行。此外，在处理器较弱的移动设备上，延迟可能更大。

R树实现

由于在幼稚的实现中，每个标记都被检查是否与先前所有标记相交，因此在最坏的情况下，该算法的复杂度是二次的。您可以通过应用R树数据结构来改进它。作为R树的实现，请使用RBush库：

 import * as rbush from 'rbush'; export class RTreeImpl implements CollisionDetector { private tree: rbush.RBush<Marker>; constructor() { this.tree = rbush(); } insert(marker: Marker): void { this.tree.insert(marker); } collides(candidate: Marker): boolean { return this.tree.collides(candidate); } }

100,000个标记的通用计算时间： 173 ms 。明显更好。我们在Floors中使用了这种方法（我的上一篇文章中已经提到过）。

R树中点存储的可视化。 平面分为矩形的层次结构可让您快速缩小搜索范围，而不用对所有对象进行排序

碰撞缓冲实现

绘制地图比绘制一栋建筑的计划要复杂得多。这也体现在概括上。即使在世界上最大的购物中心，也很少有1,000家组织位于同一楼层。同时，在大城市中进行简单的搜索查询可以返回数以万计的结果。

当我们开始开发WebGL地图时，我们开始思考：是否仍有可能加快泛化速度。为我们工作的恒星器为我们提供了一个有趣的想法：代替R树，使用缓冲区来存储屏幕上每个像素（忙或不忙）的状态。在屏幕上插入标记时，“填充”缓冲区中的相应位置，并在检查粘贴可能性时，检查所需区域中的像素值。

 class CollisionBufferByteImpl implements CollisionDetector { private buffer: Uint8Array; private height: number; constructor(width: number, height: number) { this.buffer = new Uint8Array(width * height); this.height = height; } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { buffer[i * this.height + j] = 1; } } } collides(candidate: Marker): boolean { const { minX, minY, maxX, maxY } = candidate; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { if (buffer[i * this.height + j]) { return true; } } } return false; } }

100,000个标记的通用计算时间： 46 ms 。

为什么这么快？乍一看，这种方法似乎很幼稚，并且两种方法中的嵌套循环都不像快速代码。但是，如果仔细看一下代码，您会注意到两种方法的执行时间都不取决于标记的总数。因此，对于固定大小的WxH标记，我们获得复杂度O（W * H * n），即线性！

优化的碰撞缓冲方法

如果确保不以一个字节而是一个位来表示一个像素在内存中，则可以在速度和占用的内存上都改进前一种方法。然而，此优化后的代码非常复杂，并且有点不可思议：

源代码

 export class CollisionBufferBitImpl implements CollisionDetector { private width: number; private height: number; private buffer: Uint8Array; constructor(width: number, height: number) { this.width = Math.ceil(width / 8) * 8; this.height = height; this.buffer = new Uint8Array(this.width * this.height / 8); } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; if (start === end) { buffer[start] = buffer[start] | (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { buffer[start] = buffer[start] | (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { buffer[i] = 255; } buffer[end] = buffer[end] | (255 << (8 - (maxX & 7))); } } } collides(marker: Marker): boolean { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; let sum = 0; if (start === end) { sum = buffer[start] & (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { sum = buffer[start] & (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { sum = buffer[i] | sum; } sum = buffer[end] & (255 << (8 - (maxX & 7))) | sum; } if (sum !== 0) { return true; } } return false; } }

100,000个标记的通用计算时间： 16 ms 。如您所见，逻辑的复杂性证明了其合理性，并使我们可以将泛化的计算速度提高近三倍。

碰撞缓冲区限制

重要的是要了解冲突缓冲区不是R树的完整替代品。它具有更少的功能和更多的限制：

您无法理解标记相交的确切位置。缓冲区仅存储有关哪些像素繁忙而哪些像素不繁忙的数据。因此，不可能执行返回与给定相交的标记列表的操作。
无法删除以前添加的标记。缓冲区不存储有关给定像素中有多少个标记的数据。因此，不可能正确地实现从缓冲器中去除标记的操作。
对元素的大小高度敏感。如果您尝试将占据整个屏幕的标记添加到碰撞缓冲区，性能将急剧下降。
在有限的区域内工作。缓冲区的大小是在创建时设置的，因此无法在其中放置超出该大小的标记。因此，使用这种方法时，必须手动过滤屏幕上未出现的标记。

所有这些限制并不干扰标记泛化问题的解决。现在，此方法已成功用于2gis.ru Beta版中的标记。

但是，要概括地图上的主要签名，要求更加复杂。例如，对于他们来说，有必要确保POI图标不能“杀死”其自己的签名。由于碰撞缓冲区无法区分相交发生的确切位置，因此不允许实现这种逻辑。因此，他们不得不为RBush留下解决方案。

结论

本文显示了从最简单的解决方案到现在使用的解决方案的路径。

R树的使用是第一个重要步骤，它使我们可以多次加速幼稚的实现。它在Floors中效果很好，但实际上，我们仅使用此数据结构功能的一小部分。

放弃了R树并用一个简单的二维数组代替了它，它恰好满足了我们的需要，除此以外，我们的生产率有了更大的提高。

该示例向我们展示了从几个选项中选择一个问题的解决方案以理解并意识到每个选项的局限性是多么重要。限制是重要且有用的，您不必惧怕它们：熟练地将自己限制在微不足道的地方，在真正需要的地方，您可以获得巨大的收益。例如，简化问题的解决方案，或者保护自己免受一整套问题的影响，或者像我们这样，可以多次提高生产率。

WebGL地图上的快速标记归纳