javascript - このアルゴリズムを実装するにはどうすればよいですか?
ringa_lee
ringa_lee 2017-05-18 10:53:41
0
3
427

データ形式は次のとおりです:

リーリー

要件の説明:
各データを 1 日の座標マップ (00:00 ~ 24:00) にプロットし、

考えられる回路図は次のとおりです:

1. データの startTimeendTime に応じて、データの Y 軸上の座標を取得できます ( は上端と高さで表されます)実装されている値 )

2. 各期間は交差する場合があるため (あるイベントの期間の一部 (startTime - endTime) が別のイベントの期間内にあるため、これを交差と呼びます)、X 軸上の交差はイベントの幅は、交差して等分する場合、order が大きくなるほど、位置が高くなります。#2.3 イベントは、別のイベントと交差することも、他の複数のイベントと交差することもあります。

私の質問は、X 軸の幅を二等分して左に配置するアルゴリズムをどのように実装するかです。つまり、各要素の左と幅はアルゴリズムの価値があります
補足内容:AとBが交差、BとCが交差、AとCが交差しない場合、ABCも均等に分割されます

ringa_lee
ringa_lee

ringa_lee

全員に返信(3)
Ty80

大致写了一下,基本思路是

  1. 先将全部task按order从大到小排序(此部分省略)

  2. 按start end生成task对象, 使用figure对象的add_one,依次添加到figure中。

  3. 插入一个对象时,判断已有对象中与其相重叠的对象,使其left为最大的重叠对象的left+1,同时更新最大width

  4. 最后使用is_overlap方法检测tasks中的没有与任何事件相交的事件,并标记出来,这些事件left设为0,width设为100%,除了这些事件以外的事件,宽度设为1/max_width, left设为 1/max_width*(left-1) (这一部省略)

以下代码为2和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);
いいねを押す +0
某草草

二维分组

  • 先纵向分组(VGroups)。凡之间有相交关系的事件分入同一组。各组之间是独立的(组间不相交)。分组算法是:将每个事件看做节点,若两个节点相交,则连一条边。这样得到一个图,分组即求此图的连通分量。可以用深度优先搜索或者广度优先搜索等算法求连通分量。

  • 纵向组内再横向分组(HGroups)。凡之间没有相交关系的事件分入同一组(组内不相交)。这一步的作用是压缩可以并列显示的事件数,利用没有占用的空间。

这样在纵横两个维度分组后,再转换成图形就是直截了当了。

测试

附:Mahematica 代码

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}]]
いいねを押す +0
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!