CODEWITHSUNDEEP
c++c++11openmesh
Botond
Botond

Reputation: 2802

OpenMesh: fast search of common neighbor vertices

I have a function which finds the common neighbors of two vertices v1 and v2, i.e. those vertices that are connected to both v1 and v2:

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh, MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2){
    std::vector<MyMesh::VertexHandle> common_neighbors;

    //iterate over neighbors of v1
    for(MyMesh::VertexVertexIter it1 = mesh.vv_iter(v1); it1.is_valid(); ++it1) {
      //neighbors of v2
      for(MyMesh::VertexVertexIter it2 = mesh.vv_iter(v2); it2.is_valid(); ++it2) {
        if ((*it1)==(*it2)){
            common_neighbors.push_back(*it1);     
        }
      }
    }
    return common_neighbors;

The function simply iterates over the neighborhood of v1 and v2 and checks if finds any vertex that appears in both neighborhoods. Unfortunately, this function seems to be the bottleneck of my code, thus my question is whether there is a more optimal way to accomplish this in OpenMesh?

Upvotes: 1

Views: 589

Answers (2)

Mark Loyman
Mark Loyman

Reputation: 2170

Another aspect to consider is that you have a nested loop. Assuming common_neighbors is the order of 10, then both v1 and v2 have at least 10 neighbors. By using an unordered_map, we can solve this with two separate loops - which means 20 iterations instead of 100 iterations. More precisely O(n1 + n2) instead of O(n1*n2).

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh, MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2)
{
    std::vector<MyMesh::VertexHandle> common_neighbors;
    std::unordered_map<MyMesh::VertexHandle, bool> candidates;

    for(MyMesh::VertexVertexIter it = mesh.vv_iter(v1); it.is_valid(); ++it) {
        candidates[*it] = true;
    }

    for(MyMesh::VertexVertexIter it = mesh.vv_iter(v2); it2.is_valid(); ++it) {
        if (candidates.find(*it) != candidates.end()) 
            common_neighbors.push_back(*it); 
    }

    return common_neighbors;
}

Details

To understand what we are doing here, let's first consider a conceptionally similar approach that uses std::vector<MyMesh::VertexHandle> candidates:

  • 1st loop: add all neighbors of v1 to candidates
  • 2nd loop: if a neighbor of v2 is found in candidates, add it to common_neighbors

However, find on a vector is inefficient (same as iterating the candidates vector each time). This is why we replace the candidate vector with an unordered_map, which is a hash map with an average complexity of O(1) (worst case is O(n) - but practically speaking, we can assume it to be O(1)).

Step up

If it makes sense (and is practicle) to group your calls to find_common_neighbors, such that: ...MyMesh::VertexHandle & v1, std:vector<MyMesh::VertexHandle> & v2) - then, note that the 1st loop (populating the candidates map) can be reused for all elements in v2. So we get O(n1 + m * n2) instead of O(m * (n1 + n2)), where n1 is size of v1, n2 is average size in v2 and m is number of vertices in v2.

Upvotes: 1

Viktor Latypov
Viktor Latypov

Reputation: 14467

I'm not an expert on OpenMesh proper, but it looks like you are using a rather efficient Circulator to find these pairs of vertices.

The only obvious problem with your function is the fact you are allocating and returning the std::vector object.

The declaration

std::vector<MyMesh::VertexHandle> common_neighbors;

defines an empty vector (and subsequent push_backs internally call malloc which is unpredictably expensive). The least you can do here is preallocate the approximate expected amount of vertices.

If you are calling this function for a large (10000+ ?) number of distinct v1, v2 pairs, you should change the signature of your function to

std::vector<MyMesh::VertexHandle> find_common_neighbors(MyMesh & mesh,
               MyMesh::VertexHandle & v1, MyMesh::VertexHandle & v2,
               std::vector<MyMesh::VertexHandle>& common_neighbors);

and pass preallocated common_neighbors there.

You should probably also give more context (how do you call this function, what do you actually do with these vertices - e.g., if you need a v3 adjacent to both v1 and v2 and then make a triangular face (v1,v2,v3), then probably you should just take a v1-v2 edge and iterate over adjacent triangles...) so that more optimization can be provided.

Upvotes: 2

Related Questions