OpenMesh：快速搜索公共相邻顶点

Question

我有一个函数可以找到两个顶点 v1 和 v2 的公共邻居，即那些连接到 v1 和 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;

该函数简单地遍历 v1 和 v2 的邻域，并检查是否找到出现在两个邻域中的任何顶点。不幸的是，这个功能似乎是我代码的瓶颈，因此我的问题是在 OpenMesh 中是否有更好的方法来完成这个？

Answer 1

我不是 OpenMesh 本身的专家，但看起来您正在使用相当高效的循环器来查找这些顶点对。

你的函数唯一明显的问题是你正在分配和返回 std::vector 对象。

宣言

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

定义了一个空向量（随后的 push_back 内部调用了 malloc，这是不可预测的昂贵）。您在这里至少可以做的是预先分配大约预期的顶点数量。

如果您为大量（10000+？）不同的 v1, v2 对调用此函数，您应该将函数的签名更改为

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

并在那里传递预分配的 common_neighbors。

你可能还应该提供更多上下文（你如何调用这个函数，你实际上用这些顶点做什么 - 例如，如果你需要一个 v3 与 v1 和 v2然后做一个三角形面(v1,v2,v3)，那么你可能应该只取一个v1-v2边并遍历相邻的三角形...）这样可以提供更多的优化。

Answer 2

要考虑的另一个方面是您有一个嵌套循环。假设common_neighbors是10的阶数，那么v1和v2都有至少10个邻居。通过使用 unordered_map，我们可以用两个独立的循环来解决这个问题——这意味着 20 次迭代而不是 100 次迭代。更准确地说是 O(n1 + n2) 而不是 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;
}

详情

为了理解我们在这里做什么，让我们首先考虑一个概念上相似的方法，它使用 std::vector<MyMesh::VertexHandle> candidates:

第一个循环：将v1的所有邻居添加到candidates
第二个循环：如果v2的邻居在candidates中found，添加它至 common_neighbors

然而，在向量上查找效率低下（与每次迭代候选向量相同）。这就是为什么我们用 unordered_map 替换候选向量的原因，这是一个平均复杂度为 O(1) 的哈希映射（最坏情况是 O(n) - 但实际上，我们可以假设它是 O (1)).

加强

如果将您的调用分组到 find_common_neighbors 有意义（并且可行），这样： ...MyMesh::VertexHandle & v1, std:vector<MyMesh::VertexHandle> & v2) - 然后，请注意第一个循环（填充候选地图）可以重复使用对于 v2 中的所有元素。所以我们得到 O(n1 + m * n2) 而不是 O(m * (n1 + n2))，其中 n1 是 v1 的大小，n2 是 v2 中的平均大小，m 是 v2 中的顶点数。

OpenMesh：快速搜索公共相邻顶点

OpenMesh: fast search of common neighbor vertices

c++

c++11

openmesh