Как сортировать объекты?(алгоритм художников) - PullRequest
Новая
       48

Как сортировать объекты?(алгоритм художников)

0 голосов
/ 28 января 2019

Итак, я получил 4 прямоугольных фигуры и пытаюсь применить алгоритм сортировки ( алгоритм рисования ), чтобы узнать, какие фигуры (в 3d) мне нужно нарисовать первыми, а какие - после.

Примечание : Камера находится в правом нижнем углу:

Правильный порядок будет: фиолетовый, красный, синий, зеленый (для рисования, конечно, в обратном порядке).

img

Итак, я реализовал алгоритм, который создает что-то вроде этого: Theres каждый объектв списке указаны правильные преемники и предшественники . 

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

1 Ответ

0 голосов
/ 28 января 2019

Я думаю, это делает то, что вы хотите, но я начну с измененной версии вашего ввода.Преобразовать его достаточно легко, но вы можете сгенерировать этот ввод непосредственно из текущего процесса.(Обратите внимание, что информация 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, то вам придется разбить ваши узлы, прежде чем пытаться это сделать.

...