Handling winded polygons with modified poin-in-polygon test

[Krzysztof-FF]

In my case of applying polylabel code, I've found some strange spaces on floor plan imported from some external CAD software, which occurred to wind themselves around its boundary. I detected this by splitting duplicated vertices apart, as below. Original algorithm regarded all points inside visible contour as laying "outside", and "interior" point has been calculated as somewhere on duplicated boundary edge. To cover such case, I had to modify test if point lies inside polygon by checking its winding number algorithm. I don't want to cover it in formal pull request, so below is the part of modified code with core taken from well-known geometry algorithms:

// signed distance from point to polygon outline (negative if point is outside)
// redesigned using winding number algorithm for point inside polygon test
// http://geomalgorithms.com/a03-_inclusion.html#wn_PnPoly()

function pointToPolygonDist(x, y, polygon) {
    var wn = 0;
    var minDistSq = Infinity;

    for (var k = 0; k < 1; k++) {
        var ring = polygon[k];

        for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) {
            var a = ring[i];
            var b = ring[j];

            var xi = a[0], yi = a[1];
            var xj = b[0], yj = b[1];
            if (yj <= y) {
                if (yi > y) {
                    if (isLeft([xj, yj], [xi, yi], [x,y]) > 0) {
                        wn++;
                    }
                }
            } else {
                if (yi <= y) {
                    if (isLeft([xj, yj], [xi, yi], [x, y]) < 0) {
                        wn--;
                    }
                }
            }
            minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));
        }
    }

    return minDistSq === 0 ? 0 : (wn != 0 ? 1 : -1) * Math.sqrt(minDistSq);
}

function isLeft(P0, P1, P2)
{
    var res = ( (P1[0] - P0[0]) * (P2[1] - P0[1])
            - (P2[0] -  P0[0]) * (P1[1] - P0[1]) );
    return res;
}

[hollasch]

@mourner — GitHub just released GitHub discussions to beta, which allows a way to host conversations & questions without resorting to creating issues. Here's an example: https://github.com/Raytracing/raytracing.github.io/discussions/. I got a notification to enable this in my project, so I don't know if it's available everywhere.

@Krzysztof-FF: Mapbox polygons are—as far as I can tell—a set of rings in arbitrary order and of arbitrary winding order. Polygons I will be working with have a strict "interior left" winding order, which can simplify this algorithm. In particular, when you have a defined winding order, you don't need to track the inside flag as it currently does.

Instead, find the minmal point-segment distance in the set of edges, tracking the segment data as you do so. Once you've found the nearest segment, determine whether the point lies in the interior halfspace or the exterior halfspace of the nearest segment, and set the distance sign accordingly. This approach will be faster, simpler, and more robust.