WebWorker 在文本标注中的应用

建议 未结 0 74
专注的一批
悬赏:20飞吻
在之前数据瓦片方案的介绍中,我们提到过希望将瓦片裁剪放入 WebWorker 中进行,以保证主线程中用户流畅的地图交互(缩放、平移、旋转)。
之前我们的例子没有使用 WebWorker,似乎也并不影响交互。但是本文介绍的针对 Polygon 要素的文本标注方案,将涉及复杂的多边形难抵极运算,如果不放在 WebWorker 中运算将完全卡死无法交互。题图为全球海洋文本的标注效果,数据来自 geojson.xyz,DEMO 地址如下:
https://xiaoiver.github.io/custom-mapbox-layer/?path=/story/textlayer--polygon-feature
首先我们来看看如何确定一个多边形的文本标注锚点,即难抵极的计算方法。
一、难抵极算法
难抵极(Pole of inaccessibility / PIA)顾名思义,就是从海岸线出发大陆上最难到达的点。直观上来看就是陆地上距离海岸线最远的点(下图的红点)。从几何角度看就是以形状内的各个点为圆心作圆,这些圆不能与边界(海岸线)相交,以难抵极为圆心的圆半径最大。要注意难抵极和 centroid几何中心不是一个概念。

论文「Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth」提出的是一种基于蒙特卡洛方法的算法。核心思路是迭代计算候选区域(经纬度),平均分成 21 * 21 个候选点,分别计算到海岸线的最大距离,然后以该点为中心,以  比例缩小得到新的区域。
而 Mapbox Polylabel使用了基于网格的算法,同样使用迭代找到指定精度下的 PIA。相比上面的方法更快而且是 global optimum的。

算法步骤如下:
1、以多边形的包围盒作为初始网格,使用 ray casting 计算网格中心到多边形边界的有向距离(下图的 dist 负数表示在形外)。
2、按照该有向距离排序,将网格加入优先级队列,同时计算该网格内的最大距离 max = dist + radius 其中radius = cell_size * sqrt(2) / 2
3、如果当前网格有向距离比之前最佳网格更大,更新最佳网格
4、网格出队,如果网格距离大于目前最大距离(指定精度下 max - best_dist > precision ),继续划分网格,将 4 个子网格入队,继续迭代回到 1。
5、当优先级队列为空时,迭代终止。此时找到指定精度下的 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] < minY) minY = p[1];
if (!i || p[0] > 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 < maxY; y += cellSize) {
// Cell 构造函数中会调用 pointToPolygonDist 计算中点到多边形的距离
// @see https://github.com/mapbox/polylabel/blob/master/polylabel.js#L90-L109
cellQueue.push(new Cell(x + h, y + h, h, polygon));
}
}
// 初始状态以多边形几何中心作为候选网格
// @see https://math.stackexchange.com/a/700059
var bestCell = getCentroidCell(polygon);
while (cellQueue.length) {
// 网格出队
var cell = cellQueue.pop();
// 发现距离多边形边界更远的网格,更新最佳网格
if (cell.d > 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

分类涉及到多边形的有向面积计算,正数代表顺时针方向的 exterior ring,而负数代表逆时针方向的 interior ring:
// mapbox/utils/classify_rings.js
export function calculateSignedArea(ring: Array<Point>): 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 还有很大的改进空间,例如以下三个方面:
1、考虑线程间 Transferable 数据传输
2、合并连续请求
3、在运行时拼接公共代码,减少构建打包大小
现在我们将数据瓦片的索引以及查询都放在了 WebWorker 中完成,如果要进一步解放主线程,顶点数据的组装、包括之前介绍过的顶点压缩方案也可以挪进来。事实上 Mapbox 也是这么做的,另外为了加快线程间数据传输速度,数据格式在设计上也需要考虑 Transferable,由于线程上下文转移时不需要拷贝操作,在大数据量传输时将获得较大的效率提升。
// web_worker_transfer.js
type SerializedObject = { [string]: Serialized };
export type Serialized =
| void
| boolean
//...省略其他类型
| ArrayBuffer
| Array<Serialized>
| SerializedObject;
// 向 Worker 传递对象前,需要进行序列化
export function serialize(input: mixed, transferables?: Array<Transferable>): Serialized {}
function(){ //外汇返佣http://www.fx61.com
由于相机更新时都需要向 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 构建出三个 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 的一个最佳实践,甚至要优于很多论文中的方案。
回帖
  • 消灭零回复