MATLAB无序噪声数据集下非凸多边形线拟合优化咨询

问题定义 #

从含噪声的无序数据集重建一条非凸且不自交的多边形线（目标线），目标是学习目标线的顶点位置，得到的估计结果称为多边形线。目标线已归一化，位于水平方向[-1,1]、垂直方向[0,1]区间内，起点为[1 0]'，终点落在横轴上。

核心挑战：

• 数据集为无序，仅含噪声观测点位置，无沿目标线的时序信息；
• 需支持大数据集（如1e4个观测点）秒级运算，适配实时系统，无法采用复杂优化算法；
• 数据集规模小（如≤10个观测点）或高斯噪声标准差大（归一化单位下>1）时，算法需鲁棒，输出简单合理形状（如半椭圆）；
• 估计的多边形线顶点数需等于预设值N。

现有算法概述 #

已实现一个快速初步估计算法，输入为数据集D（2×m矩阵，含m个观测点坐标）和顶点数N，输出为估计的多边形线顶点矩阵hatV（2×N矩阵），核心流程如下：

function hatV = staticShaper(D, N)
    % step 0: unfrozen initialization 
    hatV   = 1.5 * [cos(linspace(0, pi, N)); sin(linspace(0, pi, N))];
    freeze = zeros(1, N);

    for iter = 1 : 3
        % step 1: project the polygonal line over the dataset
        idx = projectLine(hatV, D);
       
        % step 2: update the polygonal line
        hatV = updateLine(hatV, D, idx, freeze);

        % step 3: simplify the polygonal line
        [hatV, Ndeficit] = simplifyLine(hatV);

        % step 4: interpolate and freeze the polygonal line
        [hatV, freeze] = interpolateLine(hatV, Ndeficit);
    end
end

算法包含初始化、投影、更新、简化、插值冻结等步骤，详细实现见附带的projectLine、updateLine等函数。

现存问题与疑问 #

当前算法存在两个核心精度问题：

1. 无法适配“较深”的凹区域；
2. 无法贴合数据集，仅能拟合数据集的外边界。

此外，需验证：该算法生成的多边形线是否一定不自交？

优化建议与证明思路 #

针对凹区域适配问题的优化 #

1. 投影步骤改进：修改projectLine逻辑，先按x坐标将数据集分段（匹配多边形线的x轴走向），再在分段内计算点到对应线段的投影，避免凹区域内的点被错误关联到凸边。
2. 更新规则调整：在updateLine阶段，增加凹性引导逻辑：统计每个顶点两侧关联点的分布斜率，若两侧点的y坐标显著低于顶点当前位置且x范围呈现内凹特征，基于关联点的平均偏移量，强制将顶点向凹侧微调。
3. 初始化多样化：除半椭圆外，额外生成2-3种含不同凹形态的初始多边形线（如在半椭圆基础上随机修改1-2个顶点的y坐标为较低值），首次迭代前选择与数据集匹配度最高的初始形态进入流程，提升对凹结构的探索能力。

针对数据集贴合问题的优化 #

1. 投影权重机制：updateLine时采用距离加权更新顶点——距离线段越近的观测点权重越高，噪声点权重越低，降低噪声干扰，让顶点更贴合真实数据分布。
2. 动态冻结策略：将固定冻结改为动态判断：仅当顶点连续2次迭代的位置变化小于阈值（如1e-3）时才冻结，否则保持可更新状态，避免过早固定顶点导致拟合偏差。
3. 简化步骤约束：simplifyLine阶段仅简化相邻三点夹角接近180度（如175-185度）且y坐标方差极小的线段，保留对数据分布有贡献的顶点，避免过度简化丢失形态细节。

多边形线不自交的证明思路 #

要证明算法生成的多边形线不自交，需从迭代全流程验证形态约束：

1. 初始化阶段：初始半椭圆多边形线的顶点x坐标严格从1递减到-1，y坐标先升后降，无交叉。
2. 迭代阶段：若updateLine、simplifyLine、interpolateLine始终保持顶点的x坐标单调递减顺序（即顶点序列的x值从起点到终点持续减小，无反转），则多边形线的所有线段都是沿x轴从右向左延伸，不可能出现交叉。
3. 约束验证：需确认现有各函数是否遵循x坐标单调递减的约束，若未遵循，需补充该约束——更新或调整顶点时，仅修改y坐标，固定x坐标的顺序关系。

综上，只要算法在所有步骤中保持顶点x坐标的严格单调递减性，生成的多边形线必然不自交。

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