Учитывая лицо сетки, найдите его соседние грани

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, но, похоже, не соответствует грани.

Я пропустил что-то очевидное?

Thanks /.

Answer 1

Я думаю, что

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] = []; 

Answer 2

Для меня это зависит от вашего прецедента. Если вы хотите сделать это только один раз, то для меня это действительно и излишний, и я просто буду проходить через лица, чтобы найти соседей. Стоимость - O (#G), чтобы говорить в терминах сложности #G - количество граней. Так не плохо. В следующий раз, когда вы это сделаете, стоимость снова будет равна O (#G).

В вашем случае стоимость O (#G) для создания структуры, а затем для извлечения соседей зависит от реализации массива, но, вероятно, O (log (#V)), где #V - количество вершин. Таким образом, первая стоимость поиска - O (# G + log (#V)), поэтому> O (#G). Затем поиск снова O (log (#V)), поэтому, если у вас есть много таких операций поиска, похоже, смысл использовать свой путь в большинстве случаев. Однако вам нужно будет отслеживать, когда геометрия будет изменена, поскольку это приведет к аннулированию вашей структуры. Так что так часто - это зависит ...

Просто боковое примечание - вопрос также является тем, что вы считаете соседом. Одна общая вершина или край ... Просто упоминая это, я просто имел случай, когда это было позже.