mapbox / mapbox/polylabel

Handling winded polygons with modified poin-in-polygon test

Open
#66 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement question
Dominant language
JavaScript
Stars
1.6k
Forks
163
PR merge metrics
No merged PRs in 30d

Description

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;
}

Contributor guide

Open the contributing guide

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.

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.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.