How To Sort Objects? (painters Algorithm)

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. Note: The came

Solution 1:

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)

constisEmpty = arr => arr.length == 0constremoveIndex = (n, arr) => arr.slice(0, n).concat(arr.slice(n + 1))

constsortDigraph = (
  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))

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.