Finding neighbour vertices of a mesh inside a given radius

Question

How to get neighbour vertices of a mesh inside a given radius using, e.g., CGAL? A simple K-nearest search on vertices neglecting face and edge properties is not sufficient, because if meshes are close to each other, vertices of both will be found using a k-nearest approach.

An example:

blue -> query point, blue circle -> search radius, green -> vertices to be found, red -> wrongly found vertices by knn search, black -> mesh

Answer 1

I solved the problem using the CGAL BGL package and the function CGAL::vertices_around_target.

A brief example:

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.
            }
        }
    }
}

Then

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

launches the greedy search algorithm.