Handling winded polygons with modified poin-in-polygon test
Nobody has claimed this yet.
- 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.

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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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