概述

今天分享一个简单的空间关系的判断：点是否在面内。

分析

image.png

如上图：

• 红色为多边形，其坐标为[[0,0],[3,2],[3,3],[2,3],[0,0]];
• A为多边形四至外的点，其坐标为[-1, -1]，计算结果为false;
• B点位多边形内的点，坐标为[2,2],，计算结果为true；
• C点位多边形边界上的点，其坐标为[3, 2.5]，计算结果为true;
• D为多边形四至内的点，但在多边形外，其坐标为[1, 2]，计算结果为false。

实现

function isPointInPolygon (point, polygon) {
    if(!point || point.length < 0) throw new Error('not a point')
    if(!polygon || polygon.length < 4 || polygon[0].join('') !== polygon[polygon.length - 1].join('')) throw new Error('not a polygon')

    const [x, y] = point
    const xs = polygon.map(([x, y]) => x)
    const ys = polygon.map(([x, y]) => y)
    const xsSort = xs.sort((a, b) => a - b)
    const ysSort = ys.sort((a, b) => a - b)
    // 在四至内
    const inBBOX = () => {
        const [xmin, ymin, xmax, ymax] = [
            xsSort[0],
            ysSort[0],
            xsSort[xsSort.length - 1],
            ysSort[ysSort.length - 1]
        ]
        return x >= xmin && x <= xmax && y >= ymin && y <= ymax
    }
    // 点在线上
    const onBorder = () => {
        let res = false
        for (let i = 0; i < polygon.length - 2; i++) {
            const [xi, yi] = polygon[i]
            const [xj, yj] = polygon[i+1]
            const k1 = (yj - yi)/(xj - xi)
            const k2 = (yj - y)/(xj - x)
            if(k1 === k2) {
                res = true
                break
            }
        }
        return res
    }
    // 点在多边形内部
    const inPolygon = () => {
        let odd = false;
        for (let i = 0, j = polygon.length - 1; i < polygon.length; i++) {
            if (((polygon[i][1] > y) !== (polygon[j][1] > y))
                && (x < ((polygon[j][0] - polygon[i][0]) * (y - polygon[i][1]) / (polygon[j][1] - polygon[i][1]) + polygon[i][0]))) {
                odd = !odd;
            }
            j = i;
        }
        return odd;
    }

    if(!inBBOX()) return false
    if(onBorder()) return true
    return inPolygon()
}

ABCD四点的测试及结果如下：

image.png