在之前数据瓦片方案的介绍中,我们提到过希望将瓦片裁剪放入 WebWorker 中进行,以保证主线程中用户流畅的地图交互(缩放、平移、旋转)。
之前我们的例子没有使用 WebWorker,似乎也并不影响交互。但是本文介绍的针对 Polygon 要素的文本标注方案,将涉及复杂的多边形难抵极运算,如果不放在 WebWorker 中运算将完全卡死无法交互。题图为全球海洋文本的标注效果,数据来自geojson.xyz,DEMO 地址如下:
首先我们来看看如何确定一个多边形的文本标注锚点,即难抵极的计算方法。
难抵极(Pole of inaccessibility / PIA)顾名思义,就是从海岸线出发大陆上最难到达的点。直观上来看就是陆地上距离海岸线最远的点(下图的红点)。从几何角度看就是以形状内的各个点为圆心作圆,这些圆不能与边界(海岸线)相交,以难抵极为圆心的圆半径最大。要注意难抵极和 centroid几何中心不是一个概念。
论文「Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth」提出的是一种基于蒙特卡洛方法的算法。核心思路是迭代计算候选区域(经纬度),平均分成 21 * 21 个候选点,分别计算到海岸线的最大距离,然后以该点为中心,以 比例缩小得到新的区域。
而 Mapbox Polylabel 使用了基于网格的算法,同样使用迭代找到指定精度下的 PIA。相比上面的方法更快而且是 global optimum 的。
算法步骤如下:
代码细节如下:
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 的基本知识以及动态创建方法(Mapbox 目前的 rollup 打包方案会用到)
我们需要定义好主线程与 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 还有很大的改进空间,例如以下三个方面:
现在我们将数据瓦片的索引以及查询都放在了 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 {}
由于相机更新时都需要向 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 的文本标注方案。
作者:潘与其
链接:https://zhuanlan.zhihu.com/p/74899909
Web Worker (工作线程) 是 HTML5 中提出的概念,分为两种类型,专用线程(Dedicated Web Worker) 和共享线程(Shared Web Worker)。专用线程仅能被创建它的脚本所使用
JavaScript从使用开初就一直基于事件循环的单线程运行模型,即使是成功进军后端开发的Nodejs也没有改变这一模型。那么对于计算密集型的应用,我们必须创建新进程来执行运算,然后执行进程间通信实现传参和获取运算结果
随着前端应用场景的逐渐复杂化,伴随而来的对大数据的处理就不可避免。 那么今天就以一个真实的应用场景为例来谈谈前端中如何通过子线程来处理大数据。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!