WebWorker 在文本标注中的应用
作者：潘与其 – 蚂蚁金服前端工程师 – 喜欢图形学、可视化
在之前数据瓦片方案的介绍中，我们提到过希望将瓦片裁剪放入 WebWorker 中进行，以保证主线程中用户流畅的地图交互（缩放、平移、旋转）。
之前我们的例子没有使用 WebWorker，似乎也并不影响交互。但是本文介绍的针对 Polygon 要素的文本标注方案，将涉及复杂的多边形难抵极运算，如果不放在 WebWorker 中运算将完全卡死无法交互。题图为全球海洋文本的标注效果，数据来自 geojson.xyz，DEMO 地址如下：
https://xiaoiver.github.io/custom-mapbox-layer/?path=/story/textlayer–polygon-feature
首先我们来看看如何确定一个多边形的文本标注锚点，即难抵极的计算方法。
难抵极算法
难抵极（Pole of inaccessibility / PIA） [1] 顾名思义，就是从海岸线出发大陆上最难到达的点。直观上来看就是陆地上距离海岸线最远的点（下图的红点）。从几何角度看就是以形状内的各个点为圆心作圆，这些圆不能与边界（海岸线）相交，以难抵极为圆心的圆半径最大。要注意难抵极和 centroid几何中心不是一个概念。
论文「Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth」 [2] 提出的是一种基于蒙特卡洛方法的算法。核心思路是迭代计算候选区域（经纬度），平均分成 21 * 21 个候选点，分别计算到海岸线的最大距离，然后以该点为中心，以 比例缩小得到新的区域。
而 Mapbox Polylabel [3] 使用了基于网格的算法，同样使用迭代找到指定精度下的 PIA。相比上面的方法更快而且是 global optimum [4] 的。
算法步骤如下：
-
以多边形的包围盒作为初始网格，使用 ray casting 计算网格中心到多边形边界的有向距离（下图的 dist 负数表示在形外）。
-
按照该有向距离排序，将网格加入优先级队列，同时计算该网格内的最大距离
max = dist + radius其中radius = cell_size * sqrt(2) / 2 -
如果当前网格有向距离比之前最佳网格更大，更新最佳网格
-
网格出队，如果网格距离大于目前最大距离（指定精度下
max - best_dist > precision），继续划分网格，将 4 个子网格入队，继续迭代回到 1。 -
当优先级队列为空时，迭代终止。此时找到指定精度下的 PIA
代码细节如下：
function polylabel(polygon, precision, debug) {
precision = precision || 1.0; // 精度
// 计算多边形的最小包围盒
var minX, minY, maxX, maxY;
for (var i = 0; i < polygon[0].length; i++) {
var p = polygon[0][i];
if (!i || p[0] < minX) minX = p[0];
if (!i || p[1] maxX) maxX = p[0];
if (!i || p[1] > maxY) maxY = p[1];
}
var width = maxX - minX;
var height = maxY - minY;
// 网格尺寸
var cellSize = Math.min(width, height);
var h = cellSize / 2;
// 优先级队列
var cellQueue = new Queue(null, compareMax);
// 划分初始网格，全部入队
for (var x = minX; x < maxX; x += cellSize) {
for (var y = minY; y bestCell.d) {
bestCell = cell;
if (debug) console.log('found best %d after %d probes', Math.round(1e4 * cell.d) / 1e4, numProbes);
}
// 小于精度阈值，不需要继续划分
// Cell 构造函数中会计算 max this.max = this.d + this.h * Math.SQRT2;
if (cell.max - bestCell.d <= precision) continue;
// 划分成 4 个子网格
h = cell.h / 2;
cellQueue.push(new Cell(cell.x - h, cell.y - h, h, polygon));
cellQueue.push(new Cell(cell.x + h, cell.y - h, h, polygon));
cellQueue.push(new Cell(cell.x - h, cell.y + h, h, polygon));
cellQueue.push(new Cell(cell.x + h, cell.y + h, h, polygon));
numProbes += 4;
}
// 返回 PIA，以最佳网格中心点
return [bestCell.x, bestCell.y];
}
现在我们解决了给定多边形中找到锚点的问题，但是 GeoJSON 的 Polygon 要素可能由多个子多边形组成（下图中的空洞），我们需要找到多边形的 outer ring 最外层边界，以此作为目标多边形供后续应用上述难抵极算法。
多边形分类
一个多边形可能由多个环组成，对于这些环首先需要进行分类：exterior ring & interior ring [5]
分类涉及到多边形的有向面积计算，正数代表顺时针方向的 exterior ring，而负数代表逆时针方向的 interior ring：
// mapbox/utils/classify_rings.js
export function calculateSignedArea(ring: Array): number {
let sum = 0;
for (let i = 0, len = ring.length, j = len - 1, p1, p2; i < len; j = i++) {
p1 = ring[i];
p2 = ring[j];
sum += (p2.x - p1.x) * (p1.y + p2.y);
}
return sum;
}
根据环的方向计算，需要确保 exterior ring 在 interior 之前，在寻找难抵极时只使用 exterior ring 作为锚点：
// mapbox/utils/classify_rings.js
const polygons = [];
let polygon,
ccw;
for (let i = 0; i < len; i++) {
// 计算有向面积
const area = calculateSignedArea(rings[i]);
if (area === 0) continue;
(rings[i]: any).area = Math.abs(area);
if (ccw === undefined) ccw = area < 0;
// 下次出现逆时针 interior ring 时再添加
if (ccw === area < 0) {
if (polygon) polygons.push(polygon);
polygon = [rings[i]];
} else {
// exterior ring 直接添加
(polygon: any).push(rings[i]);
}
}
if (polygon) polygons.push(polygon);
现在我们就找到了难抵极作为多边形的锚点，使用之前我们介绍过的文字渲染方法就能完成标注了。但显然计算难抵极十分复杂，每次发生地图交互尤其是连续缩放、平移、旋转时，都需要重新计算，我亲测会导致主线程完全卡住，为了保证主线程流畅的交互，需要将这部分计算挪到 WebWorker 中进行。
引入 WebWorker
关于 WebWorker 的基本知识以及动态创建方法（Mapbox 目前的 rollup 打包方案会用到），推荐阅读 的文章：
https://zhuanlan.zhihu.com/p/59981684
我们需要定义好主线程与 WebWorker 通信的数据格式，例如：
// https://github.com/xiaoiver/custom-mapbox-layer/blob/master/src/worker/loadData.ts#L10
interface IPayload {
command: string;
params: any;
status: 'success'|'failure';
}
const ctx: Worker = self as any;
ctx.addEventListener('message', async ({ data: payload }) => {
const { command, params } = payload;
switch (command) {
// 加载数据 & 创建瓦片索引
case 'loadData': {
ctx.postMessage({
command: 'tileIndexLoaded',
status: 'success'
});
}
// 获取需要渲染的瓦片信息
case 'getTiles': {
}
}
});
我们将 GeoJSON 数据请求和数据瓦片索引的创建都放在 WebWorker 中进行：
// https://github.com/xiaoiver/custom-mapbox-layer/blob/master/src/layers/TextLayer.ts#L105-L118
import * as Worker from 'worker-loader!../worker/worker';
// 主线程初始化
initWorker() {
this.worker = new Worker();
this.worker.addEventListener('message', this.handleWorkerMessage);
// 通知 Worker 请求 GeoJSON 数据并创建数据瓦片索引
this.worker.postMessage({
command: 'loadData',
params: {
url: this.url,
type: 'geojson',
isCluster: false
}
});
}
WebWorker 中使用 fetch API 获取 GeoJSON，随后创建数据瓦片索引，这部分之前文章介绍过就不再赘述了。
在我们的例子中，当主线程请求 WebWorker 返回当前视口包含的数据瓦片时，WebWorker 会计算出瓦片包含的 Polygon 要素的难抵极，不影响主线程的交互：
// https://github.com/xiaoiver/custom-mapbox-layer/blob/master/src/worker/feature/text.ts#L15-L26
// 多边形环分类
for (const polygon of classifyRings(rings, 0)) {
// 计算多边形的难抵极
const poi = findPoleOfInaccessibility(polygon, 16);
// 组装该瓦片供文本渲染的结构
tile.textFeatures.push({
position: [poi.x, poi.y], // 锚点位置
text, // 文本内容
});
}
后续改进
关于 WebWorker 还有很大的改进空间，例如以下三个方面：
-
考虑线程间 Transferable 数据传输
-
合并连续请求
-
在运行时拼接公共代码，减少构建打包大小
现在我们将数据瓦片的索引以及查询都放在了 WebWorker 中完成，如果要进一步解放主线程，顶点数据的组装、包括之前介绍过的顶点压缩方案也可以挪进来。事实上 Mapbox 也是这么做的，另外为了加快线程间数据传输速度，数据格式在设计上也需要考虑 Transferable [6] ，由于线程上下文转移时不需要拷贝操作，在大数据量传输时将获得较大的效率提升。
// web_worker_transfer.js
type SerializedObject = { [string]: Serialized };
export type Serialized =
| void
| boolean
//...省略其他类型
| ArrayBuffer
| Array
| SerializedObject;
// 向 Worker 传递对象前，需要进行序列化
export function serialize(input: mixed, transferables?: Array): Serialized {}
由于相机更新时都需要向 Worker 发送更新瓦片消息，在用户连续 zoomIn/Out 时，会连续发送大量消息到 Worker。我们必须要处理这种情况以减轻 Worker 压力。最简单的办法就是 throttle 节流，但缺点是阈值无法根据数据量动态设定，有可能 Worker 海量数据还没有处理完，下一条更新请求已经到了。因此 Mapbox 的做法是合并多条请求，在主线程中维护一个简单的状态机：
/**
* While processing `loadData`, we coalesce all further
* `loadData` messages into a single call to _loadData
* that will happen once we've finished processing the
* first message. {@link GeoJSONSource#_updateWorkerData}
* is responsible for sending us the `coalesce` message
* at the time it receives a response from `loadData`
*
* State: Idle
* ↑ |
* 'coalesce' 'loadData'
* | (triggers load)
* | ↓
* State: Coalescing
* ↑ |
* (triggers load) |
* 'coalesce' 'loadData'
* | ↓
* State: NeedsLoadData
*/
coalesce() {
if (this._state === 'Coalescing') {
this._state = 'Idle';
} else if (this._state === 'NeedsLoadData') {
this._state = 'Coalescing';
this._loadData();
}
}
最后，从构建打包的角度看，很明显 WebWorker 和主线程代码存在大量共用代码，将公共代码抽出并在运行时拼接，动态创建 WebWorker 是不错的方案。但目前 Webpack4 暂时还不支持多种 target（web + webworker）混合的输出模式，相关 ISSUE。如果后续支持，配合 SplitChunksPlugin 应该能解决在 Worker 和不同 entry 之间共享代码的问题。
因此 Mapbox 选择了 rollup 构建 [7] 出三个 chunk（main，worker 以及 shared），在运行时拼接共用代码动态创建 WebWorker：
// https://github.com/mapbox/mapbox-gl-js/blob/master/rollup/bundle_prelude.js
var shared, worker, mapboxgl;
// define gets called three times: one for each chunk. we rely on the order
// they're imported to know which is which
function define(_, chunk) {
if (!shared) {
shared = chunk;
} else if (!worker) {
worker = chunk;
} else {
var workerBundleString = 'var sharedChunk = {}; (' + shared + ')(sharedChunk); (' + worker + ')(sharedChunk);'
var sharedChunk = {};
shared(sharedChunk);
mapboxgl = chunk(sharedChunk);
mapboxgl.workerUrl = window.URL.createObjectURL(new Blob([workerBundleString], { type: 'text/javascript' }));
}
}
介绍完了 Point 和 Polygon 的文本标注方案，下篇文章中最复杂的 LineString 终于要登场了。这也是我认为 Mapbox 的一个最佳实践，甚至要优于很多论文中的方案。
https://zhuanlan.zhihu.com/p/74899909
参考
-
^ Wiki – Pole_of_inaccessibility https://en.wikipedia.org/wiki/Pole_of_inaccessibility
-
^ Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth https://docs.google.com/uc?id=0B_xuyENh5ksFOGE1ZmU5ZjQtNjZmNi00ZTRlLWIyZGUtNmRiNDhhNzRkYTA1&export=download&hl=en
-
^ Mapbox – Polylabel https://github.com/mapbox/polylabel
-
^ Wiki – Local_optimum https://en.wikipedia.org/wiki/Local_optimum
-
^ ArcGIS -IRing_IsExterior https://enterprise.arcgis.com/en/sdk/latest/windows/IRing_IsExterior.html
-
^ MDN – Transferable https://developer.mozilla.org/en-US/docs/Web/API/Transferable
-
^ Mapbox Rollup 构建方案 https://github.com/mapbox/mapbox-gl-js/blob/master/rollup.config.js
About The Author
