Dealing with Mapbox hidden symbols (2. Resolving features)

2022-09-16 (Updated on 2022-09-24)

thumbnail

I have been working on a utility library for Mapbox GL JS, that deals with symbols hidden by another symbol on the screen. This is the second blog post of the series that will walk you through the development of the library.

Background

In the last blog post of this series, we left the following questions unanswered.

This blog post answers the above questions and also covers how to calculate the size of an icon, which I overlooked in the last blog post.

The library is available at https://github.com/codemonger-io/mapbox-collision-boxes.

I have analyzed version 2.9.2* of Mapbox GL JS (mapbox-gl-js).

* The latest version was 2.10.0 when I was writing this blog post, though I stick to version 2.9.2 for consistency.

Obtaining Tiles and SymbolBuckets

In the last blog post, we have seen Placement#placeLayerBucketPart plays a crucial role in determining which symbols are to appear on the screen. If we examine how this method is invoked, we may figure out how to obtain Tiles and SymbolBuckets.

Resolving SymbolBucket

LayerPlacement#continuePlacement repeats calling Placement#placeLayerBucketPart in style/pauseable_placement.js#L50-L57:

        while (this._currentPartIndex < bucketParts.length) {
            const bucketPart = bucketParts[this._currentPartIndex];
            placement.placeLayerBucketPart(bucketPart, this._seenCrossTileIDs, showCollisionBoxes, bucketPart.symbolInstanceStart === 0);
            this._currentPartIndex++;
            if (shouldPausePlacement()) {
                return true;
            }
        }

Each item in bucketParts that Placement#getBucketParts creates supplies a SymbolBucket to be processed (BucketPart#parameters → TileLayerParameters#bucket). Placement#getBucketParts extracts a SymbolBucket from the Tile given as the third parameter of the method (symbol/placement.js#L233-L234):

    getBucketParts(results: Array<BucketPart>, styleLayer: StyleLayer, tile: Tile, sortAcrossTiles: boolean) {
        const symbolBucket = ((tile.getBucket(styleLayer): any): SymbolBucket);

Thus, if we have a StyleLayer and a Tile, we can also get a SymbolBucket.

Resolving StyleLayer and Tile

LayerPlacement#continuePlacement repeats calling Placement#getBucketParts in style/pauseable_placement.js#L35-L43:

        while (this._currentTileIndex < tiles.length) {
            const tile = tiles[this._currentTileIndex];
            placement.getBucketParts(bucketParts, styleLayer, tile, this._sortAcrossTiles);

            this._currentTileIndex++;
            if (shouldPausePlacement()) {
                return true;
            }
        }

tiles and styleLayer in the above snippet are the parameters given to LayerPlacement#continuePlacement. PauseablePlacement#continuePlacement repeats calling LayerPlacement#continuePlacement in style/pauseable_placement.js#L97-L123 (layerTiles[layer.source] → tiles, and layer → styleLayer):

        while (this._currentPlacementIndex >= 0) {
            const layerId = order[this._currentPlacementIndex];
            const layer = layers[layerId];
            const placementZoom = this.placement.collisionIndex.transform.zoom;
            if (layer.type === 'symbol' &&
                (!layer.minzoom || layer.minzoom <= placementZoom) &&
                (!layer.maxzoom || layer.maxzoom > placementZoom)) {
                // ... truncated for legibility
                const pausePlacement = this._inProgressLayer.continuePlacement(layerTiles[layer.source], this.placement, this._showCollisionBoxes, layer, shouldPausePlacement);
            // ... truncated for legibility
        }

PausePlacement#continuePlacement applies LayerPlacement#continuePlacement only to "symbol" layers, as you can see the following condition at style/pauseable_placement.js#L101:

            if (layer.type === 'symbol' &&

order, layers, and layerTiles in the above snippet are the parameters given to PauseablePlacement#continuePlacement. Style#_updatePlacement calls PauseablePlacement#continuePlacement at style/style.js#L1740:

            this.pauseablePlacement.continuePlacement(this._order, this._layers, layerTiles);

Style#_updatePlacement prepares layerTiles in style/style.js#L1696-L1712:

        const layerTiles = {};

        for (const layerID of this._order) {
            const styleLayer = this._layers[layerID];
            if (styleLayer.type !== 'symbol') continue;

            if (!layerTiles[styleLayer.source]) {
                const sourceCache = this._getLayerSourceCache(styleLayer);
                if (!sourceCache) continue;
                layerTiles[styleLayer.source] = sourceCache.getRenderableIds(true)
                    .map((id) => sourceCache.getTileByID(id))
                    .sort((a, b) => (b.tileID.overscaledZ - a.tileID.overscaledZ) || (a.tileID.isLessThan(b.tileID) ? -1 : 1));
            }
            // ... truncated for legibility
        }

So by mocking the above code, we can obtain the StyleLayer and all the Tiles corresponding to a given layer ID.

Listing Tiles and SymbolBuckets on a layer

To summarize, the outline of the code to list Tiles and SymbolBuckets on a specific layer will be similar to the following,

// suppose we have map: mapboxgl.Map, and layerId: string
const style = map.style;
const layer = style._layers[layerId];
const sourceCache = style._getLayerSourceCache(layer);
const layerTiles = sourceCache.getRenderableIds(true).map(id => sourceCache.getTileByID(id));
for (const tile of layerTiles) {
    const bucket = tile.getBucket(layer);
    // process tile and bucket ...
}

You can find complete code on my GitHub repository that includes additional checks.

Resolving symbol features

In the last blog post, I briefly mentioned that FeatureIndex is important for resolving symbol features. I have reasoned it by looking into Map#queryRenderedFeatures.

Overview of how Map#queryRenderedFeatures works

Map#queryRenderedFeatures calls Style#queryRenderedFeatures at ui/map.js#L1719:

        return this.style.queryRenderedFeatures(geometry, options, this.transform);

Style#queryRenderedFeatures calls queryRenderedSymbols in style/style.js#L1384-L1391:

                queryRenderedSymbols(
                    this._layers,
                    this._serializedLayers,
                    this._getLayerSourceCache.bind(this),
                    queryGeometryStruct.screenGeometry,
                    params,
                    this.placement.collisionIndex,
                    this.placement.retainedQueryData)

queyrRenderedSymbols calls FeatureIndex#lookupSymbolFeatures in source/query_features.js#L95-L103 to obtain features associated with symbols:

        const bucketSymbols = queryData.featureIndex.lookupSymbolFeatures(
                renderedSymbols[queryData.bucketInstanceId],
                serializedLayers,
                queryData.bucketIndex,
                queryData.sourceLayerIndex,
                params.filter,
                params.layers,
                params.availableImages,
                styleLayers);

FeatureIndex#lookupSymbolFeatures resolves and loads GeoJSON features associated with the first argument renderedSymbols[queryData.bucketInstanceId].

So we can resolve features by supplying proper parameters to FeatureIndex#lookupSymbolFeatures.

Preparing parameters for FeatureIndex#lookupSymbolFeatures

We have to provide the following parameters to reproduce the results of a FeatureIndex#lookupSymbolFeatures call in source/query_features.js#L95-L103,

Please note that we do not have to reproduce the first parameter renderedSymbols[queryData.bucketInstanceId] because we need all the features in a SymbolBucket rather than features intersecting a specific bounding box. Please refer to the section "Listing all the feature indices in a SymbolBucket" for how to substitute this parameter.

Parameter: queryData

queryData is bound to a RetainedQueryData in the loop in source/query_features.js#L94-L132:

    for (const queryData of bucketQueryData) {
        const bucketSymbols = queryData.featureIndex.lookupSymbolFeatures(
        // ... truncated for legibility
    }

bucketQueryData is an array of RetainedQueryDatas and initialized in source/query_features.js#L88-L92:

    const bucketQueryData = [];
    for (const bucketInstanceId of Object.keys(renderedSymbols).map(Number)) {
        bucketQueryData.push(retainedQueryData[bucketInstanceId]);
    }
    bucketQueryData.sort(sortTilesIn);

retainedQueryData is Placement#retainedQueryData.

queryRenderedSymbols initializes renderedSymbols at source/query_features.js#L87:

    const renderedSymbols = collisionIndex.queryRenderedSymbols(queryGeometry);

CollisionIndex#queryRenderedSymbols returns an object that maps a bucketInstanceId to indices of features in the SymbolBucket associated with the bucketInstanceId and intersect a given bounding box. We do not rely on CollisionIndex#queryRenderedSymbols, because it covers only visible symbols.

Since we have a list of SymbolBuckets, we can obtain the RetainedQueryData for each SymbolBucket#bucketInstanceId through Placement#retainedQueryData:

// suppose we have placement: Placement, and bucket: SymbolBucket
const queryData = placement.retainedQueryData[bucket.bucketInstanceId];

Parameter: serializedLayers

This parameter is Style#_serializedLayers.

Parameter: params.filter

Map#queryRenderedFeatures specifies an empty object to the params parameter of Style#queryRenderedFeatures by default (options → params in ui/map.js#L1716-L1719):

        options = options || {};
        geometry = geometry || [[0, 0], [this.transform.width, this.transform.height]];

        return this.style.queryRenderedFeatures(geometry, options, this.transform);

So this parameter may be undefined.

Parameter: params.layers

Like params.filter, this parameter may be undefined too.

Parameter: params.availableImages

Style#queryRenderedFeatures specifies Style#_availableImages to this parameter at style/style.js#L1354:

        params.availableImages = this._availableImages;

Parameter: styleLayers

This parameter is Style#_layers.

Listing all the feature indices in a SymbolBucket

What are feature indices that FeatureIndex#lookupSymbolFeatures takes as its first argument (symbolFeatureIndexes)? Although we do not use CollisionIndex#queryRenderedSymbols, seeing what it does should help us to figure out legitimate inputs to FeatureIndex#lookupSymbolFeatures.

I show you the conclusion first because the following analysis is intensive. To list all the feature indices in a SymbolBucket, we can take the featureIndex property from every item in SymbolBucket#symbolInstances, or the iconFeatureIndex property from every item in SymbolBucket#collisionArrays:

// suppose we have bucket: SymbolBucket
// please note that SymbolBucket#symbolInstances is not an ordinary array
for (let i = 0; i < bucket.symbolInstances.length; ++i>) {
    const featureIndex = bucket.symbolInstances.get(i).featureIndex;
    // ... process the feature index
    // ... the collision box can be calculated with bucket.collisionArrays[i]
}

Associating the feature with the collision box is straightforward because featureIndex in the above code corresponds to bucket.collisionArrays[i]: a parameter for collision box recalculation. You may skip the rest of this section to the next section "Calculating the size of an icon".

What does CollisionIndex#queryRenderedSymbols do?

CollisionIndex#queryRenderedSymbols calls GridIndex#query to list features intersecting a given bounding box in symbol/collision_index.js#L360-L361:

        const features = this.grid.query(minX, minY, maxX, maxY)
            .concat(this.ignoredGrid.query(minX, minY, maxX, maxY));

Then it processes every item of features in the loop in symbol/collision_index.js#L366-L396:

        for (const feature of features) {
            const featureKey = feature.key;
            // ... truncated for legibility
            result[featureKey.bucketInstanceId].push(featureKey.featureIndex);
        }

CollisionIndex#queryRenderedSymbols eventually returns result updated in the above code. So what are features that GridIndex#query returns? GridIndex#query returns an array of GridItems intersecting a given bounding box. GridIndex#query constructs these GridItems from the information of boxes and circles that GridIndex stores along with feature keys in GridIndex#bboxes, GridIndex#circles, GridIndex#boxKeys, and GridIndex#circleKeys. Thus, if we track down the origin of GridIndex#boxKeys (let's forget about circles), we should be able to figure out how to get all the feature indices in a SymbolBucket.

The origin of GridIndex#boxKeys

GridIndex#insert pushes a key to GridIndex#boxKeys at symbol/grid_index.js#L73:

        this.boxKeys.push(key);

CollisionIndex#insertCollisionBox defined in symbol/collision_index.js#L401-L406 prepares a key and passes it to GridIndex#insert:

    insertCollisionBox(collisionBox: Array<number>, ignorePlacement: boolean, bucketInstanceId: number, featureIndex: number, collisionGroupID: number) {
        const grid = ignorePlacement ? this.ignoredGrid : this.grid;

        const key = {bucketInstanceId, featureIndex, collisionGroupID};
        grid.insert(key, collisionBox[0], collisionBox[1], collisionBox[2], collisionBox[3]);
    }

Now our concern shifts to the origin of featureIndex that makes up the key in the above snippet.

The origin of featureIndex

In terms of symbol icons, Placement#placeLayerBucketPart.placeSymbol (placeSymbol) calls CollisionIndex#insertCollisionBox in symbol/placement.js#L748-L749:

                this.collisionIndex.insertCollisionBox(placedIconBoxes.box, layout.get('icon-ignore-placement'),
                        bucket.bucketInstanceId, iconFeatureIndex, collisionGroup.ID);

placeSymbol sets iconFeatureIndex at symbol/placement.js#L698:

                iconFeatureIndex = collisionArrays.iconFeatureIndex;

collisionArrays is a CollisionArrays and the third argument of placeSymbol. Then we pursue the origin of CollisionArrays. Placement#placeLayerBucketPart calls placeSymbol at symbol/placement.js#L791 or symbol/placement.js#L795:

                placeSymbol(bucket.symbolInstances.get(symbolIndex), symbolIndex, bucket.collisionArrays[symbolIndex]);

                placeSymbol(bucket.symbolInstances.get(i), i, bucket.collisionArrays[i]);

So CollisionArrays is an item of SymbolBucket#collisionArrays. Placement#placeLayerBucketPart calls SymbolBucket#deserializeCollisionBoxes at symbol/placement.js#L432 to initialize and fill SymbolBucket#collisionArrays:

            bucket.deserializeCollisionBoxes(collisionBoxArray);

SymbolBucket#deserializeCollisionBoxes calls SymbolBucket#_deserializeCollisionBoxesForSymbol that actually sets CollisionArrays#iconFeatureIndex in data/bucket/symbol_bucket.js#L962-L968:

        for (let k = iconStartIndex; k < iconEndIndex; k++) {
            // An icon can only have one box now, so this indexing is a bit vestigial...
            const box: CollisionBox = (collisionBoxArray.get(k): any);
            collisionArrays.iconBox = {x1: box.x1, y1: box.y1, x2: box.x2, y2: box.y2, padding: box.padding, projectedAnchorX: box.projectedAnchorX, projectedAnchorY: box.projectedAnchorY, projectedAnchorZ: box.projectedAnchorZ, tileAnchorX: box.tileAnchorX, tileAnchorY: box.tileAnchorY};
            collisionArrays.iconFeatureIndex = box.featureIndex;
            break; // Only one box allowed per instance
        }

So what is collisionBoxArray given to SymbolBucket#deserializeCollisionBoxes at symbol/placement.js#L432?

The origin of collisionBoxArray

collisionBoxArray is included in TileLayerParameters, and Placement#getBucketParts obtains it from Tile#collisionBoxArray at symbol/placement.js#L242:

        const collisionBoxArray = tile.collisionBoxArray;

Tile#loadVectorData sets Tile#collisionBoxArray at source/tile.js#L245:

        this.collisionBoxArray = data.collisionBoxArray;

Tile#loadVectorData is called at source/geojson_source.js#L372 and source/vector_tile_source.js#L320:

            tile.loadVectorData(data, this.map.painter, message === 'reloadTile');

            tile.loadVectorData(data, this.map.painter);

Above calls happen as a result of VectorTileWorkerSource#loadTile or VectorTileWorkerSource#reloadTile. Both VectorTileWorkerSource#loadTile and VectorTileWorkerSource#reloadTile call WorkerTile#parse to parse the raw vector tile data. WorkerTile#parse outputs the parsed data in source/worker_tile.js#L261-L272:

                callback(null, {
                    buckets: values(buckets).filter(b => !b.isEmpty()),
                    featureIndex,
                    collisionBoxArray: this.collisionBoxArray,
                    glyphAtlasImage: glyphAtlas.image,
                    lineAtlas,
                    imageAtlas,
                    // Only used for benchmarking:
                    glyphMap: this.returnDependencies ? glyphMap : null,
                    iconMap: this.returnDependencies ? iconMap : null,
                    glyphPositions: this.returnDependencies ? glyphAtlas.positions : null
                });

collisionBoxArray (=WorkerTile#collisionBoxArray) in the above code eventually goes to Tile#collisionBoxArray. In terms of symbol icons, WorkerTile#parse calls performSymbolLayout in source/worker_tile.js#L239-L248 to update WorkerTile#collisionBoxArray:

                        performSymbolLayout(bucket,
                            glyphMap,
                            glyphAtlas.positions,
                            iconMap,
                            imageAtlas.iconPositions,
                            this.showCollisionBoxes,
                            availableImages,
                            this.tileID.canonical,
                            this.tileZoom,
                            this.projection);

Please note that bucket is a SymbolBucket in this context, and SymbolBucket#collisionBoxArray points to WorkerTile#collisionBoxArray as it is given to the bucket creation function in source/worker_tile.js#L155-L168:

                const bucket = buckets[layer.id] = layer.createBucket({
                    index: featureIndex.bucketLayerIDs.length,
                    layers: family,
                    zoom: this.zoom,
                    canonical: this.canonical,
                    pixelRatio: this.pixelRatio,
                    overscaling: this.overscaling,
                    collisionBoxArray: this.collisionBoxArray,
                    sourceLayerIndex,
                    sourceID: this.source,
                    enableTerrain: this.enableTerrain,
                    projection: this.projection.spec,
                    availableImages
                });

performSymbolLayout lists features in bucket and calls addFeature at symbol/symbol_layout.js#L322:

            addFeature(bucket, feature, shapedTextOrientations, shapedIcon, imageMap, sizes, layoutTextSize, layoutIconSize, textOffset, isSDFIcon, availableImages, canonical, projection);

addFeature (its internal function addSymbolAtAnchor) calls addSymbol in symbol/symbol_layout.js#L438-L442:

        addSymbol(bucket, anchor, globe, line, shapedTextOrientations, shapedIcon, imageMap, verticallyShapedIcon, bucket.layers[0],
            bucket.collisionBoxArray, feature.index, feature.sourceLayerIndex,
            bucket.index, textPadding, textAlongLine, textOffset,
            iconBoxScale, iconPadding, iconAlongLine, iconOffset,
            feature, sizes, isSDFIcon, availableImages, canonical);

In terms of symbol icons, addSymbol calls evaluateBoxCollisionFeature at symbol/symbol_layout.js#L731:

        iconBoxIndex = evaluateBoxCollisionFeature(collisionBoxArray, collisionFeatureAnchor, anchor, featureIndex, sourceLayerIndex, bucketIndex, shapedIcon, iconPadding, iconRotate);

evaluateBoxCollisionFeature appends an item to collisionBoxArray at symbol/symbol_layout.js#L634:

    collisionBoxArray.emplaceBack(projectedAnchor.x, projectedAnchor.y, projectedAnchor.z, tileAnchor.x, tileAnchor.y, x1, y1, x2, y2, padding, featureIndex, sourceLayerIndex, bucketIndex);

Please note that collisionBoxArray here is identical to WorkerTile#collisionBoxArray.

SymbolBucket#symbolInstances vs SymbolBucket#collisionArrays

According to lines symbol/placement.js#L791 and symbol/placement.js#L795, items of SymbolBucket#symbolInstances match those of SymbolBucket#collisionArrays.

                placeSymbol(bucket.symbolInstances.get(symbolIndex), symbolIndex, bucket.collisionArrays[symbolIndex]);

                placeSymbol(bucket.symbolInstances.get(i), i, bucket.collisionArrays[i]);

And addSymbol also appends an item to SymbolBucket#symbolInstances in symbol/symbol_layout.js#L854-L884:

    bucket.symbolInstances.emplaceBack(
        projectedAnchor.x,
        projectedAnchor.y,
        projectedAnchor.z,
        anchor.x,
        anchor.y,
        placedTextSymbolIndices.right >= 0 ? placedTextSymbolIndices.right : -1,
        placedTextSymbolIndices.center >= 0 ? placedTextSymbolIndices.center : -1,
        placedTextSymbolIndices.left >= 0 ? placedTextSymbolIndices.left : -1,
        placedTextSymbolIndices.vertical  >= 0 ? placedTextSymbolIndices.vertical : -1,
        placedIconSymbolIndex,
        verticalPlacedIconSymbolIndex,
        key,
        textBoxIndex !== undefined ? textBoxIndex : bucket.collisionBoxArray.length,
        textBoxIndex !== undefined ? textBoxIndex + 1 : bucket.collisionBoxArray.length,
        verticalTextBoxIndex !== undefined ? verticalTextBoxIndex : bucket.collisionBoxArray.length,
        verticalTextBoxIndex !== undefined ? verticalTextBoxIndex + 1 : bucket.collisionBoxArray.length,
        iconBoxIndex !== undefined ? iconBoxIndex : bucket.collisionBoxArray.length,
        iconBoxIndex !== undefined ? iconBoxIndex + 1 : bucket.collisionBoxArray.length,
        verticalIconBoxIndex ? verticalIconBoxIndex : bucket.collisionBoxArray.length,
        verticalIconBoxIndex ? verticalIconBoxIndex + 1 : bucket.collisionBoxArray.length,
        featureIndex,
        numHorizontalGlyphVertices,
        numVerticalGlyphVertices,
        numIconVertices,
        numVerticalIconVertices,
        useRuntimeCollisionCircles,
        0,
        textOffset0,
        textOffset1,
        collisionCircleDiameter);

Thus, matching items in SymbolBucket#symbolInstances and SymbolBucket#collisionArrays have the same feature index featureIndex and iconFeatureIndex respectively.

What does FeatureIndex#lookupSymbolFeatures do?

What does FeatureIndex#lookupSymbolFeatures actually do? Does it make sense to specify feature indices (featureIndex) taken from SymbolBucket#symbolInstances to the first parameter (symbolFeatureIndexes)?

FeatureIndex#lookupSymbolFeatures repeats calling FeatureIndex#loadMatchingFeature in data/feature_index.js#L257-L272 (symbolFeatureIndex → featureIndexData.featureIndex):

        for (const symbolFeatureIndex of symbolFeatureIndexes) {
            this.loadMatchingFeature(
                result, {
                    bucketIndex,
                    sourceLayerIndex,
                    featureIndex: symbolFeatureIndex,
                    layoutVertexArrayOffset: 0
                },
                filter,
                filterLayerIDs,
                availableImages,
                styleLayers,
                serializedLayers
            );

        }

FeatureIndex#loadMatchingFeature uses featureIndex to load the feature in data/feature_index.js#L188-L190:

        const sourceLayerName = this.sourceLayerCoder.decode(sourceLayerIndex);
        const sourceLayer = this.vtLayers[sourceLayerName];
        const feature = sourceLayer.feature(featureIndex);

On the other hand, performSymbolLayout enumerates features in SymbolBucket#features and passes them to addFeature one by one in symbol/symbol_layout.js#L197-L324:

    for (const feature of bucket.features) {
        // ... truncated for legibility
        if (shapedText || shapedIcon) {
            addFeature(bucket, feature, shapedTextOrientations, shapedIcon, imageMap, sizes, layoutTextSize, layoutIconSize, textOffset, isSDFIcon, availableImages, canonical, projection);
        }
    }

So where does SymbolBucket#features come from? SymbolBucket#populate initializes and fills SymbolBucket#features (data/bucket/symbol_bucket.js#L475-L626):

    populate(features: Array<IndexedFeature>, options: PopulateParameters, canonical: CanonicalTileID, tileTransform: TileTransform) {
        // ... truncated for legibility
        this.features = [];
        // ... truncated for legibility
        for (const {feature, id, index, sourceLayerIndex} of features) {
            // ... truncated for legibility
            const symbolFeature: SymbolFeature = {
                id,
                text,
                icon,
                index,
                sourceLayerIndex,
                geometry: evaluationFeature.geometry,
                properties: feature.properties,
                type: vectorTileFeatureTypes[feature.type],
                sortKey
            };
            this.features.push(symbolFeature);
            // ... truncated for legibility
        }
        // ... truncated for legibility
    }

WorkerTile#parse calls SymbolBucket#populate at source/worker_tile.js#L171 just after creating a bucket:

                bucket.populate(features, options, this.tileID.canonical, this.tileTransform);

And WorkerTile#parse prepares the first argument features in source/worker_tile.js#L137-L142:

            const features = [];
            for (let index = 0; index < sourceLayer.length; index++) {
                const feature = sourceLayer.feature(index);
                const id = featureIndex.getId(feature, sourceLayerId);
                features.push({feature, id, index, sourceLayerIndex});
            }

So index in the above code eventually becomes featureIndex in SymbolBucket#symbolInstances along with the other related feature information.

Now we are sure that featureIndex properties in SymbolBucket#symbolInstances are consistent with the first parameter symbolFeatureIndexes of FeatureIndex#lookupSymbolFeatures.

Calculating the size of an icon

In the last blog post, I concluded that we could reproduce the scale parameter for icons. However, I found that the function evaluateSizeForZoom to calculate partiallyEvaluatedIconSize was not exported from mapbox-gl-js afterward. So I had to clone evaluateSizeForZoom from mapbox-gl-js to implement my library.

To make evaluateSizeForZoom work, I also had to clone the following types and functions,

You can find these clones in my GitHub repository.

Wrap up

In this blog post, I have shown you how to list Tiles and SymbolBuckets and resolve symbol features. The final loops will look like the following:

// suppose we have map: mapboxgl.Map, and layerId: string
const style = map.style;
const layer = style._layers[layerId];
const sourceCache = style._getLayerSourceCache(layer);
const layerTiles = sourceCache.getRenderableIds(true).map(id => sourceCache.getTileByID(id));
for (const tile of layerTiles) {
    const bucket = tile.getBucket(layer);
    for (let i = 0; i < bucket.symbolInstances.length; ++i>) {
        const featureIndex = bucket.symbolInstances.get(i).featureIndex;
        // ... recalculate the collision box and associate it with the feature
    }
}

I also have covered how to calculate the size of an icon.

While implementing the library, I faced a TypeScript-specific issue where internal types of mapbox-gl-js were not available for TypeScript. In an upcoming blog post, I will share how I have addressed the issue.

Please also check out the library on my GitHub repository!

Appendix

Source code reference

Map

Definition: ui/map.js#L326-L3677

Map#queryRenderedFeatures

Definition: ui/map.js#L1697-L1720

This method implements the Map#queryRenderedFeatures API.

Style

Definition: style/style.js#L135-L1860

Style#_layers

Definition: style/style.js#L148

    _layers: {[_: string]: StyleLayer};
Style#_serializedLayers

Definition: style/style.js#L152

    _serializedLayers: {[_: string]: Object};
Style#_availableImages

Definition: style/style.js#L168

    _availableImages: Array<string>;
Style#queryRenderedFeatures

Definition: style/style.js#L1330-L1396

query_features.queryRenderedSymbols

Definition: source/query_features.js#L79-L149

Style#_updatePlacement

Definition: src/style/style.js#L1692-L1766

This method calls PauseablePlacement#continuePlacement.

Tile

Definition: source/tile.js#L95-L799

Tile#tileID

Definition: source/tile.js#L96

    tileID: OverscaledTileID;
Tile#collisionBoxArray

Definition: source/tile.js#L115

    collisionBoxArray: ?CollisionBoxArray;
Tile#loadVectorData

Definition: source/tile.js#L221-L290

VectorTileWorkerSource

Definition: source/vector_tile_worker_source.js#L140-L309

VectorTileWorkerSource#loadTile

Definition: source/vector_tile_worker_source.js#L177-L238

This method runs on a worker thread.

VectorTileWorkerSource#reloadTile

Definition: source/vector_tile_worker_source.js#L244-L275

This method runs on a worker thread.

WorkerTile

Definition: source/worker_tile.js#L36-L277

WorkerTile#collisionBoxArray

Definition: source/worker_tile.js#L57

    collisionBoxArray: CollisionBoxArray;
WorkerTile#parse

Definition: source/worker_tile.js#L83-L276

symbol_layout.performSymbolLayout

Definition: symbol/symbol_layout.js#L152-L329

WorkerTile#parse calls this function in source/worker_tile.js#L239-L248:

                        performSymbolLayout(bucket,
                            glyphMap,
                            glyphAtlas.positions,
                            iconMap,
                            imageAtlas.iconPositions,
                            this.showCollisionBoxes,
                            availableImages,
                            this.tileID.canonical,
                            this.tileZoom,
                            this.projection);
symbol_layout.addFeature

Definition: symbol/symbol_layout.js#L367-L500

In terms of symbol icons, symbol_layout.performSymbolLayout calls this function at symbol/symbol_layout.js#L322:

            addFeature(bucket, feature, shapedTextOrientations, shapedIcon, imageMap, sizes, layoutTextSize, layoutIconSize, textOffset, isSDFIcon, availableImages, canonical, projection);
symbol_layout.addSymbol

Definition: symbol/symbol_layout.js#L657-L885

This function updates SymbolBucket#symbolInstances in symbol/symbol_layout.js#L854-L884:

    bucket.symbolInstances.emplaceBack(
        projectedAnchor.x,
        projectedAnchor.y,
        projectedAnchor.z,
        anchor.x,
        anchor.y,
        placedTextSymbolIndices.right >= 0 ? placedTextSymbolIndices.right : -1,
        placedTextSymbolIndices.center >= 0 ? placedTextSymbolIndices.center : -1,
        placedTextSymbolIndices.left >= 0 ? placedTextSymbolIndices.left : -1,
        placedTextSymbolIndices.vertical  >= 0 ? placedTextSymbolIndices.vertical : -1,
        placedIconSymbolIndex,
        verticalPlacedIconSymbolIndex,
        key,
        textBoxIndex !== undefined ? textBoxIndex : bucket.collisionBoxArray.length,
        textBoxIndex !== undefined ? textBoxIndex + 1 : bucket.collisionBoxArray.length,
        verticalTextBoxIndex !== undefined ? verticalTextBoxIndex : bucket.collisionBoxArray.length,
        verticalTextBoxIndex !== undefined ? verticalTextBoxIndex + 1 : bucket.collisionBoxArray.length,
        iconBoxIndex !== undefined ? iconBoxIndex : bucket.collisionBoxArray.length,
        iconBoxIndex !== undefined ? iconBoxIndex + 1 : bucket.collisionBoxArray.length,
        verticalIconBoxIndex ? verticalIconBoxIndex : bucket.collisionBoxArray.length,
        verticalIconBoxIndex ? verticalIconBoxIndex + 1 : bucket.collisionBoxArray.length,
        featureIndex,
        numHorizontalGlyphVertices,
        numVerticalGlyphVertices,
        numIconVertices,
        numVerticalIconVertices,
        useRuntimeCollisionCircles,
        0,
        textOffset0,
        textOffset1,
        collisionCircleDiameter);

An internal function addSymbolAtAnchor of symbol_layout.addFeature calls this function in symbol/symbol_layout.js#L438-L442:

        addSymbol(bucket, anchor, globe, line, shapedTextOrientations, shapedIcon, imageMap, verticallyShapedIcon, bucket.layers[0],
            bucket.collisionBoxArray, feature.index, feature.sourceLayerIndex,
            bucket.index, textPadding, textAlongLine, textOffset,
            iconBoxScale, iconPadding, iconAlongLine, iconOffset,
            feature, sizes, isSDFIcon, availableImages, canonical);
symbol_layout.evaluateBoxCollisionFeature

Definition: symbol/symbol_layout.js#L580-L637

This function updates collisionBoxArray at symbol/symbol_layout.js#L634:

    collisionBoxArray.emplaceBack(projectedAnchor.x, projectedAnchor.y, projectedAnchor.z, tileAnchor.x, tileAnchor.y, x1, y1, x2, y2, padding, featureIndex, sourceLayerIndex, bucketIndex);

In terms of symbol icons, symbol_layout.addSymbol calls this function at symbol/symbol_layout.js#L731:

        iconBoxIndex = evaluateBoxCollisionFeature(collisionBoxArray, collisionFeatureAnchor, anchor, featureIndex, sourceLayerIndex, bucketIndex, shapedIcon, iconPadding, iconRotate);

StyleLayer

Definition: style/style_layer.js#L39-L323

SymbolBucket

Definition: data/bucket/symbol_bucket.js#L352-L1119

SymbolBucket#bucketInstanceId

Definition: data/bucket/symbol_bucket.js#L368

    bucketInstanceId: number;
SymbolBucket#features

Definition: data/bucket/symbol_bucket.js#L378

    features: Array<SymbolFeature>;
SymbolBucket#collisionArrays

Definition: data/bucket/symbol_bucket.js#L380

    collisionArrays: Array<CollisionArrays>;

Items in this property match those in SymbolBucket#symbolInstances.

SymbolBucket#deserializeCollisionBoxes initializes and fills this property.

SymbolBucket#symbolInstances

Definition: data/bucket/symbol_bucket.js#L379

    symbolInstances: SymbolInstanceArray;

Items in this property match those in SymbolBucket#collisionArrays.

SymbolBucket#collisionBoxArray

Definition: data/bucket/symbol_bucket.js#L356

SymbolBucket#populate

Definition: data/bucket/symbol_bucket.js#L475-L626

SymbolBucket#deserializeCollisionBoxes

Definition: data/bucket/symbol_bucket.js#L979-L995

This method initializes and fills SymbolBucket#collisionArrays.

SymbolBucket#_deserializeCollisionBoxesForSymbol

Definition: data/bucket/symbol_bucket.js#L943-L977

FeatureIndex

Definition: data/feature_index.js#L54-L312

FeatureIndex#lookupSymbolFeatures

Definition: data/feature_index.js#L244-L274

This method calls FeatureIndex#loadMatchingFeature in data/feature_index.js#L258-L270:

            this.loadMatchingFeature(
                result, {
                    bucketIndex,
                    sourceLayerIndex,
                    featureIndex: symbolFeatureIndex,
                    layoutVertexArrayOffset: 0
                },
                filter,
                filterLayerIDs,
                availableImages,
                styleLayers,
                serializedLayers
            );
FeatureIndex#loadMatchingFeature

Definition: data/feature_index.js#L172-L240

This method loads the GeoJSON feature(s) of a symbol from the vector tile data.

CollisionIndex

Definition: symbol/collision_index.js#L64-L465

CollisionIndex#queryRenderedSymbols

Definition: symbol/collision_index.js#L341-L399

CollisionIndex#insertCollisionBox

Definition: symbol/collision_index.js#L401-L406

    insertCollisionBox(collisionBox: Array<number>, ignorePlacement: boolean, bucketInstanceId: number, featureIndex: number, collisionGroupID: number) {
        const grid = ignorePlacement ? this.ignoredGrid : this.grid;

        const key = {bucketInstanceId, featureIndex, collisionGroupID};
        grid.insert(key, collisionBox[0], collisionBox[1], collisionBox[2], collisionBox[3]);
    }

GridIndex

Definition: symbol/grid_index.js#L24-L341

GridIndex#bboxes

Definition: symbol/grid_index.js#L29

    bboxes: Array<number>;

Please see also GridIndex#boxKeys.

GridIndex#boxKeys

Definition: symbol/grid_index.js#L26

    boxKeys: Array<any>;

This property stores the feature key associated with the box at the same index in GridIndex#bboxes.

GridIndex#insert updates this property.

GridIndex#circles

Definition: symbol/grid_index.js#L30

    circles: Array<number>;

Please see also GridIndex#circleKeys.

GridIndex#circleKeys

Definition: symbol/grid_index.js#L25

    circleKeys: Array<any>;

This property stores the feature key associated with the circle at the same index in GridIndex#circles.

GridIndex#insert

Definition: symbol/grid_index.js#L71-L78

This method pushes a given key to GridIndex#boxKeys at symbol/grid_index.js#L73:

        this.boxKeys.push(key);
GridIndex#query

Definition: symbol/grid_index.js#L163-L165

    query(x1: number, y1: number, x2: number, y2: number, predicate?: any): Array<GridItem> {
        return (this._query(x1, y1, x2, y2, false, predicate): any);
    }

Please see also GridIndex#_query.

GridIndex#_query

Definition: symbol/grid_index.js#L98-L137

This method calls GridIndex#_forEachCell at symbol/grid_index.js#L134:

            this._forEachCell(x1, y1, x2, y2, this._queryCell, result, queryArgs, predicate);
GridIndex#_forEachCell

Definition: symbol/grid_index.js#L291-L303

    _forEachCell(x1: number, y1: number, x2: number, y2: number, fn: any, arg1: any, arg2?: any, predicate?: any) {
        const cx1 = this._convertToXCellCoord(x1);
        const cy1 = this._convertToYCellCoord(y1);
        const cx2 = this._convertToXCellCoord(x2);
        const cy2 = this._convertToYCellCoord(y2);

        for (let x = cx1; x <= cx2; x++) {
            for (let y = cy1; y <= cy2; y++) {
                const cellIndex = this.xCellCount * y + x;
                if (fn.call(this, x1, y1, x2, y2, cellIndex, arg1, arg2, predicate)) return;
            }
        }
    }

This method applies fn to every cell intersecting a given bounding box.

In the context of GridIndex#query, fn is GridIndex#_queryCell.

GridIndex#_queryCell

Definition: symbol/grid_index.js#L175-L240

This method collects boxes and circles in a specified cell intersecting a given bounding box.

GridItem

Definition: symbol/grid_index.js#L3-L9

type GridItem = {
    key: any,
    x1: number,
    y1: number,
    x2: number,
    y2: number
};

Placement

Definition: symbol/placement.js#L192-L1184

Placement#retainedQueryData

Definition: symbol/placement.js#L205

    retainedQueryData: {[_: number]: RetainedQueryData};

Please see also RetainedQueryData.

Placement#getBucketParts

Definition: symbol/placement.js#L233-L333

LayerPlacement#continuePlacement calls this method at style/pauseable_placement.js#L37:

            placement.getBucketParts(bucketParts, styleLayer, tile, this._sortAcrossTiles);

Please see also the corresponding section in the previous blog post.

Placement#placeLayerBucketPart

Definition: symbol/placement.js#L386-L808

LayerPlacement#continuePlacement calls this method at style/pauseable_placement.js#L52:

            placement.placeLayerBucketPart(bucketPart, this._seenCrossTileIDs, showCollisionBoxes, bucketPart.symbolInstanceStart === 0);

Please see also the corresponding section in the previous blog post.

Placement#placeLayerBucketPart.placeSymbol

Definition: symbol/placement.js#L439-L784

RetainedQueryData

Definition: symbol/placement.js#L87-L105

export class RetainedQueryData {
    bucketInstanceId: number;
    featureIndex: FeatureIndex;
    sourceLayerIndex: number;
    bucketIndex: number;
    tileID: OverscaledTileID;
    featureSortOrder: ?Array<number>
    // ... truncated for legibility
}

BucketPart

Definition: symbol/placement.js#L183-L188

export type BucketPart = {
    sortKey?: number | void,
    symbolInstanceStart: number,
    symbolInstanceEnd: number,
    parameters: TileLayerParameters
};

Please see also TileLayerParameters.

TileLayerParameters

Definition: symbol/placement.js#L169-L181

type TileLayerParameters = {
    bucket: SymbolBucket,
    layout: any,
    posMatrix: Mat4,
    textLabelPlaneMatrix: Mat4,
    labelToScreenMatrix: ?Mat4,
    scale: number,
    textPixelRatio: number,
    holdingForFade: boolean,
    collisionBoxArray: ?CollisionBoxArray,
    partiallyEvaluatedTextSize: any,
    collisionGroup: any
};

PauseablePlacement

Definition: style/pauseable_placement.js#L62-L132

PauseablePlacement#continuePlacement

Definition: style/pauseable_placement.js#L89-L126

This method calls LayerPlacement#continuePlacement.

Style#_updatePlacement calls this method at style/style.js#L1740:

            this.pauseablePlacement.continuePlacement(this._order, this._layers, layerTiles);

LayerPlacement

Definition: style/pauseable_placement.js#L15-L60

LayerPlacement#continuePlacement

Definition: style/pauseable_placement.js#L32-L59

This method calls

PauseablePlacement#continuePlacement calls this method at style/pauseable_placement.js#L109:

                const pausePlacement = this._inProgressLayer.continuePlacement(layerTiles[layer.source], this.placement, this._showCollisionBoxes, layer, shouldPausePlacement);

symbol_size.SizeData

Definition: symbol/symbol_size.js#L15-L32

export type SizeData = {
    kind: 'constant',
    layoutSize: number
} | {
    kind: 'source'
} | {
    kind: 'camera',
    minZoom: number,
    maxZoom: number,
    minSize: number,
    maxSize: number,
    interpolationType: ?InterpolationType
} | {
    kind: 'composite',
    minZoom: number,
    maxZoom: number,
    interpolationType: ?InterpolationType
};

symbol_size.InterpolatedSize

Definition: symbol/symbol_size.js#L34-L37

export type InterpolatedSize = {|
    uSize: number,
    uSizeT: number
|};

symbol_size.evaluateSizeForZoom

Definition: symbol/symbol_size.js#L92-L118

interpolate.InterpolationType

Definition: style-spec/expression/definitions/interpolate.js#L17-L20

export type InterpolationType =
    { name: 'linear' } |
    { name: 'exponential', base: number } |
    { name: 'cubic-bezier', controlPoints: [number, number, number, number] };

Interpolate.interpolationFactor

Definition: style-spec/expression/definitions/interpolate.js#L45-L57

interpolate.exponentialInterpolation

Definition: style-spec/expression/definitions/interpolate.js#L255-L266

util.interpolate

Definition: style-spec/util/interpolate.js#L5-L7

export function number(a: number, b: number, t: number): number {
    return (a * (1 - t)) + (b * t);
}

util.clamp

Definition: util/util.js#L211-L213

export function clamp(n: number, min: number, max: number): number {
    return Math.min(max, Math.max(min, n));
}

SymbolInstanceArray

Definition: data/array_types.js#L1188-L1198

Each item in this array is SymbolInstanceStruct.

SymbolInstanceStruct

Definition: data/array_types.js#L1146-L1179

CollisionArrays

Definition: data/bucket/symbol_bucket.js#L90-L99

export type CollisionArrays = {
    textBox?: SingleCollisionBox;
    verticalTextBox?: SingleCollisionBox;
    iconBox?: SingleCollisionBox;
    verticalIconBox?: SingleCollisionBox;
    textFeatureIndex?: number;
    verticalTextFeatureIndex?: number;
    iconFeatureIndex?: number;
    verticalIconFeatureIndex?: number;
};
Tweet