Group segments which are not overlapping and keep the good order

user_6242613 0
Viewed 146

I am trying to solve an interesting problem (I will code it in JavaScript, but doesn't really matter):

Let's say there are multiple videos as segments of few seconds on different y layers. If videos overlaps in time then the one which is in the top layer will be visible when playing all of them at the same time.

Now, I have a lot of this layers (this is the problem) I want to merge some layers when possible so at the end I will have same number of videos visually displayed in the same way, but less layers.

I will show you an image which will give a better understanding

enter image description here

In this image I took an example of 11 videos, on 11 initial layers.

For example we can see that 2 and 1 can be put on the same layer since they do not overlap and visually the videos will be displayed the same, but for instance 1 and 9 cannot be put together neighter on the 9th layer nor on 1st layer since 7 overaps and will lose the display order (z-index)

If I want to represent this in code:

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
]

And here is how can look one of possible result which will have only 5 layers but with the same display:

 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
 ]

I have thought to sort the segments by the start duration and then to create 1 layer and try to insert into it as much as possible and when not possible anymore to create a new layer... but I'm not sure how to preserve correctly the order.

So that's why I'm asking to see if there are maybe some known algorithms to do such things like merging segments while preserving order.

Thanks for your ideas.

algorithm javascript
2 Answers
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))

i guess that should do the trick

user_112811810

I noticed that you call your segments orderedSegments when in fact, they aren't. So, to remove any confusion, I decided to rename them to unOrderedSegments and then create a separate orderedSegments array that has some logic about which segments should come first.

I then wrote a little helper function isOverlapping(a, b) which looks at two segments and decides if they intersect/overlap each other or not.

Then I created a layers array that will hold each layer as a separate element (array of segments).

The logic is simple as described in the pseudo code:

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);
});

user_7361720
Related