如何排序对象? (画家算法) [英] How to sort objects? (painters algorithm)

问题描述

所以我有4个矩形，因此我尝试应用一种排序算法( painters算法)知道我需要先绘制(在3d中)哪些形状，然后再绘制哪些形状.

So I got 4 rectangular shapes and I'm trying to apply a sorting algorithm (painters algorithm) to know which shapes (in 3d) I need to draw first and which one after.

注意:相机在右下角:

正确的顺序为:紫色，红色，蓝色，绿色(用于绘制当然颠倒的顺序).

The correct order would be: purple, red, blue, green (for drawing of course reversed order).

因此，我已经实现了一种算法，该算法可以创建如下内容: 列出的每个对象都有正确的前辈和前辈.

So I've implemented an algorithm which creates something like this: Theres every object listed with it's correct successors and predecessors.

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

如何根据以上信息对商品进行排序以获取正确的订单?任何帮助将不胜感激.

How can I sort the items based on the information above to get the correct order? Any help would be really appreciated.

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

推荐答案

我认为这可以满足您的要求，但是我先从输入的更改版本开始.对其进行转换很容易，但是您可以直接从当前流程中生成此输入. (请注意，不需要successor信息，因为它是从predecessors派生的)

I think this does what you want, but I start with an altered version of your input. It's easy enough to transform it, but you might be able to generate this input directly from your current process. (Note that the successor information is not needed, since it's derivable from the 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算法的更复杂的情况，那么您将需要先分解节点，然后再尝试执行此操作.

The basic idea is that you can start with any one that has no predecessors, and then strike out any predecessor links to it from the other ones, and repeat the process. So long as your graph is acyclic, this should simply work. If you have to deal with the more complicated case of the Painter's Algorithm, then you will need to break apart your nodes before trying this.

这篇关于如何排序对象? (画家算法)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！