javascript - 在半边(DCEL)数据结构中有效地找到双边？

我使用半边数据结构来表示网格上的面之间的连接。
我正在导入一个外部模型，并在导入过程中构造半边结构。但是，由于网格包含许多三角形，因此构建过程占用了太多时间。
具体来说，连接半边的过程似乎占用了最多的时间。
我想得到一些关于如何改进我的算法的建议。
下面是我用来初始化数据结构的代码第一个for循环使用顶点数据创建一个Face，同时将组成Face的半边推入一个单独的数组中，以便稍后立即使用。
第二个for循环负责查找所有半边的数组，并查找匹配对（即，两个互为孪生）。
我注销了每个进程前后的时间，并注意到第二个循环会减慢所有进程的速度。
这是时间戳
开始建造DCEL 14:55:22
开始制作面14:55:22
制端面14:55:22
/*这需要很长时间在13000个三角形的网格上大约6秒*/
开始链接半边14:55:22
端部连接半边14:55:28
结束施工DCEL 14:55:28
这是实际的代码

console.log('start constructing DCEL', new Date().toTimeString());

// initialize Half-Edge data structure (DCEL)
const initialFaceColor = new THREE.Color(1, 1, 1);
const { position } = geometry.attributes;
const faces = [];
const edges = [];
let newFace;

console.log('start making faces', new Date().toTimeString());
for (let faceIndex = 0; faceIndex < (position.count / 3); faceIndex++) {
  newFace = new Face().create(
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 0),
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 1),
    new THREE.Vector3().fromBufferAttribute(position, faceIndex * 3 + 2),
    faceIndex);
  edges.push(newFace.edge);
  edges.push(newFace.edge.next);
  edges.push(newFace.edge.prev);
  newFace.color = initialFaceColor;
  faces.push(newFace);
}

console.log('end making faces', new Date().toTimeString());
console.log('start linking halfEdges', new Date().toTimeString());

/**
  * Find and connect twin Half-Edges
  *
  * if two Half-Edges are twins:
  * Edge A   TAIL ----> HEAD
  *           =          =
  * Edge B   HEAD <---- TAIL
  */
let currentEdge;
let nextEdge;
for (let j = 0; j < edges.length; j++) {
  currentEdge = edges[j];

  // this edge has a twin already; skip to next one
  if (currentEdge.twin !== null) continue;

  for (let k = j + 1; k < edges.length; k++) {
    nextEdge = edges[k];

    // this edge has a twin already; skip to next one
    if (nextEdge.twin !== null) continue;

    if (currentEdge.head().equals(nextEdge.tail())
      && currentEdge.tail().equals(nextEdge.head())) {
          currentEdge.setTwin(nextEdge);
    }
  }
}

console.log('end linking halfEdges', new Date().toTimeString());
console.log('end constructing DCEL', new Date().toTimeString());

如何优化搜索双边的过程？

最佳答案

我试着散开并查找边缘，例如：

function hash(p1, p2) {
  return JSON.stringify(p1)+JSON.stringify(p2);
}
const lookup = {}
for (let j = 0; j < edges.length; j++) {
  lookup[hash(edge.head(), edge.tail())] = edge;
}
for (let j = 0; j < edges.length; j++) {
  const twin = lookup[hash(edge.tail(), edge.head())];
  !edge.twin && twin && !twin.twin && edge.setTwin(twin);
}