将图节点的相对位置投影到绝对坐标

Question

我有这样的数据结构：

nodes = [
         {
          "id":0,
          "proximities":{
             "1": 12.34,
             "2": 56.78
           }, 
         {
          "id":1,
          "proximities":{
             "0": 12.34,
             "2": 90.12
           }, 
         {
          "id":2,
          "proximities":{
             "0": 56.78,
             "1": 90.12
           }, 
      ]

这是我要放置在屏幕上的节点数组。每个节点包含一组 "proximities" 到其他节点的数字距离，我想使用这些距离来计算显示节点的绝对 XY 位置。也就是说，我们希望通过算法计算布局，其中每对节点之间的距离尽可能接近数据中给定的距离。

我已将此问题标记为 d3，因为我将使用 d3 绘制图形，并且对它具有的任何内置功能感到好奇，这些功能可能会让我更轻松地完成这项工作。

也就是说，我的问题的根源更广泛：我在这里尝试做的事情有名称吗？我确定有图论方法解决这个问题，但我找不到它们，因为我不确定这个问题叫什么。我应该Google做什么？

Answer 1

这是我处理你的问题集的方法。

我的节点和它们的邻近度是这样的：

nodes = [{
  "id": 0,
  name: "cyril",
  "proximities": {
    "1": 12.34,
    "2": 56.78,
    "3": 40
  }
}, {
  "id": 1,
  name: "tia",
  "proximities": {
    "0": 12.34,
    "2": 90.12
  }
}, {
  "id": 2,
  name: "josh",
  "proximities": {
    "0": 56.78,
    "1": 90.12
  }
}, {
  "id": 3,
  name: "sim",
  "proximities": {
    "0": 40,
  }
}]

将数据集更改为 Force Layout D3 可接受的格式。

function makeNodesLinks(nodes) {

  var graph = {};
  graph.nodes = [];
  graph.links = [];
  var keys = [];

  nodes.forEach(function(d) {
    //add node
    graph.nodes.push({
      name: d.name,
      id: d.id
    });
    for (var key in d.proximities) {
      if (keys.indexOf(d.id + "-" + key)<0)//this means if link is present don't add
      {
        keys.push(d.id + "-" + key);//done to make links unique
        keys.push(key + "-" + d.id);
        //add link and value stores its approx distance.
        graph.links.push({
          source: d.id,
          target: parseInt(key),
          value: d.proximities[key]
        });
      }
    }
  });
  return graph;
}

最后在力布局中，链接之间的距离由值键决定。

  force
    .nodes(graph.nodes)
    .links(graph.links)
    .linkDistance(function(d) {
      return d.value*3;//approx distance between 2 nodes.
    })
    .start();

工作代码here.

现在，如果您不想看到链接，请更改 CSS 中的样式：将不透明度设为 0，使其不可见。

.link {
  stroke: #999;
  stroke-opacity: 0;
}

将图节点的相对位置投影到绝对坐标

Projecting relative positions of graph nodes to absolute coordinates

javascript

algorithm

graph-theory

graph

d3.js