如何找到独特的四叉树对？

Question

我正在使用四叉树数据结构在二维平面上查找附近的对象。我已经实现了一个工作四叉树，其中 returns 每个对象的数组，包括它的所有邻居。问题是，我需要这组列表中的每对唯一对象。

假设我在数组中有以下点 [a, b, c, d]。还有：

a 靠近 b,

b 靠近 c,

c 靠近 d,

因此，

a 不在 c 或 d,

附近

b 不在 d,

附近

c 不在 a,

附近

d 不在 a 或 b,

附近

因此，通过遍历每个对象并询问它的邻居，我将得到以下数组，其中每个元素都是一个数组，其中第一个元素是所讨论的对象，每个其他元素都是它的邻居：

[
  [a, b],       // a is only near b
  [b, a, c],    // So b is near c and also a
  [c, b, d],    // So c is near b and also d
  [d, c]        // d is only near c
]

我想要一个仅包含相邻对象的唯一对的数组（例如，同时具有 [a, b] 和 [b, a] 是不可接受的），因此在这种情况下，解决方案是：

[
  [a, b],
  [b, c],
  [c, d]
]

我怎样才能达到这个结果？

此外，如果代码尽可能优化，我们将不胜感激。非常感谢！

Answer 1

我解决了排序问题，但计算量很大，如果有人知道如何缩短这段代码，将不胜感激！

let unsortedArray = [
  ['a', 'b'],
  ['b', 'a', 'c'],
  ['c', 'b', 'd'],
  ['d', 'c']
];

function solver(arr) {
  // Detach first elements
  let groups = [];
  for (let i = 0; i < arr.length; i++) {
    let body = arr[i].shift();
    groups[i] = {body, others: arr[i]};
  }
  // Get all pairs
  let pairs = [];
  for (let i = 0; i < groups.length; i++) {
    for (let j = 0; j < groups[i].others.length; j++) {
      let pair = [groups[i].body, groups[i].others[j]];
      pairs.push(pair);
    }
  }
  // Filter non unique pairs
  for (let i = 0; i < pairs.length; i++) {
    for (let j = i + 1; j < pairs.length; j++) {
      if (pairs[i] == pairs[j] || (pairs[i][0] == pairs[j][1] && pairs[i][1] == pairs[j][0])) {
        pairs.splice(j, 1);
      }
    }
  }
  return pairs;
}

let sortedArray = solver(unsortedArray);
console.log(sortedArray);

Answer 2

我更多地围绕这些行思考

let unsortedArray = [
  ['a', 'b'],
  ['b', 'a', 'c'],
  ['c', 'b', 'd'],
  ['d', 'c']
];

function solver(arr) {
  let marked = {};
  let result = [];
  
  arr.forEach((arcs) => {
    let first;
    arcs.forEach((vertex, i) =>{
      if (i === 0 ) {
        first = vertex;
      } else {
        let forward = first+vertex, backward = vertex+first;

        if (!marked.hasOwnProperty(forward) && !marked.hasOwnProperty(backward)) {
          result.push([first, vertex]);
        }
        marked[forward] = 0;
        marked[backward] = 0;
      }
    });
  });
  
  return result;
}

console.log(solver(unsortedArray));

如何找到独特的四叉树对？

How to find unique pairs of a quad tree?

javascript

arrays

performance

data-structures

quadtree