Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Handling winded polygons with modified poin-in-polygon test

Open
  • Is something wrong?
#66 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
1-2 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
javascript
Domain
computer-graphics

Research direction

Review the JavaScript implementation of pointToPolygonDist and compare its point-in-polygon test with the winding-number version shown in the issue. Reproduce the reported winded-polygon case from the linked image; done when polylabel selects an interior point rather than the duplicated boundary, with regression coverage in the repository's relevant tests.

Written by the indexing model from the issue text.

Description

enhancement question

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.
winded-polygon
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;
}
Dominant language
JavaScript
Stars
1.6k
Forks
163
No merged PRs in 30d

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from mapbox/polylabel

All issues in mapbox/polylabel

Similar issues

More JavaScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.