使用深度优先搜索渲染动态创建的家庭图形，不重叠？ [英] Rendering a dynamically created family graph with no overlapping using a depth first search?
本文介绍了使用深度优先搜索渲染动态创建的家庭图形，不重叠？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想生成这个：
使用这个数据结构（id是随机的，btw不是顺序的）：
var tree = [
{id ：1，name：我，dob：1988，children：[4]，partners：[2,3]，root：true，level：0，父母： [5,6]}，
{id：2，name：Mistress 1，dob：1987，children：[4]，partners ，等级：0，父母：[]}，
{id：3，name：妻子1，dob：1988，children：[5]伙伴：[1]，等级：0，父母：[]}，
{id：4，name：儿子1，dob：，children： []，伙伴：[]，等级：-1，父母：[1,2]}，
{id：5，name：女儿1，dob： ，children：[7]，partners：[6]，level：-1，parents：[1,3]}，
{id：6，name： 女儿1s男友，dob：，小孩：[7]，伙伴：[5]，级别：-1，父母：[]}，
{id：7，name：son（bottom most），dob：， children：[]，partners：[]，level：-2，parents：[5,6]}，
{id：8，name：jeff dob：，children：[1]，partners：[9]，level：1，parents：[10,11]}，
{id：9， ：maggie，dob：，children：[1]，partners：[8]，level：1，parents：[]}，
{id 10，name：bob，dob：，children：[8]，partners：[11]，level：2，parents：[12]}，
{id：11，name：mary，dob：，children：[]，partners：[10]，level：2，parents：[]}，
{id：12，name：john，dob：，children：[10]，partners：[]，level：3，parents：[] }，
{id：13，name：robert，dob：，children：[9]，partners：[]，level：2， ：[]，
{id：14，name：jessie，dob：，children：[9]，partners：[]，level：2， 父母：[15,16]}，
{id：15，name：raymond，dob： ，children：[14]，partners：[]，level：3，parents：[]}，
{id：16，name：betty dob：，children：[14]，partners：[]，level：3，parents：[]}，
];
为了说明数据结构，定义了根/起始节点（me）。任何伴侣（妻子，前夫）都在同一水平上。下面的任何东西都变成-1，-2。以上任何内容均为第1,2级等。父母，兄弟姐妹，子女和伴侣的属性定义了该特定字段的ID。
在我以前的问题，eh9 描述他将如何解决这个问题。我试图这样做，但正如我发现的那样，这不是一件容易的事情。
我的第一次尝试是从上到下的级别渲染。在这个更简单的尝试中，我基本上将所有人都嵌入层次并从上到下渲染。
我的第二次尝试正在渲染其中一个祖先节点使用深度优先搜索。
我的主要问题是：我怎样才能将该答案实际应用到我目前拥有的？在我的第二次尝试中，我试图进行深度优先遍历，但我怎么才能开始计算抵消网格所需的距离，以使其与我想要生成的网格一致？
另外，我理解/实现了深度优先的理想，还是我可以用不同的方式来遍历它？
例子，因为我没有抵消/距离计算代码，但我失去了实际计算如何开始。
下面是对walk函数的描述我做了，我试图在第一次遍历深度：
//这是用来映射节点到他们遍历的东西。所以在第一次调用john时，dict会内部存储：
// dict.getItems（）= [{'12'：[10]}]
//这意味着john（id = 10）遍历了bob（id = 10），如果代码已经遍历，代码将不会遍历它。
var dict = new Dictionary;
walk（nested [0] ['values'] [0]）; //这个叫做最高级别的第一个元素。在这种情况下，它是约翰
函数walk（person，fromPersonId，callback）{
//如果一个人没有在字典映射中定义，定义它们
if（dict.get（person.id）== null）{
dict.set（person.id，[]）;
if（fromPersonId！== undefined || first）{
var div = generateBlock（person，{
// this offset code needs被替换
top：first？0：parseInt（$（getNodeById（fromPersonId）.element）.css（'top'），10）+50，
left：first？0：parseInt（$ （getNodeById（fromPersonId）.element）.css（'left'），10）+50
}）;
//将此追加到画布
$（canvas）.append（div）;
person.element = div;
//如果这不是第一个实例，那么如果我们在另一个节点上调用walk，并且如果父节点没有被定义，定义它
if（fromPersonId！== undefined）{
if（dict.get（fromPersonId）== null）{
dict.set（fromPersonId，[]）;
}
//如果调用者人没有被定义为遍历当前节点，则定义他们
//所以在第一次调用walk时，fromPersonId是null
//它调用孩子上的步行，并从PersonsId传递，这是12
//所以这定义了{12：[10]}，因为fromPersonId是12，person.id是10（bob）
if（dict.get（fromPersonId）.indexOf（person.id）== -1）
dict.get（fromPersonId）.push（person.id）;
}
console.log（person.name）;
//关联关系id的属性列表
var iterable = ['partners'，'siblings'，'children'，'parents'];
iterable.forEach（function（property）{
if（person [property]）{
person [property] .forEach（function（nodeId）{
// if this person没有被遍历，遍历它们
if（dict.get（person.id）.indexOf（nodeId）== -1）
walk（getNodeById（nodeId），person.id，function ）{
dict.get（person.id）.push（nodeId）;
}）;
}）;
}
}）;
}
}
要求/限制：
- 这是一个编辑器，到familyecho.com。几乎任何未定义的业务规则都可以通过这种方式来假设。 家庭育种不支持，因为它会使这种方法过于复杂。不要担心这一点。
- 支持多个合作伙伴，因此这不像仅有2个父母和1个孩子的传统家谱那么简单。
- 只有一个根节点，它只是起始节点。
注意：如果有许多叶节点，familyecho.com似乎会隐藏一个分支，碰撞。可能需要执行此操作。
解决方案
尽管答案已发布（并已被接受），但我认为发布我昨天晚上在这个问题上做了些什么。
我从新手的角度来看待这个问题，而不是用现有的图/树遍历算法来解决这个问题。 p>
我的第一次尝试是从上到下按照级别进行渲染。在
这个更简单的尝试中，我基本上将所有人都嵌套在
的层次上，并从上到下渲染它。
这也是我的第一次尝试。您可以自上而下或自下而上或从根开始。正如你受到某个网站的启发，从根开始似乎是一个合理的选择。但是，我发现自下而上的方法更简单，更易于理解。
这是一个粗略的尝试：
绘制数据：
- 我们从最底层开始，向上工作。正如问题中提到的那样，您正在尝试通过编辑器解决这个问题，我们可以在构建树时将所有相关属性存储在对象数组中。
我们缓存关卡并使用它来遍历树：
//对于从最低一个
levels.forEach（函数（级别）{
//获取此级别的所有人员
var startAt = data.filter（function（person）{
return person。 level == level;
}）;
startAt.forEach（function（start）{
var person = getPerson（start.id）;
//绘制每个人级别
plotNode（person，'self'）;
//绘制合作伙伴
plotPartners（person）;
//绘制此人的父母走向
plotParents（person）;
}）;
}）;
其中， getPerson 数据基于它的 id 。
- 我们绘制节点本身，它的父母（递归）和它的合作伙伴。绘制合作伙伴并不是必须的，但我在这里做的只是为了绘制连接器很容易。如果一个节点已经被绘制出来，我们简单地跳过那部分。
这就是我们如何绘制合作伙伴的方式：
/ *为当前人绘制合作伙伴* /
函数plotPartners（start）{
if（！start）{return ; }
start.partners.forEach（function（partnerId）{
var partner = getPerson（partnerId）;
// Plot节点
plotNode（伙伴，'伙伴'，开始） ;
//绘制伙伴连接器
plotConnector（开始，伙伴，'伙伴'）;
}）;
}
父母递归：
/ *绘制父母走上树* /
函数plotParents（start）{
if（！start）{return; }
start.parents.reduce（function（previousId，currentId）{
var previousParent = getPerson（previousId），
currentParent = getPerson（currentId）;
// Plot node
plotNode（currentParent，'parents'，start，start.parents.length）;
//绘制多个父母的伙伴连接器
if（previousParent）{plotConnector（previousParent，currentParent，'partners' ）;}
//绘制父连接器
plotConnector（start，currentParent，'parents'）;
//通过向上移动树来递归并绘图父
plotParents（currentParent） ;
return currentId;
}，0）;
}
我们在哪里使用 reduce 来简化绘制两个父母之间的连接器作为合作伙伴。
- 这就是我们如何绘制节点本身的方式： li>
其中，我们通过 findLevel 实用程序函数重用每个唯一级别的坐标。我们维护一个关卡的地图，并检查它是否到达顶部位置。休息是根据关系确定的。
/ *绘制单个节点* /
函数plotNode（）{
var person = arguments [ 0]，relationType = arguments [1]，relative = arguments [2]，numberOfParents = arguments [3]，
node = get（person.id），relativeNode，element = {}，thisLevel，exists
;
if（node）{return; }
node = createNodeElement（person）;
//获取当前等级
thisLevel = findLevel（person.level）;
if（！thisLevel）{
thisLevel = {'level'：person.level，'top'：startTop};
levelMap.push（thisLevel）;
}
//根据关系确定相对于当前人的位置
if（relationType =='self'）{
node.style.left = startLeft +' PX';
node.style.top = thisLevel.top +'px';
} else {
relativeNode = get（relative.id）;
if（relationType =='partners'）{
//向右绘图
node.style.left =（parseInt（relativeNode.style.left）+ size +（gap * 2））+'px';
node.style.top = parseInt（relativeNode.style.top）+'px';
if（relationType =='children'）{
//绘制在$ b $下面b node.style.left =（parseInt（relativeNode.style.left） - size）+ 像素;
node.style.top =（parseInt（relativeNode.style.top）+ size + gap）+'px';
if（relationType =='parents'）{
//上面的绘图，如果单个父图直接位于其他图上，则用左偏移
if（numberOfParents == 1）{
node.style.left = parseInt（relativeNode.style.left）+'px';
node.style.top =（parseInt（relativeNode.style.top） - gap - size）+'px';
} else {
node.style.left =（parseInt（relativeNode.style.left） - size）+'px';
node.style.top =（parseInt（relativeNode.style.top） - gap - size）+'px';
//避免碰撞向右移动
while（exists = detectCollision（node））{
node.style.left =（ exists.left + size +（gap * 2））+'px';
}
//记录级别位置
if（thisLevel.top> parseInt（node.style.top））{
updateLevel（person.level，'顶部'，parseInt（node.style.top））;
}
element.id = node.id; element.left = parseInt（node.style.left）; element.top = parseInt（node.style.top）;
elements.push（element）;
//将节点添加到DOM树
tree.appendChild（node）;
$ b 为了简单起见，我使用了非常粗略的碰撞检测来移动节点当一个已经存在的时候向右。在一个非常复杂的应用程序中，这会动态地向左或向右移动节点以保持水平平衡。
最后，我们将该节点添加到DOM。
- 休息都是帮助功能。
重要的是：
$ $ p $ function detectCollision（node）{
var element = elements.filter（function （elem）{
var left = parseInt（node.style.left）;
return（（elem.left == left ||（elem.left< left&& left<（ elem.left + size + gap）））&& elem.top == parseInt（node.style.top））;
}）;
return element.pop（）;
$ / code>
上面是一个简单的碰撞检测，考虑到节点之间的差距。
并绘制连接器：
函数plotConnector（source ，destination，relation）{
var connector = document.createElement（'div'），orientation，start，stop，
x1，y1，x2，y2，length，angle，transform
;
orientation =（relation =='partners'）？ 'h'：'v';
connector.classList.add（'asset'）;
connector.classList.add（'connector'）;
connector.classList.add（orientation）;
start = get（source.id）; stop = get（destination.id）;
if（relation =='partners'）{
x1 = parseInt（start.style.left）+ size; y1 = parseInt（start.style.top）+（size / 2）;
x2 = parseInt（stop.style.left）; y2 = parseInt（stop.style.top）;
length =（x2 - x1）+'px';
connector.style.width = length;
connector.style.left = x1 +'px';
connector.style.top = y1 +'px';
if（relation =='parents'）{
x1 = parseInt（start.style.left）+（size / 2）; y1 = parseInt（start.style.top）;
x2 = parseInt（stop.style.left）+（size / 2）; y2 = parseInt（stop.style.top）+（size - 2）; （（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2））;（b1）
angle = Math.atan2（y2 - y1，x2 - x1）* 180 / Math.PI;
transform ='rotate（'+ angle +'deg）';
connector.style.width = length +'px';
connector.style.left = x1 +'px';
connector.style.top = y1 +'px';
connector.style.transform = transform;
}
tree.appendChild（connector）;
}
我使用了两个不同的连接器，一个连接伙伴的水平连接器，一个连接父母与子女的关系。这对我来说是非常棘手的部分，即绘制倒置] 水平连接器。这就是为什么要保持简单，我只是旋转一个div，使它看起来像一个有角度的连接器。
- 一次整个树被绘制/绘制，可能有节点由于负面位置而离开屏幕（因为我们正在自下而上）。为了弥补这一点，我们只需检查是否有任何负面的位置，然后向下移动整个树。
这是完整的代码与小提琴演示。
小提琴演示： http ：//jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/
这是一个编辑器，类似于
创建编辑器：
测试它是否有效的最好方法是有一个编辑器，它允许您即时创建这样的树/图并查看它是否成功地绘制。
所以，我还创建了一个简单的编辑器来测试。代码保持完全一样，但已重新考虑了一点，以适应编辑器的例程。
编辑小提琴演示： http：// jsfiddle .net / abhitalks / 56whqh0w / embedded / result
$ b
带编辑器的片段演示（查看全屏幕）：
var sampleData = [{id：1，name：我，children： [4]，伙伴：[2,3]，根：真，等级：0，父母：[8,9]}，{id：2，名字：女主人， ：[4]，伙伴：[1]，等级：0，父母：[]，{id：3，名字：妻子，子女：[5]伙伴：[1]，等级：0，父母：[]，{id：4，name：儿子，children：[]，partners -1，父母：[1,2]}，{id：5，名字：女儿，子女：[7]，伙伴：[6]，等级： 父母：[1,3]}，{id：6，姓名：男朋友，子女：[7 ]，伙伴：[5]，等级：-1，父母：[]}，{id：7，名字：儿子最后，子女：[]，伙伴： []，level：-2，parents：[5,6]}，{id：8，name：Jeff，children：[1]，partners：[9]，等级：1，父母：[10,11]}，{id：9，名字：玛姬，子女：[1]，合伙人：[8]，等级： 父母：[13,14]}，{id：10，name：Bob，children：[8]，partners：[11]，level：2，parents： [12]}，{id：11，name：Mary，children：[]，partners：[10]，level：2，parents：[]}，{id ：12，name：John，children：[10]，partners：[]，level：3，parents：[]}，{id：13，name： 罗伯特，孩子：[9]，伙伴：[14]，等级：2，父母：[]}，{id：14，名字：Jessie， ：[9]，伙伴：[13]，等级：2，父母：[15,16]}，{id：15，名字：雷蒙德， ，伙伴：[16]，等级：3，父母：[]}，{id：16，名字：贝蒂，子女：[14] ]，等级：3，父母：[]}，]， data = []，elements = []，levels = []，levelMap = []，tree = document.getElementById（'tree'），people = document.getElementById（'people'），selectedNode，startTop，startLeft，gap = 32，size = 64; / *模板对象为person * / function Person（id）{this.id = id？ ID ： ''; this.name = id？ ID ： ''; this.partners = []; this.siblings = []; this.parents = []; this.children = []; this.level = 0; this.root = false;} / *事件监听器* / tree.addEventListener（'click'，function（e）{if（e.target.classList.contains（'node'））{selectedNode = e.target; select ）; document.getElementById（'save'）。addEventListener（'click'，function（）{var pname = document.getElementById（'title'）。 getElementById（'pname'）.value; if（pname.length> 0）{data.forEach（function（person）{if（person.id == selectedNode.id）{person.name = pname; selectedNode.textContent = （document.getElementById（'title'）。textContent = pname;}}）;}}）; document.getElementById（'add'）。addEventListener（'click'，function（）{addPerson（document.getElementById ）。价值）; plotTree（）;}）; document.getElementById（'addExisting'）。addEventListener（'click'，function（）{attachParent（）; plotTree（）;}）; document.getElementById（'clear'）。addEventListener（'click'，startFresh）; addEventListener（'click'，function（）{data = sampleData.slice（）; plotTree（）;}）; addEventListener（'click'，function（）{if（data.length> 1）{var download = JSON.stringify（data，null，4）; var payload =text / json ; charset = utf-8，+ encodeURIComponent（download）; var a = document.createElement（'a'）; a.href ='data：'+ payload; a.download ='data.json'; a.innerHTML ='点击下载'; var container = document.getElementById（'downloadLink'）; container.appendChild（a）;}}）; / *初始化* /函数appInit（）{//近似于div的中心startTop = parseInt（（tree.clientHeight / 2） - （size / 2））; startLeft = parseInt（（tree.clientWidth / 2） - （size / 2））; } / *开始一个新的树* / function startFresh（）{var start，downloadArea = document.getElementById（'downloadLink'）; //重置数据缓存数据= []; appInit（）; while（downloadArea.hasChildNodes（））{downloadArea.removeChild（downloadArea.lastChild）; } //添加一个root我人，以start = new Person开头（'P01'）; start.name ='我'; start.root = true; data.push（开始）; //绘制树plotTree（）; //预先选择根节点selectedNode = get（'P01'）; document.getElementById（'title'）。textContent = selectedNode.textContent;} / *从下往上绘制整个树* / function plotTree（）{//重置其他缓存和DOM元素= []，levels = []，levelMap = [] while（tree.hasChildNodes（））{tree.removeChild（tree.lastChild）; （function（elem）{if（levels.indexOf（elem.level）=== -1）{levels.push（elem.level）;}}）; //获取所有可用的数据data.forEach //按照升序对levels进行排序levels.sort（function（a，b）{return a - b;}）; //从所有级别开始levels.forEach（function（level）{//从此级别获取所有人员var startAt = data.filter（function（person）{return person.level == level;}）; startAt .forEach（function（start）{var person = getPerson（start.id）; //绘制每个人在这个级别plotNode（person，'self'）; //绘制伙伴plotPartners（person）; //并绘制父母这个人往上走plotParents（person）;}）;}）; //调整坐标以保持树或多或少处于中心位置adjustNegatives（）; } / *为当前人绘制伙伴* / function plotPartners（start）{if（！start）{return; } start.partners.forEach（function（partnerId）{var partner = getPerson（partnerId）; //绘制节点plotNode（伙伴，'伙伴'，开始）; //绘制伙伴连接器plotConnector（start，partner，'partners'） ;}）;} / *绘制父母走上树* / function plotParents（start）{if（！start）{return; } start.parents.reduce（function（previousId，currentId）{var previousParent = getPerson（previousId），currentParent = getPerson（currentId）; //绘制节点plotNode（currentParent，'parents'，start，start.parents.length）; //绘制伙伴连接器，如果有多个父母if（previousParent）{plotConnector（previousParent，currentParent，'partners'）;} //绘制父连接器plotConnector（start，currentParent，'parents'）; //递归树plotParents（currentParent）; return currentId;}，0）;} / *绘制单个节点* / function plotNode（）{var person = arguments [0]，relationType = arguments [1]，relative = arguments [2] ，numberOfParents = arguments [3]，node = get（person.id），relativeNode，element = {}，thisLevel，exists; if（node）{return; } node = createNodeElement（person）; //获取当前级别thisLevel = findLevel（person.level）;如果（！thisLevel）{thisLevel = {'level'：person.level，'top'：startTop}; levelMap.push（thisLevel）; } //根据关系确定要相对于当前人绘制的位置if（relationType =='self'）{node.style.left = startLeft +'px';} node.style.top = thisLevel.top +'px'; } else {relativeNode = get（relative.id）; } if（relationType =='partners'）{//绘制到右边node.style.left =（parseInt（relativeNode.style.left）+ size +（gap * 2））+'px'; node.style.top = parseInt（relativeNode.style.top）+'px'; } if（relationType =='children'）{// Plot below node.style.left =（parseInt（relativeNode.style.left） - size）+'px'; node.style.top =（parseInt（relativeNode.style.top）+ size + gap）+'px'; }如果（relationType =='parents'）{//上面的情节，如果直接在上面的单个父图直接绘制左偏移if（numberOfParents == 1）{node.style.left = parseInt（relativeNode.style.left ）+'px'; node.style.top =（parseInt（relativeNode.style.top） - gap-size）+'px'; } else {node.style.left =（parseInt（relativeNode.style.left） - size）+'px'; node.style.top =（parseInt（relativeNode.style.top） - gap-size）+'px'; （exists = detectCollision（node））{node.style.left =（exists.left + size +（gap * 2））+'px';}} //避免碰撞向右移动while } //记录级别位置if（thisLevel.top> parseInt（node.style.top））{updateLevel（person.level，'top'，parseInt（node.style.top））; } element.id = node.id; element.left = parseInt（node.style.left）; element.top = parseInt（node.style.top）; elements.push（元件）; //将节点添加到DOM树tree.appendChild（node）; } / * Helper函数* / function createNodeElement（person）{var node = document.createElement（'div'）; node.id = person.id; node.classList.add（节点）; node.classList.add（资产）; node.textContent = person.name; node.setAttribute（'data-level'，person.level）; return node;} function select（selectedNode）{var allNodes = document.querySelectorAll（'div.node'）; [] .forEach.call（allNodes，function（node）{node.classList.remove（'selected'）;}）; selectedNode.classList.add（'selected'）;} function get（id）{return document.getElementById（id）; } function getPerson（id）{var element = data.filter（function（elem）{return elem.id == id;}）;返回element.pop（）;}函数fillPeopleAtLevel（）{if（！selectedNode）return; var person = getPerson（selectedNode.id），level =（person.level + 1），persons，option; while（people.hasChildNodes（））{people.removeChild（people.lastChild）; } data.forEach（function（elem）{if（elem.level === level）{option = document.createElement（'option'）; option.value = elem.id; option.textContent = elem.name; people。的appendChild（可选）;}}）;返回的人;}函数attachParent（）{var parentId = people.value，thisId = selectedNode.id; updatePerson（thisId，'parents'，parentId）; updatePerson（parentId，'children'，thisId）;} function addPerson（relationType）{var newId ='P'+（data.length< 9''0'+（data.length + 1）：data.length + 1 ），newPerson = new Person（newId），thisPerson; ; thisPerson = getPerson（selectedNode.id）; //在原始人和此人之间添加关系updatePerson（thisPerson.id，relationType，newId）; switch（relationType）{case'children'：newPerson.parents.push（thisPerson.id）; newPerson.level = thisPerson.level - 1;打破; case'partners'：newPerson.partners.push（thisPerson.id）; newPerson.level = thisPerson.level;打破; case'siblings'：newPerson.siblings.push（thisPerson.id）; newPerson.level = thisPerson.level; //为原始人的所有其他亲属添加关系newPerson = addRelation（thisPerson.id，relationType，newPerson）;打破; case'parents'：newPerson.children.push（thisPerson.id）; newPerson.level = thisPerson.level + 1;打破; } data.push（newPerson）;} function updatePerson（id，key，value）{data.forEach（function（person）{if（person.id === id）{if（person [key] .constructor === Array）{person [key] .push（value）;} else {person [key] = value;}}}）;}函数addRelation（id，relationType，newPerson）{data.forEach（function（person）{if person [relationType] .indexOf（id）！= -1）{person [relationType] .push（newPerson.id）; newPerson [relationType] .push（person.id）;}}）; return newPerson;} function findLevel（level）{var element = levelMap.filter（function（elem）{return elem.level == level;}）;返回element.pop（）;}函数updateLevel（id，key，value）{levelMap.forEach（function（level）{if（level.level === id）{level [key] = value;}}）;}函数detectCollision（node）{var element = elements.filter（function（elem）{var left = parseInt（node.style.left）; return（（elem.left == left ||（elem.left< left& & left<（elem.left + size + gap）））&& elem.top == parseInt（node.style.top））;}）; return element.pop（）;}函数adjustNegatives（）{var allNodes = document.querySelectorAll（'div.asset'），minTop = startTop，diff = 0; for（var i = 0; i< allNodes.length; i ++）{if（parseInt（allNodes [i] .style.top）< minTop）{minTop = parseInt（allNodes [i] .style.top）; }}; if（minTop< startTop）{diff = Math.abs（minTop）+ gap; for（var i = 0; i< allNodes.length; i ++）{allNodes [i] .style.top = parseInt（allNodes [i] .style.top）+ diff +'px'; }; }}function plotConnector(source, destination, relation) {\tvar connector = document.createElement(’div’), orientation, start, stop, \t\tx1, y1, x2, y2, length, angle, transform\t; orientation = (relation == ’partners’) ? ’h’ : ’v’; connector.classList.add(’asset’); connector.classList.add(’connector’); connector.classList.add(orientation); start = get(source.id); stop = get(destination.id); if (relation == ’partners’) {\t\tx1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2); x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top); length = (x2 - x1) + ’px’; connector.style.width = length; connector.style.left = x1 + ’px’; connector.style.top = y1 + ’px’; }\tif (relation == ’parents’) {\t\tx1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top); x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2); length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); angle = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI; transform = ’rotate(’ + angle + ’deg)’; connector.style.width = length + ’px’; connector.style.left = x1 + ’px’; connector.style.top = y1 + ’px’; connector.style.transform = transform; }\ttree.appendChild(connector);}\t\t/* App Starts Here */appInit();startFresh();* { box-sizing: border-box;填充：0;保证金：0; }html, body { width: 100vw;身高：100vh;溢出：隐藏; font-family：sans-serif; font-size: 0.9em; }#editor { float: left; width: 20vw;身高：100vh;溢出：隐藏; overflow-y：scroll; border：1px solid #ddd; }#tree { float: left; width: 80vw;身高：100vh;溢出：自动;位置：相对; }h2 { text-align: center; margin: 12px;颜色：#bbb; }fieldset { margin: 12px; padding: 8px 4px; border：1px solid #bbb; }legend { margin: 0px 8px;填充：4px; }button, input, select { padding: 4px; margin: 8px 0px; }button { min-width: 64px; }div.node {\twidth: 64px; height: 64px; line-height: 64px; background-color: #339; color: #efefef; font-family：sans-serif; font-size: 0.7em; text-align：center;边界半径：50％;溢出：隐藏;位置：绝对; cursor: pointer;} div.connector { position: absolute; background-color：＃333; z-index: -10; }div.connector.h { height: 2px; background-color: #ddd; }div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }div[data-level=’0’] { background-color: #933; }div[data-level=’1’], div[data-level=’-1’] { background-color: #393; }div[data-level=’2’], div[data-level=’-2’] { background-color: #333; }div.node.selected { background-color: #efefef;颜色：＃444; }<div id=\"editor\"> <h2 id=\"title\">Me</h2> <div> <fieldset> <legend>Change Name</legend> <label>Name: <input id=\"pname\" type=\"text\" /></label> <br /><button id=\"save\">Ok</button> </fieldset> <fieldset> <legend>Add Nodes</legend> <label for=\"relation\">Add: </label> <select id=\"relation\"> <option value=\"partners\">Partner</option> <option value=\"siblings\">Sibling</option> <option value=\"parents\">Parent</option> <option value=\"children\">Child</option> </select> <button id=\"add\">Ok</button><br /> <label for=\"relation\">Add: </label> <select id=\"people\"></select> <button id=\"addExisting\">As Parent</button> </fieldset> <fieldset> <legend>Misc</legend> <button id=\"clear\">Clear</button> <button id=\"sample\">Load Sample</button> <br/><button id=\"download\">Download Data</button> </fieldset> <fieldset id=\"downloadLink\"></fieldset> </div></div><div id=\"tree\"></div>This is all a very crude attempt and beyond doubts an un-optimized one. What I particularly couldn’t get done are:
- Getting inverted
[or]shaped horizontal connectors for parent-child relationships. - Getting the tree to be horizontally balanced. i.e. dynamically figuring out which is the heavier side and then shifting those nodes to the left.
- Getting the parent to centrally align with respect to children especially multiple children. Currently, my attempt simply pushes everything to right in order.
Hope it helps. And posting it here so that I too can refer to it when needed.
I want to generate this:
With this data structure (ids are random, btw not sequential):
var tree = [
{ "id": 1, "name": "Me", "dob": "1988", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [5,6] },
{ "id": 2, "name": "Mistress 1", "dob": "1987", "children": [4], "partners" : [1], level: 0, "parents": [] },
{ "id": 3, "name": "Wife 1", "dob": "1988", "children": [5], "partners" : [1], level: 0, "parents": [] },
{ "id": 4, "name": "son 1", "dob": "", "children": [], "partners" : [], level: -1, "parents": [1,2] },
{ "id": 5, "name": "daughter 1", "dob": "", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
{ "id": 6, "name": "daughter 1s boyfriend", "dob": "", "children": [7], "partners" : [5], level: -1, "parents": [] },
{ "id": 7, "name": "son (bottom most)", "dob": "", "children": [], "partners" : [], level: -2, "parents": [5,6] },
{ "id": 8, "name": "jeff", "dob": "", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
{ "id": 9, "name": "maggie", "dob": "", "children": [1], "partners" : [8], level: 1, "parents": [] },
{ "id": 10, "name": "bob", "dob": "", "children": [8], "partners" : [11], level: 2, "parents": [12] },
{ "id": 11, "name": "mary", "dob": "", "children": [], "partners" : [10], level: 2, "parents": [] },
{ "id": 12, "name": "john", "dob": "", "children": [10], "partners" : [], level: 3, "parents": [] },
{ "id": 13, "name": "robert", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [] },
{ "id": 14, "name": "jessie", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [15,16] },
{ "id": 15, "name": "raymond", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
{ "id": 16, "name": "betty", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
];
To give a description of the data structure, the root/starting node (me) is defined. Any partner (wife,ex) is on the same level. Anything below becomes level -1, -2. Anything above is level 1, 2, etc. There are properties for parents, siblings, children and partners which define the ids for that particular field.
In my previous question, eh9 described how he would solve this. I am attempting to do this, but as I've found out, it isn't an easy task.
My first attempt is rendering this by levels from the top down. In this more simplistic attempt, I basically nest all of the people by levels and render this from the top down.
My second attempt is rendering this with one of the ancestor nodes using a depth-first search.
My main question is: How can I actually apply that answer to what I currently have? In my second attempt I'm trying to do a depth first traversal but how can I even begin to account for calculating the distances necessary to offset the grids to make it consistent with how I want to generate this?
Also, is my understanding/implementation of depth-first ideal, or can I traverse this differently?
The nodes obviously overlap in my second example since I have no offsetting/distance calculation code, but I'm lost as to actually figuring out how I can begin that.
Here is a description of the walk function I made, where I am attempting a depth first traversal:
// this is used to map nodes to what they have "traversed". So on the first call of "john", dict would internally store this:
// dict.getItems() = [{ '12': [10] }]
// this means john (id=10) has traversed bob (id=10) and the code makes it not traverse if its already been traversed.
var dict = new Dictionary;
walk( nested[0]['values'][0] ); // this calls walk on the first element in the "highest" level. in this case it's "john"
function walk( person, fromPersonId, callback ) {
// if a person hasn't been defined in the dict map, define them
if ( dict.get(person.id) == null ) {
dict.set(person.id, []);
if ( fromPersonId !== undefined || first ) {
var div = generateBlock ( person, {
// this offset code needs to be replaced
top: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css('top'), 10 )+50,
left: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css('left'), 10 )+50
});
//append this to the canvas
$(canvas).append(div);
person.element = div;
}
}
// if this is not the first instance, so if we're calling walk on another node, and if the parent node hasn't been defined, define it
if ( fromPersonId !== undefined ) {
if ( dict.get(fromPersonId) == null ) {
dict.set(fromPersonId, []);
}
// if the "caller" person hasn't been defined as traversing the current node, define them
// so on the first call of walk, fromPersonId is null
// it calls walk on the children and passes fromPersonId which is 12
// so this defines {12:[10]} since fromPersonId is 12 and person.id would be 10 (bob)
if ( dict.get(fromPersonId).indexOf(person.id) == -1 )
dict.get(fromPersonId).push( person.id );
}
console.log( person.name );
// list of properties which house ids of relationships
var iterable = ['partners', 'siblings', 'children', 'parents'];
iterable.forEach(function(property) {
if ( person[property] ) {
person[property].forEach(function(nodeId) {
// if this person hasnt been "traversed", walk through them
if ( dict.get(person.id).indexOf(nodeId) == -1 )
walk( getNodeById( nodeId ), person.id, function() {
dict.get(person.id).push( nodeId );
});
});
}
});
}
}
Requirements/restrictions:
- This is for an editor and would be similar to familyecho.com. Pretty much any business rules not defined can be assumed through that.
- In-family breeding isn't supported as it would make this way too complex. Don't worry about this.
- Multiple partners are supported so this isn't as easy as a traditional "family tree" with just 2 parents and 1 child.
- There is only one "root" node, which is just the starting node.
Notes: familyecho.com seems to "hide" a branch if there's lots of leaf nodes and there's a collision. May need to implement this.
解决方案
Although an answer has been posted (and accepted), I thought there is no harm in posting what I worked upon this problem last night.
I approached this problem more from a novice point of view rather than working out with existing algorithms of graph/tree traversal.
My first attempt is rendering this by levels from the top down. In this more simplistic attempt, I basically nest all of the people by levels and render this from the top down.
This was exactly my first attempt as well. You could traverse the tree top-down, or bottom-up or starting from the root. As you have been inspired by a particular website, starting from the root seems to be a logical choice. However, I found the bottom-up approach to be simpler and easier to understand.
Here is a crude attempt:
Plotting the data:
- We start from the bottom-most layer and work our way upwards. As mentioned in the question that you are trying to work it out via an editor, we can store all related properties in the object array as we build the tree.
We cache the levels and use that to walk up the tree:
// For all level starting from lowest one
levels.forEach(function(level) {
// Get all persons from this level
var startAt = data.filter(function(person) {
return person.level == level;
});
startAt.forEach(function(start) {
var person = getPerson(start.id);
// Plot each person in this level
plotNode(person, 'self');
// Plot partners
plotPartners(person);
// And plot the parents of this person walking up
plotParents(person);
});
});
Where, getPerson gets the object from the data based on its id.
- As we are walking up, we plot the node itself, its parents (recursively) and its partners. Plotting partners is not really required, but I did it here just so that plotting the connectors could be easy. If a node has already been plotted, we simply skip that part.
This is how we plot the partners:
/* Plot partners for the current person */
function plotPartners(start) {
if (! start) { return; }
start.partners.forEach(function(partnerId) {
var partner = getPerson(partnerId);
// Plot node
plotNode(partner, 'partners', start);
// Plot partner connector
plotConnector(start, partner, 'partners');
});
}
And the parents recursively:
/* Plot parents walking up the tree */
function plotParents(start) {
if (! start) { return; }
start.parents.reduce(function(previousId, currentId) {
var previousParent = getPerson(previousId),
currentParent = getPerson(currentId);
// Plot node
plotNode(currentParent, 'parents', start, start.parents.length);
// Plot partner connector if multiple parents
if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }
// Plot parent connector
plotConnector(start, currentParent, 'parents');
// Recurse and plot parent by walking up the tree
plotParents(currentParent);
return currentId;
}, 0);
}
Where we use reduce to simplify plotting a connector between two parents as partners.
- This is how we plot a node itself:
Where, we reuse the coordinates for each unique level via the findLevel utility function. We maintain a map of levels and check that to arrive at the top position. Rest is determined on the basis of relationships.
/* Plot a single node */
function plotNode() {
var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],
node = get(person.id), relativeNode, element = {}, thisLevel, exists
;
if (node) { return; }
node = createNodeElement(person);
// Get the current level
thisLevel = findLevel(person.level);
if (! thisLevel) {
thisLevel = { 'level': person.level, 'top': startTop };
levelMap.push(thisLevel);
}
// Depending on relation determine position to plot at relative to current person
if (relationType == 'self') {
node.style.left = startLeft + 'px';
node.style.top = thisLevel.top + 'px';
} else {
relativeNode = get(relative.id);
}
if (relationType == 'partners') {
// Plot to the right
node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';
node.style.top = parseInt(relativeNode.style.top) + 'px';
}
if (relationType == 'children') {
// Plot below
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px';
}
if (relationType == 'parents') {
// Plot above, if single parent plot directly above else plot with an offset to left
if (numberOfParents == 1) {
node.style.left = parseInt(relativeNode.style.left) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
} else {
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
}
}
// Avoid collision moving to right
while (exists = detectCollision(node)) {
node.style.left = (exists.left + size + (gap * 2)) + 'px';
}
// Record level position
if (thisLevel.top > parseInt(node.style.top)) {
updateLevel(person.level, 'top', parseInt(node.style.top));
}
element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);
elements.push(element);
// Add the node to the DOM tree
tree.appendChild(node);
}
Here to keep it simple, I used a very crude collision detection to move nodes to right when one already exists. In a much sophisticated app, this would move nodes dynamically to the left or right to maintain a horizontal balance.
Lastly, we add that node to the DOM.
- Rest are all helper functions.
The important ones are:
function detectCollision(node) {
var element = elements.filter(function(elem) {
var left = parseInt(node.style.left);
return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
});
return element.pop();
}
Above is a simple detection of collision taking into account the gap between the nodes.
And, to plot the connectors:
function plotConnector(source, destination, relation) {
var connector = document.createElement('div'), orientation, start, stop,
x1, y1, x2, y2, length, angle, transform
;
orientation = (relation == 'partners') ? 'h' : 'v';
connector.classList.add('asset');
connector.classList.add('connector');
connector.classList.add(orientation);
start = get(source.id); stop = get(destination.id);
if (relation == 'partners') {
x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
length = (x2 - x1) + 'px';
connector.style.width = length;
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
}
if (relation == 'parents') {
x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);
length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
angle = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
transform = 'rotate(' + angle + 'deg)';
connector.style.width = length + 'px';
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
connector.style.transform = transform;
}
tree.appendChild(connector);
}
I used two different connectors, a horizontal one to connect partners, and an angled one to connect parent-child relationships. This turned out to be a very tricky part for me, i.e. to plot inverted ] horizontal connectors. This is why to keep it simple, I simply rotated a div to make it look like an angled connector.
- Once the entire tree is drawn/plotted, there could be nodes which go off-screen due to negative positions (because we are traversing bottom-up). To offset this, we simply check if there are any negative positions, and then shift the entire tree downwards.
Here is the complete code with a fiddle demo.
Fiddle Demo: http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/
This is for an editor and would be similar to
Creating an editor:
The best way to test if it works, is to have an editor which allows you to create such trees/graphs on the fly and see if it plots successfully.
So, I also created a simple editor to test out. The code remains exactly the same, however has been re-factored a little to fit with the routines for the editor.
Fiddle Demo with Editor: http://jsfiddle.net/abhitalks/56whqh0w/embedded/result
Snippet Demo with Editor (view full-screen):
var sampleData = [
{ "id": 1, "name": "Me", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [8,9] },
{ "id": 2, "name": "Mistress", "children": [4], "partners" : [1], level: 0, "parents": [] },
{ "id": 3, "name": "Wife", "children": [5], "partners" : [1], level: 0, "parents": [] },
{ "id": 4, "name": "Son", "children": [], "partners" : [], level: -1, "parents": [1,2] },
{ "id": 5, "name": "Daughter", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
{ "id": 6, "name": "Boyfriend", "children": [7], "partners" : [5], level: -1, "parents": [] },
{ "id": 7, "name": "Son Last", "children": [], "partners" : [], level: -2, "parents": [5,6] },
{ "id": 8, "name": "Jeff", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
{ "id": 9, "name": "Maggie", "children": [1], "partners" : [8], level: 1, "parents": [13,14] },
{ "id": 10, "name": "Bob", "children": [8], "partners" : [11], level: 2, "parents": [12] },
{ "id": 11, "name": "Mary", "children": [], "partners" : [10], level: 2, "parents": [] },
{ "id": 12, "name": "John", "children": [10], "partners" : [], level: 3, "parents": [] },
{ "id": 13, "name": "Robert", "children": [9], "partners" : [14], level: 2, "parents": [] },
{ "id": 14, "name": "Jessie", "children": [9], "partners" : [13], level: 2, "parents": [15,16] },
{ "id": 15, "name": "Raymond", "children": [14], "partners" : [16], level: 3, "parents": [] },
{ "id": 16, "name": "Betty", "children": [14], "partners" : [15], level: 3, "parents": [] },
],
data = [], elements = [], levels = [], levelMap = [],
tree = document.getElementById('tree'), people = document.getElementById('people'), selectedNode,
startTop, startLeft, gap = 32, size = 64
;
/* Template object for person */
function Person(id) {
this.id = id ? id : '';
this.name = id ? id : '';
this.partners = [];
this.siblings = [];
this.parents = [];
this.children = [];
this.level = 0;
this.root = false;
}
/* Event listeners */
tree.addEventListener('click', function(e) {
if (e.target.classList.contains('node')) {
selectedNode = e.target;
select(selectedNode);
document.getElementById('title').textContent = selectedNode.textContent;
fillPeopleAtLevel();
}
});
document.getElementById('save').addEventListener('click', function() {
var pname = document.getElementById('pname').value;
if (pname.length > 0) {
data.forEach(function(person) {
if (person.id == selectedNode.id) {
person.name = pname;
selectedNode.textContent = pname;
document.getElementById('title').textContent = pname;
}
});
}
});
document.getElementById('add').addEventListener('click', function() {
addPerson(document.getElementById('relation').value);
plotTree();
});
document.getElementById('addExisting').addEventListener('click', function() {
attachParent();
plotTree();
});
document.getElementById('clear').addEventListener('click', startFresh);
document.getElementById('sample').addEventListener('click', function() {
data = sampleData.slice();
plotTree();
});
document.getElementById('download').addEventListener('click', function() {
if (data.length > 1) {
var download = JSON.stringify(data, null, 4);
var payload = "text/json;charset=utf-8," + encodeURIComponent(download);
var a = document.createElement('a');
a.href = 'data:' + payload;
a.download = 'data.json';
a.innerHTML = 'click to download';
var container = document.getElementById('downloadLink');
container.appendChild(a);
}
});
/* Initialize */
function appInit() {
// Approximate center of the div
startTop = parseInt((tree.clientHeight / 2) - (size / 2));
startLeft = parseInt((tree.clientWidth / 2) - (size / 2));
}
/* Start a fresh tree */
function startFresh() {
var start, downloadArea = document.getElementById('downloadLink');
// Reset Data Cache
data = [];
appInit();
while (downloadArea.hasChildNodes()) { downloadArea.removeChild(downloadArea.lastChild); }
// Add a root "me" person to start with
start = new Person('P01'); start.name = 'Me'; start.root = true;
data.push(start);
// Plot the tree
plotTree();
// Pre-select the root node
selectedNode = get('P01');
document.getElementById('title').textContent = selectedNode.textContent;
}
/* Plot entire tree from bottom-up */
function plotTree() {
// Reset other cache and DOM
elements = [], levels = [], levelMap = []
while (tree.hasChildNodes()) { tree.removeChild(tree.lastChild); }
// Get all the available levels from the data
data.forEach(function(elem) {
if (levels.indexOf(elem.level) === -1) { levels.push(elem.level); }
});
// Sort the levels in ascending order
levels.sort(function(a, b) { return a - b; });
// For all level starting from lowest one
levels.forEach(function(level) {
// Get all persons from this level
var startAt = data.filter(function(person) {
return person.level == level;
});
startAt.forEach(function(start) {
var person = getPerson(start.id);
// Plot each person in this level
plotNode(person, 'self');
// Plot partners
plotPartners(person);
// And plot the parents of this person walking up
plotParents(person);
});
});
// Adjust coordinates to keep the tree more or less in center
adjustNegatives();
}
/* Plot partners for the current person */
function plotPartners(start) {
if (! start) { return; }
start.partners.forEach(function(partnerId) {
var partner = getPerson(partnerId);
// Plot node
plotNode(partner, 'partners', start);
// Plot partner connector
plotConnector(start, partner, 'partners');
});
}
/* Plot parents walking up the tree */
function plotParents(start) {
if (! start) { return; }
start.parents.reduce(function(previousId, currentId) {
var previousParent = getPerson(previousId),
currentParent = getPerson(currentId);
// Plot node
plotNode(currentParent, 'parents', start, start.parents.length);
// Plot partner connector if multiple parents
if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }
// Plot parent connector
plotConnector(start, currentParent, 'parents');
// Recurse and plot parent by walking up the tree
plotParents(currentParent);
return currentId;
}, 0);
}
/* Plot a single node */
function plotNode() {
var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],
node = get(person.id), relativeNode, element = {}, thisLevel, exists
;
if (node) { return; }
node = createNodeElement(person);
// Get the current level
thisLevel = findLevel(person.level);
if (! thisLevel) {
thisLevel = { 'level': person.level, 'top': startTop };
levelMap.push(thisLevel);
}
// Depending on relation determine position to plot at relative to current person
if (relationType == 'self') {
node.style.left = startLeft + 'px';
node.style.top = thisLevel.top + 'px';
} else {
relativeNode = get(relative.id);
}
if (relationType == 'partners') {
// Plot to the right
node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';
node.style.top = parseInt(relativeNode.style.top) + 'px';
}
if (relationType == 'children') {
// Plot below
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px';
}
if (relationType == 'parents') {
// Plot above, if single parent plot directly above else plot with an offset to left
if (numberOfParents == 1) {
node.style.left = parseInt(relativeNode.style.left) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
} else {
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
}
}
// Avoid collision moving to right
while (exists = detectCollision(node)) {
node.style.left = (exists.left + size + (gap * 2)) + 'px';
}
// Record level position
if (thisLevel.top > parseInt(node.style.top)) {
updateLevel(person.level, 'top', parseInt(node.style.top));
}
element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);
elements.push(element);
// Add the node to the DOM tree
tree.appendChild(node);
}
/* Helper Functions */
function createNodeElement(person) {
var node = document.createElement('div');
node.id = person.id;
node.classList.add('node'); node.classList.add('asset');
node.textContent = person.name;
node.setAttribute('data-level', person.level);
return node;
}
function select(selectedNode) {
var allNodes = document.querySelectorAll('div.node');
[].forEach.call(allNodes, function(node) {
node.classList.remove('selected');
});
selectedNode.classList.add('selected');
}
function get(id) { return document.getElementById(id); }
function getPerson(id) {
var element = data.filter(function(elem) {
return elem.id == id;
});
return element.pop();
}
function fillPeopleAtLevel() {
if (!selectedNode) return;
var person = getPerson(selectedNode.id), level = (person.level + 1), persons, option;
while (people.hasChildNodes()) { people.removeChild(people.lastChild); }
data.forEach(function(elem) {
if (elem.level === level) {
option = document.createElement('option');
option.value = elem.id; option.textContent = elem.name;
people.appendChild(option);
}
});
return persons;
}
function attachParent() {
var parentId = people.value, thisId = selectedNode.id;
updatePerson(thisId, 'parents', parentId);
updatePerson(parentId, 'children', thisId);
}
function addPerson(relationType) {
var newId = 'P' + (data.length < 9 ? '0' + (data.length + 1) : data.length + 1),
newPerson = new Person(newId), thisPerson;
;
thisPerson = getPerson(selectedNode.id);
// Add relation between originating person and this person
updatePerson(thisPerson.id, relationType, newId);
switch (relationType) {
case 'children':
newPerson.parents.push(thisPerson.id);
newPerson.level = thisPerson.level - 1;
break;
case 'partners':
newPerson.partners.push(thisPerson.id);
newPerson.level = thisPerson.level;
break;
case 'siblings':
newPerson.siblings.push(thisPerson.id);
newPerson.level = thisPerson.level;
// Add relation for all other relatives of originating person
newPerson = addRelation(thisPerson.id, relationType, newPerson);
break;
case 'parents':
newPerson.children.push(thisPerson.id);
newPerson.level = thisPerson.level + 1;
break;
}
data.push(newPerson);
}
function updatePerson(id, key, value) {
data.forEach(function(person) {
if (person.id === id) {
if (person[key].constructor === Array) { person[key].push(value); }
else { person[key] = value; }
}
});
}
function addRelation(id, relationType, newPerson) {
data.forEach(function(person) {
if (person[relationType].indexOf(id) != -1) {
person[relationType].push(newPerson.id);
newPerson[relationType].push(person.id);
}
});
return newPerson;
}
function findLevel(level) {
var element = levelMap.filter(function(elem) {
return elem.level == level;
});
return element.pop();
}
function updateLevel(id, key, value) {
levelMap.forEach(function(level) {
if (level.level === id) {
level[key] = value;
}
});
}
function detectCollision(node) {
var element = elements.filter(function(elem) {
var left = parseInt(node.style.left);
return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
});
return element.pop();
}
function adjustNegatives() {
var allNodes = document.querySelectorAll('div.asset'),
minTop = startTop, diff = 0;
for (var i=0; i < allNodes.length; i++) {
if (parseInt(allNodes[i].style.top) < minTop) { minTop = parseInt(allNodes[i].style.top); }
};
if (minTop < startTop) {
diff = Math.abs(minTop) + gap;
for (var i=0; i < allNodes.length; i++) {
allNodes[i].style.top = parseInt(allNodes[i].style.top) + diff + 'px';
};
}
}
function plotConnector(source, destination, relation) {
var connector = document.createElement('div'), orientation, start, stop,
x1, y1, x2, y2, length, angle, transform
;
orientation = (relation == 'partners') ? 'h' : 'v';
connector.classList.add('asset');
connector.classList.add('connector');
connector.classList.add(orientation);
start = get(source.id); stop = get(destination.id);
if (relation == 'partners') {
x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
length = (x2 - x1) + 'px';
connector.style.width = length;
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
}
if (relation == 'parents') {
x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);
length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
angle = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
transform = 'rotate(' + angle + 'deg)';
connector.style.width = length + 'px';
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
connector.style.transform = transform;
}
tree.appendChild(connector);
}
/* App Starts Here */
appInit();
startFresh();
* { box-sizing: border-box; padding: 0; margin: 0; }
html, body { width: 100vw; height: 100vh; overflow: hidden; font-family: sans-serif; font-size: 0.9em; }
#editor { float: left; width: 20vw; height: 100vh; overflow: hidden; overflow-y: scroll; border: 1px solid #ddd; }
#tree { float: left; width: 80vw; height: 100vh; overflow: auto; position: relative; }
h2 { text-align: center; margin: 12px; color: #bbb; }
fieldset { margin: 12px; padding: 8px 4px; border: 1px solid #bbb; }
legend { margin: 0px 8px; padding: 4px; }
button, input, select { padding: 4px; margin: 8px 0px; }
button { min-width: 64px; }
div.node {
width: 64px; height: 64px; line-height: 64px;
background-color: #339; color: #efefef;
font-family: sans-serif; font-size: 0.7em;
text-align: center; border-radius: 50%;
overflow: hidden; position: absolute; cursor: pointer;
}
div.connector { position: absolute; background-color: #333; z-index: -10; }
div.connector.h { height: 2px; background-color: #ddd; }
div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }
div[data-level='0'] { background-color: #933; }
div[data-level='1'], div[data-level='-1'] { background-color: #393; }
div[data-level='2'], div[data-level='-2'] { background-color: #333; }
div.node.selected { background-color: #efefef; color: #444; }
<div id="editor">
<h2 id="title">Me</h2>
<div>
<fieldset>
<legend>Change Name</legend>
<label>Name: <input id="pname" type="text" /></label>
<br /><button id="save">Ok</button>
</fieldset>
<fieldset>
<legend>Add Nodes</legend>
<label for="relation">Add: </label>
<select id="relation">
<option value="partners">Partner</option>
<option value="siblings">Sibling</option>
<option value="parents">Parent</option>
<option value="children">Child</option>
</select>
<button id="add">Ok</button><br />
<label for="relation">Add: </label>
<select id="people"></select>
<button id="addExisting">As Parent</button>
</fieldset>
<fieldset>
<legend>Misc</legend>
<button id="clear">Clear</button> <button id="sample">Load Sample</button>
<br/><button id="download">Download Data</button>
</fieldset>
<fieldset id="downloadLink"></fieldset>
</div>
</div>
<div id="tree"></div>
This is all a very crude attempt and beyond doubts an un-optimized one. What I particularly couldn't get done are:
- Getting inverted
[or]shaped horizontal connectors for parent-child relationships. - Getting the tree to be horizontally balanced. i.e. dynamically figuring out which is the heavier side and then shifting those nodes to the left.
- Getting the parent to centrally align with respect to children especially multiple children. Currently, my attempt simply pushes everything to right in order.
Hope it helps. And posting it here so that I too can refer to it when needed.
这篇关于使用深度优先搜索渲染动态创建的家庭图形，不重叠？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
