javascript - Bagaimana untuk melaksanakan algoritma ini?

Question

Format data adalah seperti berikut:

[
  {
    "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
    }
  }
]

Penerangan keperluan:
Plot setiap data pada peta koordinat 1 hari (00:00 - 24:00),

Rajah yang mungkin adalah seperti berikut:

1 Menurut startTime和endTime data, koordinat data pada paksi Y boleh diperolehi ( dinyatakan sebagai nilai atas dan ketinggian, dilaksanakan )

.

2 Memandangkan setiap tempoh masa mungkin bersilang (sebahagian daripada tempoh masa (startTime - endTime) satu peristiwa berada dalam tempoh masa peristiwa lain, ia dipanggil persimpangan), maka peristiwa yang bersilang pada X. paksi dibahagi sama Lebar Semakin besar nilai, semakin dekat kedudukannyaX 轴上相交的事件平分X轴的宽度(表现为left和width值)
2.1.如果一个事件没有与任何事件相交，则这个事件的宽度是100%
2.2 如果相交平分的话，必须order2.3 Sesuatu peristiwa mungkin bersilang dengan acara lain, atau mungkin bersilang dengan beberapa acara lain

Soalan saya ialah bagaimana untuk melaksanakan algoritma membahagi dua lebar paksi-X dan meletakkan kedudukan kiri? Iaitu, kiri dan lebar setiap elemen bernilai algoritma

Kandungan tambahan: A dan B bersilang, B dan C bersilang, dan A dan C tidak bersilang, maka ABC juga dibahagikan sama banyak

Answer 1

Ditulis secara kasar, idea asasnya ialah

1. Isih dahulu semua tugasan dari besar ke kecil (bahagian ini ditiadakan)

2. Tekan hujung mula untuk menjana objek tugasan, dan gunakan add_one daripada objek rajah untuk menambahkannya pada rajah secara bergilir-gilir.

3. Apabila memasukkan objek, tentukan objek bertindih antara objek sedia ada, jadikan kirinya sama dengan kiri+1 objek bertindih terbesar, dan kemas kini lebar maksimum

4. Akhir sekali, gunakan kaedah is_overlap untuk mengesan acara dalam tugasan yang tidak bersilang dengan sebarang acara dan menandakannya di sebelah kiri acara ini ditetapkan kepada 0 dan lebar ditetapkan kepada 100%. selain daripada peristiwa ini, lebar ditetapkan ialah 1/max_width, kiri ditetapkan kepada 1/max_width*(kiri-1) (bahagian ini diabaikan)

Kod berikut ialah langkah 2 dan 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

Perkumpulan 2D

• Kumpulan pertama secara menegak (VGroups). Peristiwa yang mempunyai perhubungan yang bersilang dikumpulkan ke dalam kumpulan yang sama. Setiap kumpulan adalah bebas (kumpulan tidak bersilang). Algoritma pengelompokan ialah: layan setiap peristiwa sebagai nod, dan jika dua nod bersilang, satu tepi disambungkan. Dengan cara ini, graf diperoleh, dan pengelompokan adalah untuk mencari komponen bersambung graf ini. Anda boleh menggunakan algoritma seperti carian mendalam-dahulu atau carian luas-dahulu untuk mencari komponen yang disambungkan. VGroups）。凡之间有相交关系的事件分入同一组。各组之间是独立的（组间不相交）。分组算法是：将每个事件看做节点，若两个节点相交，则连一条边。这样得到一个图，分组即求此图的连通分量。可以用深度优先搜索或者广度优先搜索等算法求连通分量。

• 纵向组内再横向分组（HGroups

  Kumpulkan secara mendatar dalam kumpulan menegak (HGroups). Peristiwa yang tidak mempunyai
perhubungan persilangan antara mereka dikumpulkan ke dalam kumpulan yang sama (kumpulan tidak bersilang). Tujuan langkah ini adalah untuk memampatkan bilangan acara yang boleh dipaparkan bersebelahan dan menggunakan ruang yang tidak berpenghuni.

Dengan cara ini, selepas mengumpulkan dua dimensi secara menegak dan mendatar, adalah mudah untuk menukarnya kepada grafik.

Ujian

Dilampirkan:

Mahematica🎜 kod🎜

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
Mungkin begini