在给定半径内查找网格的相邻顶点

Question

如何使用例如 CGAL 获取给定半径内网格的相邻顶点？ 对忽略面和边属性的顶点进行简单的 K 最近搜索是不够的，因为如果网格彼此靠近，将使用 k 最近方法找到两者的顶点。

一个例子：

蓝色 -> 查询点，蓝色圆圈 -> 搜索半径，绿色 -> 待查找的顶点，红色 -> knn 搜索错误找到的顶点，黑色 -> 网格

Answer 1

我使用 CGAL BGL 包和函数 CGAL::vertices_around_target 解决了这个问题。

一个简单的例子：

typedef CGAL::Simple_cartesian<double> SCKernel;
typedef CGAL::Surface_mesh<SCKernel::Point_3> SurfaceMeshT;
typedef SurfaceMeshT::Vertex_index VertexIndex;

[...]

std::shared_ptr<SurfaceMeshT> mesh;

[...]

void getVerticesAroundTarget(std::vector<std::size_t>& indices, 
                             std::size_t ptx) {
    VertexIndex vti(ptx);
    for (auto& idx : CGAL::vertices_around_target(mesh->halfedge(vti), *mesh)){
        indices.push_back(idx.idx());
    }
}

void getNeighbourVertices(std::vector<std::size_t>& neighbourVertices, 
                          std::size_t ptx, 
                          std::size_t idx, 
                          double searchRadius) {
    std::vector<std::size_t> indices;
    getVerticesAroundTarget(indices, idx);

    for (auto& vIdx : indices) {
        if (std::find(neighbourVertices.begin(), neighbourVertices.end(), vIdx) == neighbourVertices.end()) { // Vertex has not yet been treated.
            if (squaredEuclideanDistance(ptx, vIdx) <= searchRadius * searchRadius) { // Vertex in search radius.
                neighbourVertices.push_back(vIdx);
                getNeighbourVertices(neighbourVertices, ptx, vIdx, searchRadius); // Get next neighbours around vIdx.
            }
        }
    }
}

然后

std::vector<size_t> neighbours;
double searchRadius = XXXX;
std::size_t ptx = XXXX;
getNeighbourVertices(neighbours, ptx, ptx, searchRadius);

启动贪心搜索算法。