基于固定GetSelectedVertices的3D选点最优标记点与半径求解

我正在维护一款遗留软件，其中包含如下GetSelectedVertices函数，该函数接收点云模型、3D标记点、方向向量及选择半径，返回选中的顶点ID列表：

public static List<int> GetSelectedVertices(PointCloud model, Vec3 markPoint, Vec3 direction, float selectionRadius)
{
    List<int> outputVertices = new List<int>();
    Vec3 normal = GetNormal(direction);
    foreach(int vertexId in model.VertexIds)
    {
        Vec3 facetPosition = model.GetFacetPosition(vertexId);
        Vec3 vec3d = facetPosition - markPoint;
        
        var computation = vec3d.X * vec3d.X + vec3d.Y * vec3d.Y + vec3d.Z * vec3d.Z - 
           FloatSquare(vec3d.X * normal.X + vec3d.Y * normal.Y + vec3d.Z * normal.Z);
        
        if(computation < selectionRadius)
        {
            outputVertices.Add(vertexId);
        }
    }
    
    return outputVertices;
}

public static float FloatSquare(float input)
{
    return input * input;
}

public static Vec3 GetNormal(Vec3 input)
{
    double num = 1.0 / Math.Sqrt(input.X * input.X + input.Y * input.Y + input.Z * input.Z);
    return new Vec3(num * input.X, num * input.Y, num * input.Z);
}

注：原代码中computation行的vector3应为vec3d的笔误，已修正。

现给定一批位置已知的选中顶点（红色高亮部分），需计算合适的3D标记点与半径，使得调用该函数时，尽可能多地包含这些选中顶点，同时最小化未选中顶点的误选，且需支持设置最大半径限制。无法修改该函数的实现，减少误选是核心需求。已尝试分治法（速度慢且非最优）、选择特征顶点（精度不足）两种方法，效果不佳，求成熟解决方案或可行方法。

补充说明：可接受选中范围增长20%以内的误选顶点。

可行解决方案 #

首先明确函数的几何意义：该函数选中的是**到以direction为轴线、经过markPoint的无限圆柱的距离平方小于selectionRadius**的顶点，即圆柱半径为√selectionRadius。问题转化为寻找最优圆柱参数，平衡目标顶点覆盖率与误选率。

1. 目标点集最小包围圆柱求解（核心方案） #

这是最直接的最优解方向，最小包围圆柱（MBC）是能包含所有目标点的最小半径圆柱，有成熟的随机增量算法（如Emo Welzl算法，期望时间复杂度O(n)）可快速求解：

• 算法输出包含目标点集的最小圆柱的轴线方向（对应direction）、半径r_min，以及轴线位置；
• 适配遗留函数：将selectionRadius设为r_min²，markPoint选轴线上任意点（如圆柱中心轴中点）；
• 误选控制：若误选超过20%，可适当增大半径（不超过最大限制）或微调轴线方向，若仍超标，可牺牲少量边缘目标点，缩小圆柱范围直到误选符合要求。

2. 聚类辅助的轴线优化 #

若最小包围圆柱误选超标，结合密度聚类筛选核心目标点：

• 用DBSCAN对目标点集进行聚类，提取占比最高的核心子集（如90%以上的目标点）；
• 求解该核心子集的最小包围圆柱，此时圆柱范围更小，误选概率显著降低；
• 验证目标点覆盖率（至少保留80%原目标点）与误选率，若不满足则逐步扩大核心子集范围，达到平衡。

3. 主成分分析（PCA）定向轴线 #

若目标点集有明显延伸方向（如平面、长条状结构）：

• 对目标点集做PCA，取第一主成分方向作为direction（即点集的主要延伸方向）；
• 在垂直于该方向的平面上，求解目标点集的最小包围圆，圆心对应markPoint在该平面的投影，圆半径为r；
• 设置selectionRadius = r²，markPoint为投影圆心沿轴线方向的任意点，该方法计算快速，贴合点集自然结构，误选率低。

4. 最大半径约束下的迭代优化 #

当存在最大半径限制时：

• 若最小包围圆柱半径r_min≤最大限制，直接使用并验证误选；
• 若r_min超过限制，需寻找能包含最多目标点的受限圆柱：
  • 随机采样目标点对生成候选轴线（两点连线方向）；
  • 对每个候选轴线，计算目标点到轴线的距离，排序后取前k个点（k最大使得第k个距离≤最大半径）；
  • 保留包含目标点最多的候选轴线，微调markPoint位置以覆盖更多目标点；
  • 若误选超标，减少包含的目标点数量，直到符合要求。

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