javascript - 查找相邻节点

Question

我有一系列多边形，用 3 个 vector3 对象表示。即:

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

其中a,b,c是三 Angular 形的三个点，索引的0,1分别是x,y。

如果这个对象在一个数组中，有 50 个左右的其他三 Angular 形，每个三 Angular 形都有一个共享顶点，我可以运行什么算法本身来创建某种兄弟三 Angular 形索引数组？

Answer 1

如果要查找共享公共(public)顶点的三 Angular 形，请创建一个对象，其键是顶点，其值是三 Angular 形数组或三 Angular 形数组或对象中的索引/键。

假设您有一个不变的三 Angular 形数组，您按该数组的索引存储三 Angular 形:

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 中查找顶点并获得一组相连的三 Angular 形。这个函数告诉你两个三 Angular 形是否相邻。如果是，则返回公共(public)节点，如果不是，则返回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;
}

如果你想找到有公共(public)边的三 Angular 形，你也可以使用这种方法。然后，您的 key 由两个顶点组成。您必须找到一种方法使顶点的顺序唯一，以便边 [1, 2], [5, 0] 等同于它的反向，[5, 0] , [1, 2]。一种方法是将较小的顶点作为边的第一个点。 (更小意味着 x 坐标较小的顶点，如果 n 相等，则两者都指向 y 坐标较小的顶点。)