WebWorker在文本标注中的应用

更新日期: 2019-09-08阅读: 1.6k标签: WebWorker

在之前数据瓦片方案的介绍中,我们提到过希望将瓦片裁剪放入 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 的。


基于网格的 PIA 算法

算法步骤如下:

  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 最外层边界,以此作为目标多边形供后续应用上述难抵极算法。


GeoJSON Polygon

多边形分类

一个多边形可能由多个环组成,对于这些环首先需要进行分类: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 打包方案会用到)

我们需要定义好主线程与 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 {}

由于相机更新时都需要向 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


链接: https://www.fly63.com/article/detial/5805

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!