判断点是否位于多边形内部的JS算法实现代码修正

判断坐标点(x,y)是否位于二维多边形边界围成的平面区域内部，是计算机图形学领域的常见问题，典型应用场景包括光栅设备的多边形填充、绘图软件的剖面线绘制、多多边形相交关系判定等。需求目标是批量检测多个点与多边形的位置关系，准确识别多边形外部区域。

现有测试代码 #

当前提供的可交互测试代码如下，核心判定逻辑存在错误：

JavaScript 逻辑 #

var canvas = window.document.getElementsByTagName("canvas")[0];
var ctx = canvas.getContext("2d");
var W = 500;
var H = 600;

    var a = 0;
    var b = 0;

var point_array = [[0,0]];

if(JSON.parse(localStorage.getItem("select_point")) != null){

    for(var i = point_array.length - 1; i >= 0; i--) {
        point_array.splice(i, 1);
    }

    point_array = JSON.parse(localStorage.getItem("select_point"));
}

var point = [W/2, H/2];

canvas.onclick = function(evt){
    point[0] = evt.pageX - canvas.getBoundingClientRect().top;
    point[1] = evt.pageY - canvas.getBoundingClientRect().left;
    if(localStorage.getItem("select_point") == null){
        if(point_array[0][0] == 0 && point_array[0][1] == 0){
            point_array.splice(0, 1);
        }
        point_array.push([point[0],point[1]]);
    }
    test();
};

test();

function sifirla(){
    localStorage.removeItem("select_point");
    window.location.reload();
}

function aktar(){
    localStorage.setItem("select_point", JSON.stringify(point_array));
    window.location.reload();
}

function sign(p, p2, p3){
    return (p[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p[1] - p3[1]);
}

function PointInTriangle(pt, polygon){
    
    var d = [];
    var has_neg, has_pos;

    a = 0;
    b = 0;

    for(var i = 0; i < polygon.length-1; i++){
        var ss = sign(pt, polygon[i], polygon[i+1]);
        d.push(ss);

        if(ss > 0){ a++; }
        if(ss < 0){ b++; }
        
    }
    /*d1 = this.sign(pt, v1, v2);
    d2 = this.sign(pt, v2, v3);
    d3 = this.sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);*/
    return true;
}

function zero_death(num){
    if(num < 0){ num = num*-1; }
    return num;
}

function test(){
    var result = PointInTriangle(point, point_array);

    var info = "point = [" + point[0] + "," + point[1] + "]\n";
    info += "+: "+a+"-: "+b+"\n";
    for(var i = 0; i < point_array.length; i++){
        info += "point_array\t["+i+"][" + point_array[i][0] + "," + point_array[i][1] + "] \t ["+zero_death(point_array[i][0]-point[0])+","+zero_death(point_array[i][1]-point[1])+"]("+(zero_death(point_array[i][0]-point[0])+zero_death(point_array[i][1]-point[1]))+")\n";
    }
    info += "result = " + (result ? "true" : "false");

    window.document.getElementById("result").innerHTML = info;
    render();
}

function render(){
    ctx.fillStyle = "#CCCCCC";
    ctx.fillRect(0, 0, 500, 600);
    drawTriangle(point_array);
    drawPoint(point);
    //appendTriangle(point_array);
    pastePoint(point_array);
}

function pastePoint(polygon){

    var result = [];
    for(var i = 0; i < point_array.length; i++){
        result.push([i,((zero_death(point_array[i][0]-point[0])+zero_death(point_array[i][1]-point[1])))]);
    }
    result.sort(function(a, b) {
      return a[1] - b[1];
    });

    ctx.beginPath();
            ctx.moveTo(point[0], point[1]);

            ctx.lineTo(point[0], point[1]);
            ctx.lineTo(polygon[result[0][0]][0], polygon[result[0][0]][1]);
    ctx.stroke();
    ctx.strokeStyle = "#FF0000";
    
        ctx.beginPath();
            ctx.moveTo(point[0], point[1]);

            ctx.lineTo(point[0], point[1]);
            ctx.lineTo(polygon[result[1][0]][0], polygon[result[1][0]][1]);
    ctx.stroke();
    ctx.strokeStyle = "#FF0000";
    
}

function appendTriangle(polygon){

    ctx.beginPath();
        for(var i = 0; i < (polygon.length/3)-1; i++){
            ctx.moveTo(polygon[(i*3)+0][0], polygon[(i*3)+0][1]);

            ctx.lineTo(polygon[(i*3)+0][0], polygon[(i*3)+0][1]);
            ctx.lineTo(polygon[(i*3)+1][0], polygon[(i*3)+1][1]);
            ctx.lineTo(polygon[(i*3)+2][0], polygon[(i*3)+2][1]);
        }
    ctx.stroke();
    
}

function drawTriangle(polygon){
    ctx.fillStyle = "white";
    ctx.beginPath();
    ctx.moveTo(polygon[0][0], polygon[0][1]);
    for(var i = 0; i < polygon.length; i++){
        ctx.lineTo(polygon[i][0], polygon[i][1]);
    }
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000000";
    ctx.font = "12px monospace";
    for(var i = 0; i < polygon.length; i++){
        ctx.fillText(i, polygon[i][0], polygon[i][1]);
    }
}

function drawPoint(p){
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p[0], p[1], 5, 0, 2 * Math.PI);
    ctx.fill();
}

CSS 样式 #

canvas{
    background: #f1f1f1;
    border:1px solid #eeeeee;
}

HTML 结构 #

<canvas width="500" height="600" style="float:left;margin-right:15px;"></canvas>
<pre id="result"></pre>

核心问题说明 #

当前代码的判定逻辑存在三处硬伤：

1. 遍历多边形边时，没有处理最后一个顶点连接回第一个顶点的闭合边，多边形不是封闭图形
2. PointInTriangle函数没有实际判定逻辑，固定返回true，所有点都会被判定为在内部
3. 注释中的叉积同号判定逻辑仅适用于三角形，无法直接支持任意边数的凹/凸多边形

正确实现方案 #

任意多边形点包含判定优先选择射线法（奇偶规则法），实现简单、性能稳定，兼容凸多边形、凹多边形，非常适合批量检测场景。

算法逻辑 #

• 从待检测点向右发射一条水平射线
• 统计射线与多边形所有边的相交次数
• 相交次数为奇数：点在多边形内部；偶数：点在多边形外部
• 额外处理点落在多边形边界上的边缘场景即可

可用判定函数 #

/**
 * 点与多边形位置关系判定
 * @param {[number, number]} point 待检测点坐标 [x, y]
 * @param {[number, number][]} polygon 多边形顶点数组，按顺时针/逆时针顺序排列
 * @returns {boolean} true=点在多边形内部/边界上，false=点在外部
 */
function pointInPolygon(point, polygon) {
  const [x, y] = point;
  let inside = false;
  const vertexCount = polygon.length;

  // 双指针遍历所有边，j始终是i的前一个顶点，自动处理首尾闭合
  for (let i = 0, j = vertexCount - 1; i < vertexCount; j = i++) {
    const [xi, yi] = polygon[i];
    const [xj, yj] = polygon[j];

    // 判定点是否落在当前边上
    const isOnEdge = (y - yi) * (xj - xi) === (x - xi) * (yj - yi)
      && x >= Math.min(xi, xj) && x <= Math.max(xi, xj)
      && y >= Math.min(yi, yj) && y <= Math.max(yi, yj);
    if (isOnEdge) return true;

    // 判定水平射线是否与当前边相交
    const isIntersect = ((yi > y) !== (yj > y))
      && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
    if (isIntersect) inside = !inside;
  }

  return inside;
}

批量检测优化技巧 #

• 预计算多边形的外接矩形（最小/最大x、y值），待检测点不在外接矩形范围内时直接判定为外部，跳过逐边遍历，性能可提升3~10倍
• 如果点量级达到十万级以上，可以配合网格索引、四叉树做空间划分，进一步减少无效计算

内容的提问来源于stack exchange，提问作者Ramazan ŞAHİN