A script for testing whether a GeoJSON will have triangulation issues in GL JS

check-polygon.js

import testGeoJSON from './index.js';

const data = {"type":"Polygon","coordinates":[[[-75.37809622,39.75768577],[-75.37791147,39.75742662],[-75.37774395,39.75749719],[-75.37625697,39.75541122],[-75.37812782,39.75461995],[-75.37929017,39.75625055],[-75.37904088,39.75635558],[-75.3793678,39.7568142],[-75.37944602,39.75678124],[-75.37953576,39.75690713],[-75.37945754,39.75694008],[-75.37981952,39.75744787],[-75.38006881,39.75734284],[-75.38119068,39.75891661],[-75.37931582,39.75970219],[-75.37792869,39.75775635],[-75.37809622,39.75768577]],[[-75.37809701405872,39.75768594822176],[-75.37792948404102,39.75775652822922],[-75.37931605248104,39.759701580474385],[-75.38118988531158,39.758916430865874],[-75.38006857816282,39.757343450438995],[-75.3798192881624,39.75744848043917],[-75.37945674594357,39.75693990175167],[-75.37953496594635,39.7569069517505],[-75.37944578817623,39.75678185046365],[-75.37936756817307,39.75681481046498],[-75.37904008596885,39.7563554017763],[-75.37928937596836,39.7562503717765],[-75.37812758861534,39.75462056108452],[-75.3762577635778,39.75541139757995],[-75.37774418185427,39.75749657958119],[-75.3779117018363,39.75742600958877],[-75.37809701405872,39.75768594822176]]]};

const problemTiles = testGeoJSON(data, {maxzoom: 18});

if (problemTiles.length) {
    console.log('Found triangulation issues in the following tiles:');
    for (const [z, x, y] of problemTiles) {
        console.log(z, x, y);
    }
} else {
    console.log('No issues found.');
}

index.js

import earcut, {deviation, flatten} from 'earcut';
import geojsonvt from 'geojson-vt';
import quickselect from 'quickselect';

const extent = 8192;
const tileSize = 512;
const scale = extent / tileSize;

export default function testGeoJSON(data, options = {}) {
    const {
        buffer = 128,
        tolerance = 0.375,
        maxzoom = 18
    } = options;

    const index = geojsonvt(data, {
        buffer: buffer * scale,
        tolerance: tolerance * scale,
        maxZoom: maxzoom,
        indexMaxZoom: maxzoom,
        indexMaxPoints: 0,
        extent
    });

    const problemTiles = [];

    for (const {z, x, y} of index.tileCoords) {
        const tile = index.getTile(z, x, y);
        if (tile && tile.numSimplified) {
            testTile(tile, problemTiles);
        }
    }

    return problemTiles;
}

function testTile(tile, problemTiles) {
    const {z, x, y, features} = tile;

    for (const {type, geometry} of features) {
        if (type !== 3) continue;
        const polygons = classifyRings(geometry);
        for (const polygon of polygons) {
            const {vertices, holes} = flatten(polygon);
            const triangles = earcut(vertices, holes);
            const err = deviation(vertices, holes, 2, triangles);
            if (err) problemTiles.push([z, x, y, err]);
        }
    }
}

function classifyRings(rings, maxRings = 500) {
    if (rings.length <= 1) return [rings];

    const polygons = [];
    let polygon, ccw;

    for (const ring of rings) {
        const area = calculateSignedArea(ring);
        if (area === 0) continue;

        ring.area = Math.abs(area);

        if (ccw === undefined) ccw = area < 0;

        if (ccw === area < 0) {
            if (polygon) polygons.push(polygon);
            polygon = [ring];

        } else {
            (polygon).push(ring);
        }
    }
    if (polygon) polygons.push(polygon);

    if (maxRings > 1) {
        for (const polygon of polygons) {
            if (polygon.length <= maxRings) continue;
            quickselect(polygon, maxRings, 1, polygon.length - 1, compareAreas);
            polygon.splice(maxRings);
        }
    }

    return polygons;
}

export function calculateSignedArea(ring) {
    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[0] - p1[0]) * (p1[1] + p2[1]);
    }
    return sum;
}

function compareAreas(a, b) {
    return b.area - a.area;
}

package.json

{
  "name": "polygon-checker",
  "version": "1.0.0",
  "author": "Volodymyr Agafonkin",
  "license": "ISC",
  "type": "module",
  "dependencies": {
    "earcut": "^3.0.0",
    "geojson-vt": "^4.0.2",
    "quickselect": "^2.0.0"
  }
}