JavaScript:四叉树比较 [英] JavaScript: Quadtree comparison
本文介绍了JavaScript:四叉树比较的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我没有找到任何快速算法来获取以下格式的四叉树差异.假设我们有两个任意的4级树:
I didn't find any fast algorithm for getting quad-trees differences in following format. Let's say that we have two arbitrary 4 level trees:
var tree1 = [
{ id: "1.1", children: [
{ id: "1.1.1", children: null },
{ id: "1.1.2", children: null },
{ id: "1.1.3", children: [
{ id: "1.1.3.1", children: null },
{ id: "1.1.3.2", children: null },
{ id: "1.1.3.3", children: null },
{ id: "1.1.3.4", children: null }
] },
{ id: "1.1.4", children: null }
] },
{ id: "1.2", children: null },
{ id: "1.3", children: [
{ id: "1.3.1", children: [
{ id: "1.3.1.1", children: null },
{ id: "1.3.1.2", children: null },
{ id: "1.3.1.3", children: null },
{ id: "1.3.1.4", children: null }
] },
{ id: "1.3.2", children: null },
{ id: "1.3.3", children: null },
{ id: "1.3.4", children: null }
] },
{ id: "1.4", children: null }
];
var tree2 = [
{ id: "1.1", children: [
{ id: "1.1.1", children: null },
{ id: "1.1.2", children: null },
{ id: "1.1.3", children: null },
{ id: "1.1.4", children: [
{ id: "1.1.4.1", children: null },
{ id: "1.1.4.2", children: null },
{ id: "1.1.4.3", children: null },
{ id: "1.1.4.4", children: null }
] }
] },
{ id: "1.2", children: [
{ id: "1.2.1", children: null },
{ id: "1.2.2", children: null },
{ id: "1.2.3", children: [
{ id: "1.2.3.1", children: null },
{ id: "1.2.3.2", children: null },
{ id: "1.2.3.3", children: null },
{ id: "1.2.3.4", children: null }
] },
{ id: "1.2.1", children: null }
]},
{ id: "1.3", children: null },
{ id: "1.4", children: [
{ id: "1.4.1", children: [
{ id: "1.4.1.1", children: null },
{ id: "1.4.1.2", children: null },
{ id: "1.4.1.3", children: null },
{ id: "1.4.1.4", children: null }
] },
{ id: "1.4.2", children: null },
{ id: "1.4.3", children: null },
{ id: "1.4.1", children: null }
] }
];
因此，我需要找到差异并将其返回为:
So, I need to find differences and return them as:
var result = {
"1.1.3.1" : "1.1.3",
"1.1.3.2" : "1.1.3",
"1.1.3.3" : "1.1.3",
"1.1.3.4" : "1.1.3",
"1.1.4" : ["1.1.4.1", "1.1.4.2", "1.1.4.3", "1.1.4.4"],
"1.2" : ["1.2.1", "1.2.2". ["1.2.3.1", "1.2.3.2", "1.2.3.3", "1.2.3.4"], "1.2.4"],
"1.3.1.1" : "1.3",
"1.3.1.2" : "1.3",
"1.3.1.3" : "1.3",
"1.3.1.4" : "1.3",
"1.3.2" : "1.3",
"1.3.3" : "1.3",
"1.3.4" : "1.3",
"1.4" : [["1.4.1.1", "1.4.1.2", "1.4.1.3", "1.4.1.4"], "1.4.2", "1.4.3", "1.4.4"]
};
如果可以看到，结果必须是与更新相对应的地图或字典.不知道如何将["1.1.3.1"，"1.1.3.2"，"1.1.3.3"，"1.1.3.4"]引用到单个索引，所以我将它们拆分了，但是如果有一个更优雅的方法方式，不客气.
If you can see, the result has to be a map or a dictionary corresponding to updates. Didn't know how to reference ["1.1.3.1", "1.1.3.2", "1.1.3.3", "1.1.3.4"] to a single index, so I have split them, however if there is a more elegant way, you're welcome.
此数据是手动创建的，如果有一些错误，敬请谅解.
This data was created manually, so sorry if there're some mistakes.
推荐答案
您可以构建一棵树，在其中添加标记 where 的树，以添加/删除树的一部分，并从中获得区别
You could build a tree where you add a marker where for adding/deleting a part of the tree and get from this the difference.
function getDifference(t1, t2) {
function getD(object, parent) {
function getKeys({ where, ...object }) {
return Object.keys(object).flatMap(k => [k, ...(object[k] ? getKeys(object[k]) : [])]);
}
var types;
Object
.entries(object)
.forEach(([k, { where, ...o }]) => {
if (where) {
let keys = getKeys(o);
if (!types) types = {};
if (!types[where]) types[where] = [];
types[where].push(keys.length ? [k, keys] : k);
} else {
getD(o, k);
}
});
if (types) {
if (-1 in types) result.push([types[-1], parent]);
if (1 in types) result.push([parent, types[1]]);
}
}
var temp = {},
add = (inc, tree) => ({ id, children }) => {
tree[id] = tree[id] || { where: 0 };
tree[id].where += inc;
if (children) children.forEach(add(inc, tree[id]));
},
result = [];
t1.forEach(add(-1, temp));
t2.forEach(add(1, temp));
getD(temp);
return result;
}
var tree1 = [{ id: "1.1", children: [{ id: "1.1.1", children: null }, { id: "1.1.2", children: null }, { id: "1.1.3", children: [{ id: "1.1.3.1", children: null }, { id: "1.1.3.2", children: null }, { id: "1.1.3.3", children: null }, { id: "1.1.3.4", children: null }] }, { id: "1.1.4", children: null }] }, { id: "1.2", children: null }, { id: "1.3", children: [{ id: "1.3.1", children: [{ id: "1.3.1.1", children: null }, { id: "1.3.1.2", children: null }, { id: "1.3.1.3", children: null }, { id: "1.3.1.4", children: null }] }, { id: "1.3.2", children: null }, { id: "1.3.3", children: null }, { id: "1.3.4", children: null }] }, { id: "1.4", children: null }],
tree2 = [{ id: "1.1", children: [{ id: "1.1.1", children: null }, { id: "1.1.2", children: null }, { id: "1.1.3", children: null }, { id: "1.1.4", children: [{ id: "1.1.4.1", children: null }, { id: "1.1.4.2", children: null }, { id: "1.1.4.3", children: null }, { id: "1.1.4.4", children: null }] }] }, { id: "1.2", children: [{ id: "1.2.1", children: null }, { id: "1.2.2", children: null }, { id: "1.2.3", children: [{ id: "1.2.3.1", children: null }, { id: "1.2.3.2", children: null }, { id: "1.2.3.3", children: null }, { id: "1.2.3.4", children: null }] }, { id: "1.2.4", children: null }] }, { id: "1.3", children: null }, { id: "1.4", children: [{ id: "1.4.1", children: [{ id: "1.4.1.1", children: null }, { id: "1.4.1.2", children: null }, { id: "1.4.1.3", children: null }, { id: "1.4.1.4", children: null }] }, { id: "1.4.2", children: null }, { id: "1.4.3", children: null }, { id: "1.4.4", children: null }] }],
result = getDifference(tree1, tree2);
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }这篇关于JavaScript:四叉树比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
