如何对物体进行排序？（画家算法）

Question

如何对物体进行排序？（画家算法）

javascriptalgorithmsortingtopological-sort

3

所以我有4个矩形，我正尝试应用排序算法(画家算法)来确定我需要先绘制哪些3D形状，然后再绘制哪些形状。

注意：相机位于右下角。

正确的顺序是：紫色、红色、蓝色、绿色(当然是反向绘制的顺序)。

所以我实现了一个算法，创建了类似于这样的东西：每个对象都列出了它的正确的后继和前驱。

ITEM:  red
  predecessor: -
  successor: -
ITEM:  green
  predecessor: -
  successor: red
ITEM:  blue
  predecessor: green
  successor: red
ITEM:  purple
  predecessor: blue, green
  successor: blue, red

我该如何根据上面的信息对项目进行排序以获得正确的顺序？非常感谢您的帮助。

let digraph = {
  red: {
    predecessor: [],
    successor: []
  },
  green: {
    predecessor: [],
    successor: ["red"]
  },
  blue: {
    predecessor: ["green"],
    successor: ["red"]
  },
  purple: {
    predecessor: ["blue", "green"],
    successor: ["blue", "red"]
  }
}

let itinerary = {}
for (let e of Object.keys(digraph)) {
  if (digraph[e].successor.length != 0) itinerary[e] = digraph[e]
}

//console.log(itinerary)
let sorted_pile = []
let overflow = 0;
while (Object.keys(itinerary).length) {
  overflow++;
  if (overflow > 40) {
    console.error("OVERFLOW");
    break;
  }
  let key = Object.keys(itinerary)[0],
    entity = itinerary[key];
  delete itinerary[key];
  sorted_pile.push(key)
  let successors = digraph[key].successor
  for (succ of successors) {
    digraph[succ].predecessor = digraph[succ].predecessor.filter(function(item) {
      return item !== key;
    })
    if (digraph[succ].predecessor.length === 0) itinerary[key] = digraph[succ]
  }
}

console.log(sorted_pile)

编辑:

let tile_entities = [
    {x: 8, y: 0, w: 1, h: 5, id: "rot"},
    {x: 5, y: 0, w: 2, h: 1, id: "gruen"},
    {x: 7, y: 0, w: 1, h: 1, id: "blau"},
    {x: 4, y: 5, w: 4, h: 2, id: "lila"},
]

- user3596335

每个对象都列出了它的正确后继和前驱 - 为什么这么复杂？为什么不按照距离摄像机的远近排序呢？ - Bergi

嘿，Bergi。感谢你的回答 - 不幸的是，这并不像你想象的那么容易（为你辩护：计算相机距离也是我的第一种方法）。问题在于对象通过它们的w/h遇到了画家算法的问题。如果你有兴趣，请看一下这个源代码，在我看来它解释了很多事情，并且也帮助了我： 1：cs.umd 2：siggraph 最好的问候 - Jonas - user3596335

1

在你的例子中，紫色既有蓝色作为前驱节点，也有蓝色作为后继节点。这是什么意思？这两个条件不能同时成立... - trincot

哦，没错 @trincot - 条件可以同时成立。我猜这取决于物体的大小和位置，不幸的是这是无法避免的。 - user3596335

很抱歉我这么愚蠢地问 - 但似乎我在数据收集中犯了一个错误。如何找出一个元素是否是前任？假设我有这些坐标：

let tile_entities = [     {x: 8, y: 0, w: 1, h: 5, id: "red"},     {x: 5, y: 0, w: 2, h: 1, id: "green"},     {x: 7, y: 0, w: 1, h: 1, id: "blue"},     {x: 4, y: 5, w: 4, h: 2, id: "purple"},   ]

- user3596335

显示剩余11条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Scott Sauyet · Answer 1

我认为这做到了你想要的，但我从你的输入开始使用改变过的版本。将它转换很容易，但你可能能够直接从你当前的流程中生成此输入。（注意不需要successor信息，因为它可以从predecessors派生出来）

const isEmpty = arr => arr.length == 0 
const removeIndex = (n, arr) => arr.slice(0, n).concat(arr.slice(n + 1))

const sortDigraph = (
  digraph, 
  sorted = [], 
  idx = digraph.findIndex(node => isEmpty(node.predecessor)),
  nodeName = (digraph[idx] || {}).name
) => isEmpty(digraph)
  ? sorted
  : sortDigraph(
    removeIndex(idx, digraph).map(({name, predecessor}) => ({
      name,
      predecessor: predecessor.filter(n => n !== nodeName)
    }), digraph),
    sorted.concat(nodeName)
  )
  
let digraph = [
  {name: 'blue', predecessor: ["green"]},
  {name: 'green', predecessor: []},
  {name: 'orange', predecessor: ["green"]},
  {name: 'purple', predecessor: ["blue", "green"]},
  {name: 'red', predecessor: ["yellow"]},
  {name: 'yellow', predecessor: ["green", "orange"]},
]

console.log(sortDigraph(digraph))

基本思路是可以从任何一个没有前置节点的节点开始，然后从其他节点中删除指向它的前置链接，并重复这个过程。只要您的图形无环，这应该很简单有效。如果您需要处理更复杂的Painter's Algorithm情况，则需要在尝试此操作之前将节点拆分。