2D有序点集直线拟合算法优化需求：修复共线检测缺陷

需求说明 #

• 在2D环境中实现基于有序点集的直线定位算法，识别指定容差内的共线点并生成对应直线
• 输出每条直线的位置、朝向（orientation）及长度
• 输入点按顺序依次排列

示例输入 #

// 测试用示例输入
const table = [
    { Position: [0.849999487, -1.47224224] },
    { Position: [0.848479152, -1.01117814] },
    { Position: [0.842648506, -0.707066119] },
    { Position: [0.848704576, -0.489999771] },
    { Position: [0.845723033, -0.307818025] },
    { Position: [0.846934378, -0.149337426] },
    { Position: [0.859999716, 0] },
    { Position: [0.846934378, 0.149337381] },
    { Position: [0.845723033, 0.307817996] },
    { Position: [0.848704517, 0.489999801] },
    { Position: [0.842648506, 0.707066059] },
    { Position: [0.848479271, 1.01117814] },
    { Position: [0.599999666, 1.03923011] },
    { Position: [0.376222014, 1.03366148] },
    { Position: [0.184067041, 1.04389584] },
    { Position: [0, 1.0399996] },
    { Position: [-0.184066996, 1.04389584] },
    { Position: [-0.376221985, 1.03366148] },
    { Position: [-0.599999726, 1.03922999] },
    { Position: [-0.874190629, 1.04181993] },
    { Position: [-1.24099123, 1.04131532] }
];

现有实现缺陷 #

当前采用三点三角形面积判断共线性的方法，存在以下问题：

1. 方向改变时，因点间距过近，算法误判后续点仍属于同一直线序列；
2. 误将首尾远距离点判定为共线并生成直线。

现有实现代码 #

function getBoundaryWalls2(points) {
    const COLLINEAR_TOLERANCE = 0.05; // 直线检测的严格程度
    const MIN_LINE_LENGTH = 1; // 有效直线的最小长度
    const walls = [];
    
    // 通过计算三角形面积判断三点是否近似共线
    function areCollinear(p1, p2, p3) {
        const x1 = p1.position.x, y1 = p1.position.y;
        const x2 = p2.position.x, y2 = p2.position.y;
        const x3 = p3.position.x, y3 = p3.position.y;
        
        // 若三角形面积接近0，则点近似共线
        const area = Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2);
        return area < COLLINEAR_TOLERANCE;
    }
    
    // 获取两点间的角度（以度为单位）
    function getAngle(p1, p2) {
        const dx = p2.position.x - p1.position.x;
        const dy = p2.position.y - p1.position.y;
        return (Math.atan2(dy, dx) * 180 / Math.PI);
    }
    
    // 获取两点间的距离
    function getDistance(p1, p2) {
        const dx = p2.position.x - p1.position.x;
        const dy = p2.position.y - p1.position.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
    
    let i = 1;
    while (i < points.length - 1) {
        // 以两个点初始化潜在直线
        const currentLine = {
            startPoint: points[i],
            endPoint: points[i + 1],
            points: [points[i], points[i + 1]]
        };
        
        // 尝试添加更多共线点以延长直线
        let j = i + 2;
        while (j < points.length) {
            if (areCollinear(currentLine.startPoint, currentLine.endPoint, points[j])) {
                currentLine.endPoint = points[j];
                currentLine.points.push(points[j]);
                j++;
            } else {
                break;
            }
        }
        
        // 若直线长度达标，则生成墙体
        const length = getDistance(currentLine.startPoint, currentLine.endPoint);
        if (length >= MIN_LINE_LENGTH) {
            // 计算墙体中心
            const centerX = (currentLine.startPoint.position.x + currentLine.endPoint.position.x) / 2;
            const centerY = (currentLine.startPoint.position.y + currentLine.endPoint.position.y) / 2;
            
            // 获取墙体朝向
            const orientation = getAngle(currentLine.startPoint, currentLine.endPoint);
            
            // 创建墙体对象
            const wall = {
                position: { x: centerX, y: centerY },
                orientation: orientation,
                length: length,
                points: currentLine.points
            };
            
            walls.push(wall);
        }
        
        // 跳至下一个未处理的点
        i += currentLine.points.length - 1;
    }
    
    return walls;
}

优化后的算法实现 #

针对现有缺陷，优化思路如下：

• 改用局部方向向量校验：不用直线首尾点判断新点，而是用直线最后两个点的方向向量，与新点和直线最后一个点的方向向量做夹角校验，避免远距离首尾点的误判
• 同时保留面积共线性校验：双重校验确保点在直线容差范围内
• 增加方向偏差容差：限制新方向与原直线方向的夹角，避免方向突变时的误判

优化后的代码：

function getBoundaryWallsOptimized(points) {
    // 参数配置
    const COLLINEAR_TOLERANCE = 0.01; // 点到直线的距离容差（面积等价）
    const ANGLE_TOLERANCE = 5; // 方向偏差容差（度）
    const MIN_LINE_LENGTH = 1; // 有效直线最小长度
    const walls = [];

    // 工具函数：将点对象转换为坐标数组
    const getCoords = (p) => p.Position || (p.position ? [p.position.x, p.position.y] : []);

    // 计算两点间的方向向量（归一化）
    function getDirectionVector(p1, p2) {
        const [x1, y1] = getCoords(p1);
        const [x2, y2] = getCoords(p2);
        const dx = x2 - x1;
        const dy = y2 - y1;
        const len = Math.sqrt(dx * dx + dy * dy);
        return len === 0 ? [0, 0] : [dx / len, dy / len];
    }

    // 计算两个向量的夹角（度）
    function getVectorAngle(v1, v2) {
        const dot = v1[0] * v2[0] + v1[1] * v2[1];
        const angle = Math.acos(Math.max(-1, Math.min(1, dot))) * 180 / Math.PI;
        // 返回最小夹角（0-180度）
        return Math.min(angle, 180 - angle);
    }

    // 三点共线性校验（面积法）
    function areCollinear(p1, p2, p3) {
        const [x1, y1] = getCoords(p1);
        const [x2, y2] = getCoords(p2);
        const [x3, y3] = getCoords(p3);
        const area = Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2);
        return area < COLLINEAR_TOLERANCE;
    }

    // 计算两点间距离
    function getDistance(p1, p2) {
        const [x1, y1] = getCoords(p1);
        const [x2, y2] = getCoords(p2);
        const dx = x2 - x1;
        const dy = y2 - y1;
        return Math.sqrt(dx * dx + dy * dy);
    }

    // 计算直线朝向角度（度）
    function getOrientation(p1, p2) {
        const [x1, y1] = getCoords(p1);
        const [x2, y2] = getCoords(p2);
        const dx = x2 - x1;
        const dy = y2 - y1;
        return (Math.atan2(dy, dx) * 180 / Math.PI);
    }

    let i = 0;
    while (i < points.length - 1) {
        // 初始化直线：从当前点和下一个点开始
        const currentLine = {
            startPoint: points[i],
            endPoint: points[i + 1],
            points: [points[i], points[i + 1]]
        };
        // 获取初始方向向量
        let lineDir = getDirectionVector(currentLine.startPoint, currentLine.endPoint);

        let j = i + 2;
        while (j < points.length) {
            const lastPoint = currentLine.endPoint;
            const newPoint = points[j];
            // 1. 计算新方向向量
            const newDir = getDirectionVector(lastPoint, newPoint);
            // 2. 校验方向偏差
            const angleDiff = getVectorAngle(lineDir, newDir);
            // 3. 校验共线性（用直线最后两个点和新点）
            const collinear = areCollinear(currentLine.points[currentLine.points.length - 2], lastPoint, newPoint);

            if (angleDiff <= ANGLE_TOLERANCE && collinear) {
                // 符合条件，扩展直线
                currentLine.endPoint = newPoint;
                currentLine.points.push(newPoint);
                // 更新直线方向（用最新的两个点，适应微小方向漂移）
                lineDir = newDir;
                j++;
            } else {
                // 方向突变或不共线，停止扩展
                break;
            }
        }

        // 检查直线长度是否达标
        const lineLength = getDistance(currentLine.startPoint, currentLine.endPoint);
        if (lineLength >= MIN_LINE_LENGTH) {
            const [x1, y1] = getCoords(currentLine.startPoint);
            const [x2, y2] = getCoords(currentLine.endPoint);
            const wall = {
                position: { x: (x1 + x2) / 2, y: (y1 + y2) / 2 },
                orientation: getOrientation(currentLine.startPoint, currentLine.endPoint),
                length: lineLength,
                points: [...currentLine.points]
            };
            walls.push(wall);
        }

        // 跳至下一个未处理的点
        i = j - 1;
    }

    return walls;
}

// 测试调用
const testPoints = table.map(p => ({ position: { x: p.Position[0], y: p.Position[1] } }));
const optimizedWalls = getBoundaryWallsOptimized(testPoints);
console.log(optimizedWalls);

优化点说明 #

1. 局部方向校验：每次用直线最后两个点的方向向量和新点的方向向量做夹角比对，避免了首尾远距离点的误判
2. 双重校验机制：同时校验方向偏差和共线性，既保证点在直线上，又保证方向没有突变
3. 动态更新方向：每次扩展直线后更新方向向量，适应点集的微小方向漂移，提升鲁棒性
4. 兼容输入格式：支持两种输入点格式（Position数组或position对象），适配示例输入

内容的提问来源于stack exchange，提问作者aziz