Поиск соседних узлов

Question

У меня есть серия многоугольников, представленных в 3 объектах vector3. то есть:

{ 
    "a": [1,2], 
    "b": [3,4], 
    "c": [5,6] 
} 

Где a,b,c находятся три точки треугольника, и индекса 0,1 являются x,y соответственно.

Если этот объект был в массиве с 50 или около того другими треугольниками, каждый из которых имеет общую вершину, какой алгоритм сам по себе мог бы запустить, чтобы создать какой-то массив индексов треугольников брата?

Answer 1

Если вы хотите найти треугольники, которые имеют общую вершину, создайте объект, ключи которого являются вершинами и значениями которых являются массивы треугольников или индексы/ключи в массиве или объекте треугольников.

Скажет у вас есть массив треугольников, которые не меняются, и вы храните треугольники по индексу этого массива:

var tria = [ 
    {a: [1, 2], b: [3, 4], c: [0, 6]}, 
    // more triangles ... 
]; 

var adjacent = {}; 

function addAdjacent(vertex, tria) { 
    if (!(vertex in adjacent)) adjacent[vertex] = []; 
    adjacent[vertex].push(tria); 

} 

for (var i = 0; i < tria.length; i++) { 
    var t = tria[i]; 

    addAdjacent(t.a, i); 
    addAdjacent(t.b, i); 
    addAdjacent(t.c, i); 
} 

Тогда вы можете посмотреть вершины в adjacent и получить массив соединенных треугольников. Эта функция указывает, смежны ли два треугольника. Если да, то он возвращает общий узел, если нет, то он возвращает null:

function isAdjacent(x, y) { 
    var t = tria[x]; 

    if (t.a in adjacent && ~adjacent[t.a].indexOf(y)) return t.a; 
    if (t.b in adjacent && ~adjacent[t.b].indexOf(y)) return t.b; 
    if (t.c in adjacent && ~adjacent[t.c].indexOf(y)) return t.c; 

    return null; 
} 

Если вы хотите, чтобы найти треугольники с общими ребрами, вы можете использовать этот подход тоже. Затем ваш ключ состоит из двух вершин. Вы должны найти способ сделать упорядочение вершин уникальным, так что ребро [1, 2], [5, 0] эквивалентно его обратному, [5, 0], [1, 2]. Один из способов сделать это - сделать меньшую вершину первой точкой ребра. (Меньшее означает вершину с меньшей координатой x, и если она равна n, то обе точки вершины с меньшей координатой y.)