不重叠且保持良好顺序的组段

问题描述 投票:3回答:2

我正在尝试解决一个有趣的问题(我将使用JavaScript对其进行编码,但并不重要):

比方说,在不同的y层上有几段几秒的视频片段。如果视频在时间上重叠,则当同时播放所有视频时,将显示最上层的视频。

现在,我有很多这样的图层(这是问题所在),我想尽可能合并一些图层因此最后,我将以相同的方式直观地显示相同数量的视频,但是层数更少。

我将向您展示可以更好地理解的图像

enter image description here

在此图像中,我在11个初始图层上以11个视频为例。

例如,我们可以看到2和1可以放置在同一层上,因为它们不重叠,并且视频在视觉上将显示为相同,但是例如1和9不能在第9层或第9层上更紧密地放在一起由于第7层重叠,因此第1层将失去显示顺序(z索引)

如果我想用代码表示:

const orderedSegments = [
  [15, 18],     // 1
  [0.3, 9],     // 2
  [4, 13],      // 3
  [8, 14],      // 4
  [1, 3],       // 5
  [16, 19.5],   // 6
  [4.1, 17.5],  // 7
  [0, 2.9],     // 8
  [2.9, 11],    // 9
  [12.5, 19.4], // 10
  [11.3, 12]    // 11
]

这是可能的结果之一,它只有5层,但显示相同:

 const expectedLayers = [
      [[0.3, 9], [15, 18]],                  // 2, 1
      [[1, 3], [4, 13]],                     // 5, 3
      [[8, 14], [16, 19.5]],                 // 4, 6
      [[0, 2.9], [4.1, 17.5]],               // 8, 7
      [[2.9, 11], [11.3, 12], [12.5, 19.4]]  // 9, 11, 10
 ]

我曾考虑过按开始时长对片段进行排序,然后创建1层,并尝试尽可能多地插入其中,并且在不再可能的情况下创建新层...但是我不确定如何正确保留顺序。

所以这就是为什么我要问是否有一些已知的算法来执行诸如在保留顺序的同时合并段之类的事情。

感谢您的想法。

javascript algorithm
2个回答
1
投票

我注意到您实际上并不是将细分称为orderedSegments。因此,为了消除任何混乱,我决定将它们重命名为unOrderedSegments,然后创建一个单独的orderedSegments数组,该数组具有有关哪些段应该首先出现的逻辑。

然后我写了一个小的辅助函数isOverlapping(a, b),它查看两个段并确定它们是否相交/重叠。

然后我创建了一个layers数组,该数组将把每个图层作为一个单独的元素(分段数组)。

逻辑很简单,如伪代码中所述:

loop through each `segment` in `orderedSegments`:
    loop through each `layer` in `layers`:
        check if the `segment` is overlaping any of the segments in the current `layer'
        if not then insert the `segment` to the current `layer`
        if yes, then check with the other layers
        if we reach the end of layers but could not insert it in any,
           then add the segment to its own new layer

const unOrderedSegments = [
  [15, 18], // 1
  [0.3, 9], // 2
  [4, 13], // 3
  [8, 14], // 4
  [1, 3], // 5
  [16, 19.5], // 6
  [4.1, 17.5], // 7
  [0, 2.9], // 8
  [2.9, 11], // 9
  [12.5, 19.4], // 10
  [11.3, 12], // 11
];

const orderedSegments = unOrderedSegments.sort((a, b) => a[0] - b[0]);

const isOverlapping = (a, b) => {
  const check1 = a[0] > b[0] && a[0] < b[1];
  const check2 = b[0] > a[0] && b[0] < a[1];

  return check1 || check2;
};

const layers = [];

for (let i = 0; i < orderedSegments.length; i++) {
  const currentSegment = orderedSegments[i];

  let inserted = false;

  for (let j = 0; j < layers.length; j++) {
    const currentLayer = layers[j];
    let canBeInserted = true;
    for (let k = 0; k < currentLayer.length; k++) {
      const segment = currentLayer[k];

      if (isOverlapping(segment, currentSegment)) {
        canBeInserted = false;
        break;
      }
    }
    if (canBeInserted) {
      currentLayer.push(currentSegment);
      inserted = true;
      break;
    }
  }
  if (!inserted) {
    layers.push([currentSegment]);
  }
}

// print each layer on a spearate line 
// ( convert array to string )
layers.forEach((layer) => {
  let layerString = "";
  layer.forEach((segment) => {
    layerString += `[${segment[0]}-${segment[1]}]`;
  });
  console.log(layerString);
});

0
投票
const orderedSegments = [
  [15, 18],     // 1
  [0.3, 9],     // 2
  [4, 13],      // 3
  [8, 14],      // 4
  [1, 3],       // 5
  [16, 19.5],   // 6
  [4.1, 17.5],  // 7
  [0, 2.9],     // 8
  [2.9, 11],    // 9
  [12.5, 19.4], // 10
  [11.3, 12]    // 11
]

// sort array by starting time (orderedSegments[i][0])
orderedSegments.sort((a, b) => {
  if(a[0] < b[0]) return -1;
  if(a[0] > b[0]) return 1;
  return 0;
});

const newSegments = [];
while(orderedSegments.length > 0) {
  // get first element of array
  let element = orderedSegments[0];
  // all "used" items will be removed. used items are marked with -1
  if(element[0] == -1) {
    orderedSegments.shift();
    break;
  }
  // newElementGroup represents a new layer
  let newElementGroup = [];
  newElementGroup.push(element);
  for(let i = 0; i < orderedSegments.length; i++) {
    if(orderedSegments[i][0] > element[1]) {
      element = orderedSegments[i].slice();
      newElementGroup.push(element);
      // mark element as "used"
      orderedSegments[i][0] = -1;
    }
  }
  newSegments.push(newElementGroup);
  // remove first element after creating a new layer until orderedSegments is empty
  orderedSegments.shift();
}

newSegments.forEach(element => console.info(element))

我想应该可以解决问题

© www.soinside.com 2019 - 2024. All rights reserved.