unkinkPolygon cant deal with duplicate coordinates

[laundmo]

This is basically a re-opening of:

• #1679

As that was closed by the author without any fix 6 years ago.

unkinkPolygon throws an error The input polygon may not have duplicate vertices (except for the first and last vertex of each ring) when run on a polygon with duplicate vertices.

Reproduction using an hourglass shape, where the center has 2 stacked vertices:

const hourglass = turf.polygon( [[
    [0,0],
    [1,1], // center
    [2,2],
    [0,2],
    [1,1], // center
    [2,0],
    [0,0]
]]);

// all of these error
turf.unkinkPolygon(hourglass)
turf.unkinkPolygon(turf.cleanCoords(hourglass))
turf.unkinkPolygon(turf.simplify(hourglass, {tolerance: 0.5}))
turf.unkinkPolygon(turf.simplify(hourglass, {tolerance: 0.5, highQuality: true}))

Image of the shape

[laundmo]

After quite some messing around, i found a good workaround: I was able to use turf.kinks to find the kinks, buffer them to a polygon, and union this with the original. That resolves the kinks by making them have some area.

/**
 * Better unkinking algorithm, since turf.unkinkPolygon is quite broken
 * @param {GeoJSON.Feature<GeoJSON.Polygon>} poly
 * @returns {GeoJSON.Feature<GeoJSON.Polygon>}
 */
function unkinkPolyFeature(poly) {
    const kinks = turf.kinks(poly);
    if (kinks.features.length === 0) {
        return poly;
    }
    // @ts-ignore // kinks will always overlap the polygon, so it shouldn't become a multipolygon
    return turf.union(
        turf.featureCollection([
            poly,
            ...turf.buffer(kinks, 1, {
                steps: 1,
                units: "centimeters",
            }).features,
        ])
    );
}

the 1 centimeter and buffer steps of 1 means it won't add much overall area, and it won't add many extra vertices.

Initial workaround attempt

This was my initial attempt at a workaround, randomly moving the duplicate points. It didn't work well, as unkinkPolygon with very small distances between vertices had a tendency to output duplicates again

/**
 * Unkinks a turf polygon feature, accounting for duplicate coordinates
 * @param {GeoJSON.Feature<GeoJSON.Polygon>} poly
 * @returns {GeoJSON.FeatureCollection<GeoJSON.Polygon>}
 */
function unkinkPolyFeature(poly) {
    const poly_clone = turf.clone(poly);
    const seen = new Set();
    poly_clone.geometry.coordinates.forEach((ring) => {
        ring.forEach((coord, i, arr) => {
            // don't modify the last, as it should be the same as the first to close the polygon
            if (i === arr.length - 1) {
                return;
            }
            // loop if its a dupliate.
            // should run once in almost all cases, but randomness could lead to generating a duplicate
            while (seen.has(JSON.stringify(coord))) {
                // a few mm error in most places, acceptable for this workaround
                coord[0] = coord[0] - 0.00000002 + Math.random() * 0.00000004;
                coord[1] = coord[1] - 0.00000002 + Math.random() * 0.00000004;
            }
            seen.add(JSON.stringify(coord));
        });
    });
    return turf.unkinkPolygon(poly_clone);
}