Hacktoberfest 2026：维护者为十月标记出来的 issue，仍然开放、适合新手。 浏览 Hacktoberfest issue

Handling winded polygons with modified poin-in-polygon test

未关闭
  • 哪里不对？
#66 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看

还没有人认领这个 Issue。

评估

难度
3/5
预计耗时
1-2 天
新手友好度
35/100
Issue 类型
缺陷
描述清晰度
基本清楚
活跃度
停滞
技术栈
javascript
领域
computer-graphics

调研方向

检查 pointToPolygonDist 的 JavaScript 实现，并将其 point-in-polygon 测试与 issue 中展示的 winding-number 版本进行比较。复现链接图片中报告的 winded-polygon 情况；当 polylabel 选择内部点而不是重复的 boundary，并且 repository 的相关测试中包含回归覆盖时，即视为完成。

由索引模型根据 Issue 内容生成。

描述

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;
}
主要语言
JavaScript
星标
1.6k
派生
163
30 天内没有已合并 PR

环境准备

  • 没有 Dockerfile 或 Docker Compose 文件
  • 没有 Pull Request 模板
  • 阅读贡献指南

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

mapbox/polylabel 的其他 Issue

查看 mapbox/polylabel 的全部 Issue

相似的 Issue

更多 JavaScript Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。