给定一个网格面，寻找它的相邻面。

Question

我正在尝试高效地查找给定面的所有相邻面。

我采取了一种巧妙的方法，但我想知道是否可以改进。

到目前为止，我采取的方法是在创建网格几何体之后创建数据结构。我建立了一个哈希数组，将顶点映射到由它们组成的面：

var vertexToFace = [];

function crossReference(g) {

    for (var fx = 0; fx < g.faces.length; fx++) {
        vertexToFace[fx] = new Array();
    }
    for (var fx = 0; fx < g.faces.length; fx++) {
        var f = g.faces[fx];
        var ax = f.a;
        var bx = f.b;
        var cx = f.c;

        vertexToFace[ax].push(fx);
        vertexToFace[bx].push(fx);
        vertexToFace[cx].push(fx);
    }
}

现在我有了数组的哈希值，就可以检索给定面的相邻面：

var neighbors = [];

neighbors.push( vertexToFace(face.a), vertexToFace(face.b), vertexToFace(face.c) );

这很好，但我想知道是否过于冗长。我知道geometry.faces中的每个面都包含成员a、b、c，它们是索引到geometry.vertices中的点的位置。

我不认为反向信息被存储，尽管令人心动的是，geometry.vertices中的每个点确实有.index成员，但似乎与面没有对应关系。

我是否漏掉了一些明显的东西？

谢谢/。

- Jeremy Fischer

Answer 1

对我来说，这取决于你的使用情况。如果你只想做一次，那么对我来说这确实是过度设计，我会遍历面来查找邻居。成本是O(#G)，在复杂性方面#G是面数。所以不错。下一次你做它的成本将再次是O(#G)。

在你的情况下，创建结构的成本是O(#G)，然后检索邻居的成本取决于数组实现，但可能是O(log(#V))，其中#V是顶点数。因此，第一次检索成本为O(#G+log(#V))，所以> O(#G)。然而，下一次检索仍然是O(log(#V))，所以在你有很多这样的检索操作的情况下，在大多数情况下似乎使用你的方法是有意义的。然而，你需要跟踪几何体何时发生变化，因为这会使你的结构无效。所以像往常一样 - 这取决于...

只是一个旁注 - 问题也是你认为什么是邻居。一个共同的顶点还是一个边...只是提一下，因为我刚刚遇到了一个后者。

- TomFree

Answer 2

我认为

for (var fx = 0; fx < g.faces.length; fx++) {
        vertexToFace[fx] = new Array();
}

应该被更改为

for (var fx = 0; fx < g.vertices.length; fx++) {
        vertexToFace[fx] = new Array();
}

否则，如果顶点数大于面数，则vertexToFace中的元素将不足。您还可以简化一下：

vertexToFace[fx] = [];

- dgmz