MapLibre induces self-intersection in valid polygon

[leofuhrmann]

maplibre-gl-js version: 3.3.1

browser: Firefox 118

Steps to Trigger Behavior

1. Create vector tile from example GeoJSON (see below) using ogr2ogr ogr2ogr -f MVT -dsco EXTENT=16384 -dsco MINZOOM=15 -dsco MAXZOOM=15 -dsco SIMPLIFICATION=0 tiles example.json.
2. Serve vector tile using tilejson.
3. Create a map using MapLibre GL JS, rendering fill and line for the example data's polygon.
4. Create GeoJSON from vector tile for comparison.

Link to Demonstration

You can see a demonstration here: https://jsbin.com/xadehayoru/edit?html,output

Comment out the layers or remove the comments to hide/show expected/actual behavior.

Expected Behavior

The polygon is rendered without self-intersection:

Note: This polygon is created using geoJSON, which was converted from the vector tile (using ogr2ogr -f GeoJSON -t_srs EPSG:4326 json_from_tile.geojson tiles/15/17270/10767.pbf).

Actual Behavior

The polygon is rendered with an induced self-intersection (bottom-right), creating visual artifacts:

Example Data

example.json

{
    "type": "FeatureCollection",
    "name": "example",
    "features": [
        {
            "type": "Feature",
            "properties": {},
            "geometry": {
                "type": "Polygon",
                "coordinates": [
                    [
                        [
                            9.740717350247355,
                            52.376506165582903
                        ],
                        [
                            9.740708999892272,
                            52.376505583226404
                        ],
                        [
                            9.7407136,
                            52.3765034
                        ],
                        [
                            9.740707673725138,
                            52.376504711225316
                        ],
                        [
                            9.740708229712421,
                            52.376498958445339
                        ],
                        [
                            9.740717350247355,
                            52.376506165582903
                        ]
                    ]
                ]
            }
        }
    ]
}

[HarelM]

Is this a duplicate of #1830?

[leofuhrmann]

Is this a duplicate of #1830?

No, because the issue you mentioned addresses the rendering of already invalid polygons, if I understood correctly. The current issue deals with a valid polygon (without intersections), that seemingly becomes invalid during rendering.

[HarelM]

It might be that the conversion accuracy is problematic. I would be surprised if the rendering is causing the invalid polygon. Did you check that the vector tile data is correct and not intersecting itself? You can use the https://github.com/mapbox/vector-tile-js package to inspect a single tile data and extract the polygon, I would start there. If the data is not intersecting itself there then the issue might be with the transition of the data to the worker/GPU, but I would be surprised if this is the case. Nevertheless, everything is possible :-)

[leofuhrmann]

Thanks for your reply. I have already checked the validity of the polygon using QGIS. It does not contain any self-intersection.

I've checked again using the suggested tool in combination with Turf.js, which finds no intersection in the polygon, read directly from the vector tile. Here is my code to do this (install the necessary packages: npm install @turf/turf @mapbox/vector-tile pbf zlib):

const VectorTile = require('@mapbox/vector-tile').VectorTile;
const Protobuf = require('pbf');
const zlib = require('zlib');
const fs = require('fs');
const turf = require('@turf/turf');

const fileBuffer = fs.readFileSync('./10767.pbf');

zlib.gunzip(fileBuffer, (err, buffer) => {

    const tile = new VectorTile(new Protobuf(buffer));
    const jsonData = tile.layers.example.feature(0).toGeoJSON(17270, 10767, 15);

    // Find intersections
    const intersectionPoints = turf.kinks(jsonData);
    console.log(`Found ${intersectionPoints.features.length} intersections.`);

    // Output: Found 0 intersections.
});

If the data is not intersecting itself there then the issue might be with the transition of the data to the worker/GPU, but I would be surprised if this is the case. Nevertheless, everything is possible :-)

Do you have ideas on how to debug this possibility?

[HarelM]

I would try and simplify this issue first, make a polygon with 4-6 points, try even a geojson as example to see if it reproduces there and then follow the code that uses the shaders programs to see what is sent to the GPU in the vertices. It might be a limitation of the data sent to the GPU, IDK...

[leofuhrmann]

I have updated my first comment and tried my best to include a minimal example to reduce the problem. It uses a valid GeoJSON, from which a vector tile is created. The vector tile is converted back to GeoJSON to check the validity of the tile's content. Both are displayed in the demonstration (https://jsbin.com/xadehayoru/edit?html,output). One should clearly see the intersection in the rendered tile.

So far, I couldn't look into the rendering process, but as the geojson is rendered correctly, this seems to be connected to the "unpacking" or rendering of vector tiles.

[HarelM]

The geojson's accuracy is a lot higher than the tile's accuracy because the tile max zoom is 15 while the geojson max zoom is unlimited (24 in this example). When I add the following property to the geojson source I get the same results: maxzoom: 15.

map.addSource('geojson', {
            'type': 'geojson',
            'maxzoom': 15, // this is the interesting part!
            'data': { // I just inlined the data for readability
                "type": "FeatureCollection",
                "name": "example",
                "features": [
                    { 
                        "type": "Feature", 
                        "properties": { }, 
                        "geometry": { 
                            "type": "MultiPolygon", 
                            "coordinates": [[[

                                [ 9.740717634558678, 52.376506310061373 ], 
                                [ 9.740708246827126, 52.376498941724329 ], 
                                [ 9.740707576274872, 52.376504672653247 ], 
                                [ 9.740713611245154, 52.376503444597105 ], 
                                [ 9.740708917379379, 52.376505491357321 ], 
                                [ 9.740717634558678, 52.376506310061373 ] 
                            ] ] ] 
                        } 
                    }
                ]
            }
        });

This is how this looks in the map:

I'm not saying there isn't a bug here in terms of moving data to the GPU, but looking at a feature in zoom 24 while having a tile that has accuracy of zoom 15 is asking for accuracy issues, doesn't it?

[leofuhrmann]

looking at a feature in zoom 24 while having a tile that has accuracy of zoom 15 is asking for accuracy issues, doesn't it?

You're right, this kind of "overzoom" is surely questionable. However, the intersection being created can lead to artifacts visible in smaller zoom levels, if the problematic vertices are part of a bigger polygon:

The problematic part is located at the bottom right of the following polygon. It leads to a visual artifact (seemingly "cutting" the polygon) being visible from zoom 15.5:

So, at some point coordinates might be translated without checking again if the resulting polygon is still "valid". Such a check and resulting measures are necessary in my opinion. If anyone has an idea, I'll happily try to contribute.

[HarelM]

I started looking into it, but it requires time. Your best bet would be to start digging. Since this can be reproduced with a geojson source of 6 points I would start there. It might be a 32 bit limitation, IDK... The geojson worker source is where I started debugging, but didn't find anything there, so it's probably the uniform array that is passed to the GPU. There's a PR which increased the "extent" and an issue that talks about overzoom, feel free to poke around those.

[CurtisFenner]

I just ran into this issue with a polygon as small as 6 vertices (7 including the closing vertex).

It seems that maplibre-gl is incorrectly splitting up a polygon when it spans more than 3 tiles.

Add map.showTileBoundaries = true; makes this abundantly clear:

Large polygon where it is immediately obvious:

Here is a very small polygon (a hexagon) where the problem occurs:

I don't think there's anything special about the polygon itself, but here it is for reproduction:

[
    [
        [
            139.5046234808873,
            35.605187046891146
        ],
        [
            139.50577340782908,
            35.60762779416374
        ],
        [
            139.50939725344256,
            35.60762779416374
        ],
        [
            139.510485622726,
            35.60507129239125
        ],
        [
            139.51066891696067,
            35.602724732337514
        ],
        [
            139.5044093046226,
            35.60262350327767
        ],
        [
            139.5046234808873,
            35.605187046891146
        ]
    ]
]

[HarelM]

I'm not sure it's the same issue... I would recommend opening a different issue about this issue.