javascript - 如何排序对象？ (画家算法)

Question

所以我得到了 4 个矩形形状，我正在尝试应用排序算法 (painters algorithm) 来了解哪些形状(在 3d 中)我需要先绘制，哪些在后绘制。

注意:相机在右下角:

正确的顺序是:purple, red, blue, green(对于绘图当然是颠倒的顺序)。

---

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

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"},
]

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 算法的更复杂情况，那么在尝试此操作之前您将需要拆分节点。