javascript - How to implement this algorithm?

Question

The data format is as follows: {code...} Requirement description: Draw 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, it can be obtained Get the coordinates of the data on the Y axis (expressed as top and height values, implemented) 2....

PHP中文网 · Answer

Written roughly, the basic idea is

First sort all tasks from large to small (this part is omitted)
Press start end to generate a task object, and use add_one of the figure object to add it to the figure in turn.
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
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

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

@saigyouyou
It might be like this