javascript - How to implement this algorithm?

Question

The data format is as follows:

[
  {
    "event": {
      "id": "2013",
      "startTime": "00:57:00",
      "endTime": "07:56:00",
      "title": "list 1",
      "backgroundColor": "#f6c79f",
      "textColor": "#8c725b",
      "order": 2014
    }
  },
  {
    "event": {
      "id": "2016",
      "startTime": "00:51:59",
      "endTime": "06:57:00",
      "title": "list 2",
      "backgroundColor": "#a7bff7",
      "textColor": "#5f6d8c",
      "order": 2017
    }
  },
  {
    "event": {
      "id": "2019",
      "startTime": "00:11:00",
      "endTime": "11:35:00",
      "title": "list 3",
      "backgroundColor": "#beea91",
      "textColor": "#728c57",
      "order": 2020
    }
  },
  {
    "event": {
      "id": "2022",
      "startTime": "09:01:00",
      "endTime": "13:18:00",
      "title": "list 4",
      "backgroundColor": "#d1b1ff",
      "textColor": "#73618c",
      "order": 2023
    }
  }
]

Description of requirements:
Plot each data on a 1-day coordinate map (00:00 - 24:00),

The possible schematic diagram is as follows:

1. According to the startTime and endTime of the data, the coordinates of the data on the Y axis can be obtained ( is represented by the top and height values, which has been implemented)

2. Since each time period may intersect (part of the time period (startTime - endTime) of one event is in the time period of another event, it is called intersection), then the intersection on the X axis The width of the event bisects the If they intersect and divide equally, the larger the order must be, the higher the position 2.3 An event may intersect with another event, or may intersect with several other events

My question is how to implement the algorithm of bisecting the width of the X-axis and positioning the left? That is, the left and width of each element are worth the algorithm

Supplementary content: A and B intersect, B and C intersect, and A and C do not intersect, then ABC is also divided equally

Answer 1

Written roughly, the basic idea is

1. First sort all tasks from large to small (this part is omitted)

2. Press start end to generate a task object, and use add_one of the figure object to add it to the figure in turn.

3. When inserting an object, determine the overlapping objects among the existing objects, make its left equal to the left+1 of the largest overlapping object, and update the maximum width at the same time

4. Finally, use the is_overlap method to detect events in tasks that do not intersect with any events, and mark them. The left of these events is set to 0, and the width is set to 100%. For events other than these events, the width is set to 1/max_width, left Set to 1/max_width*(left-1) (this part is omitted)

The following code is steps 2 and 3

function task(start, end) {
    var _this = this;
    this.start = start;
    this.end = end;
    this.left = 0;
    this.width = 0;
    this.is_overlap = function (t1, t2) {
        return !((t1 < _this.start && t2 < _this.start ) || (t1 > _this.end && t2 > _this.end));
    }
}

function figure() {
    var _this = this;
    this.tasks = [];
    this.max_width = 0;
    this.add_one = function (obj) {
        var overlap = [];
        var max_left = 0;
        for(var i = 0; i < _this.tasks.length; i++) {
            if (_this.tasks[i].is_overlap(obj.start, obj.end)){
                overlap.push(_this.tasks[i]);
            }
        }
        for(var i = 0; i < overlap.length; i++) {
            max_left = Math.max(overlap[i].left, max_left);
        }
        obj.left = max_left + 1;
        _this.max_width = Math.max(obj.left, _this.max_width);
        _this.tasks.push(obj);
    }
}

var fig = new figure();
var tasks = [];
tasks[0] = new task(3, 10);
tasks[1] = new task(8, 14);
tasks[2] = new task(5, 12);
tasks[3] = new task(2, 9);
tasks[4] = new task(18, 21);
// tasks[0] = new task(9, 15);
// tasks[1] = new task(0, 22);
// tasks[2] = new task(3, 7);
// tasks[3] = new task(9, 15);

for (var i = 0; i< tasks.length; i++){
    fig.add_one(tasks[i]);
}

for (var i = 0; i< fig.tasks.length; i++){
    console.log('index: '+ i +'  left: ' + fig.tasks[i].left);
}
console.log('width :'+fig.max_width);

Answer 2

2D Grouping

• Group vertically first (VGroups). Events that have intersecting relationships are grouped into the same group. Each group is independent (the groups do not intersect). The grouping algorithm is: treat each event as a node, and if two nodes intersect, an edge is connected. In this way, a graph is obtained, and grouping is to find the connected components of this graph. You can use algorithms such as depth-first search or breadth-first search to find connected components.

• Group horizontally within vertical groups (HGroups). Events that have no intersection relationship between them are grouped into the same group (the groups do not intersect). The purpose of this step is to compress the number of events that can be displayed side by side and utilize unoccupied space.

In this way, after grouping the two dimensions vertically and horizontally, it is straightforward to convert them into graphics.

Test

Attached:

Mahematica code

renderEvents[evts_List] := 
 Map[SortBy[-#duration &] /* renderVGroup]@
  ConnectedComponents@
   RelationGraph[{e1, e2} \[Function] 
     IntervalIntersection[e1["duration"], e2["duration"]] =!= 
      Interval[], evts]

renderVGroup[evts_List] := Module[{hgs, n},
  hgs = Last@
    NestWhile[{Rest@First@#, 
       addToGroups[Last@#, First@First@#]} &, {evts, {}}, 
     First[#] != {} &];
  n = Length[hgs];
  MapIndexed[renderHGroup[#1, (First[#2] - 1)/n, 1/n] &]@hgs]

addToGroups[gs_List, e_] := Module[{p},
  p = FirstPosition[gs,
    g_ /; 
     IntervalIntersection[IntervalUnion @@ (#duration & /@ g), 
       e["duration"]] === Interval[],
    Missing["NotFound"], {1}, Heads -> False];
  If[Head[p] === Missing,
   Append[gs, {e}],
   ReplacePart[gs, First[p] -> Append[gs[[First[p]]], e]]]]

renderHGroup[evts_List, x_, w_] :=
 Map[{#["color"], 
    Rectangle[{x, Min[#["duration"]]}, {x + w, Max[#["duration"]]}], 
    Black, Text[
     Style[#["title"], 
      Medium], {x + w/2, (Max[#["duration"]] + Min[#["duration"]])/
       2}]} &, evts]

testEvents[n_] := Module[{events},
  events = 
   Table[<|"title" -> ToString[i], 
     "duration" -> Interval[{#, # + #2}] &[RandomReal[{0, 21}], 
      RandomReal[{1, 3}]], "color" -> Hue[i/n, 0.4], 
     "order" -> i|>, {i, n}];
  Graphics[{EdgeForm[Thin], renderEvents[events]}, AspectRatio -> 1, 
   GridLines -> {None, Range[24]}, 
   GridLinesStyle -> {LightGray, Dashed}, Axes -> {None, True}]]

Answer 3

@saigyouyou
It might be like this