守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 799|回复: 1

[算法/性能优化] Force-Directed Graph Drawing(树的弹性拖拽效果)

[复制链接]
  • TA的每日心情
    擦汗
    2018-4-10 15:18
  • 签到天数: 447 天

    [LV.9]以坛为家II

    1742

    主题

    2094

    帖子

    13万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    562
    贡献
    29
    金币
    51792
    钢镚
    1422

    开源英雄守望者

    发表于 2015-7-15 14:06:44 | 显示全部楼层 |阅读模式



    1. // forked from Qwaz's Force-Directed Graph Drawing
    2. package
    3. {
    4.     import flash.display.Sprite;
    5.     import flash.events.Event;
    6.     import flash.events.MouseEvent;
    7.     import flash.geom.Point;

    8.     public class Main extends Sprite {
    9.         public static const NUM_VERTEX:int=40, NUM_EDGE:int=30;
    10.         
    11.         private var n:int, m:int;
    12.         private var dragging:int;        private var nodeList:Vector.<Node>, edgeList:Vector.<Edge>;
    13.         private var scale:Number, minX:Number, maxX:Number, minY:Number, maxY:Number, baseX:Number, baseY:Number;

    14.         public function Main(){
    15.             generateGraph(NUM_VERTEX, NUM_EDGE);

    16.             addEventListener(Event.ENTER_FRAME, enterFrameHandler);
    17.             stage.addEventListener(MouseEvent.MOUSE_DOWN, mouseDown);
    18.             stage.addEventListener(MouseEvent.MOUSE_UP, mouseUp);
    19.             stage.doubleClickEnabled = true;
    20.             stage.addEventListener(MouseEvent.DOUBLE_CLICK, doubleClicked);
    21.         }

    22.         private function enterFrameHandler(e:Event):void {
    23.             render();
    24.         }        

    25.         private function render():void {
    26.             graphics.clear();            

    27.             minX = minY = Number.MAX_VALUE;
    28.             maxX = maxY = Number.MIN_VALUE;            

    29.             var i:int, j:int;
    30.             var f:Node, s:Node, node:Node;            

    31.             var dist:Number;            

    32.             for(i=0; i<n; i++){
    33.                 f = nodeList[i];

    34.                 for(j=0; j<n; j++){
    35.                     if(i != j){
    36.                         s = nodeList[j];
    37.                         dist = (f.x-s.x)*(f.x-s.x)+(f.y-s.y)*(f.y-s.y);
    38.                         f.vx += (f.x-s.x)/dist*Node.FORCE;
    39.                         f.vy += (f.y-s.y)/dist*Node.FORCE;
    40.                     }
    41.                 }

    42.                 minX = Math.min(minX, f.x);
    43.                 maxX = Math.max(maxX, f.x);
    44.                 minY = Math.min(minY, f.y);
    45.                 maxY = Math.max(maxY, f.y);
    46.             }

    47.             var edge:Edge;

    48.             for(i=0; i<m; i++){
    49.                 edge = edgeList[i];
    50.                 f = nodeList[edge.first];
    51.                 s = nodeList[edge.second];

    52.                 dist = Math.sqrt((f.x-s.x)*(f.x-s.x)+(f.y-s.y)*(f.y-s.y));
    53.                 f.vx -= (f.x-s.x)*dist*Edge.FORCE;
    54.                 f.vy -= (f.y-s.y)*dist*Edge.FORCE;
    55.                 s.vx += (f.x-s.x)*dist*Edge.FORCE;
    56.                 s.vy += (f.y-s.y)*dist*Edge.FORCE;
    57.             }


    58.             const scaleW:Number = (stage.stageWidth-20)/(maxX-minX), scaleH:Number = (stage.stageHeight-20)/(maxY-minY);

    59.             if(scaleW < scaleH){
    60.                 scale = scaleW;
    61.                 baseX = 10;
    62.                 baseY = 10+(stage.stageHeight-20-(maxY-minY)*scale)/2;
    63.             } else {
    64.                 scale = scaleH;
    65.                 baseX = 10+(stage.stageWidth-20-(maxX-minX)*scale)/2;
    66.                 baseY = 10;
    67.             }

    68.             for(i=0; i<n; i++)
    69.                 nodeList[i].update();

    70.             var rx:Number, ry:Number;
    71.             if(dragging != -1){
    72.                 if(mouseX < baseX) rx = minX;
    73.                 else if(mouseX > baseX+(maxX-minX)*scale) rx = maxX;
    74.                 else rx = minX+(mouseX-baseX)/scale;

    75.                 if(mouseY < baseY) ry = minY;
    76.                 else if(mouseY > baseY+(maxY-minY)*scale) ry = maxY;
    77.                 else ry = minY+(mouseY-baseY)/scale;

    78.                 node = nodeList[dragging];
    79.                 node.x = rx;
    80.                 node.y = ry;
    81.                 node.vx = 0;
    82.                 node.vy = 0;
    83.             }

    84.             graphics.lineStyle(1);

    85.             for(i=0; i<m; i++){
    86.                 edge = edgeList[i];
    87.                 f = nodeList[edge.first];
    88.                 s = nodeList[edge.second];

    89.                 graphics.moveTo(getX(f), getY(f));
    90.                 graphics.lineTo(getX(s), getY(s));
    91.             }

    92.             graphics.lineStyle();
    93.             graphics.beginFill(0x0000FF);

    94.             for(i=0; i<n; i++){
    95.                 node = nodeList[i];
    96.                 graphics.drawCircle(getX(node), getY(node), Node.NODE_RADIUS);
    97.             }
    98.         }

    99.         private function getX(node:Node):Number {
    100.             return baseX+(node.x-minX)*scale;
    101.         }

    102.         private function getY(node:Node):Number {
    103.             return baseY+(node.y-minY)*scale;
    104.         }

    105.         private function mouseDown(e:MouseEvent):void {
    106.             var i:int;
    107.             for(i=0; i<n; i++){
    108.                 if(Point.distance(new Point(stage.mouseX, stage.mouseY), new Point(getX(nodeList[i]), getY(nodeList[i]))) < Node.NODE_RADIUS*5){
    109.                     dragging = i;
    110.                     break;
    111.                 }
    112.             }
    113.         }

    114.         private function mouseUp(e:MouseEvent):void {
    115.             dragging = -1;
    116.         }
    117.         
    118.         private function doubleClicked(e:MouseEvent):void {
    119.             generateGraph(NUM_VERTEX, NUM_EDGE);
    120.         }


    121.         private function generateGraph(numNode:int, numEdge:int):void {
    122.             n = numNode;
    123.             m = numEdge;

    124.             dragging = -1;

    125.             nodeList = new Vector.<Node>;
    126.             edgeList = new Vector.<Edge>;

    127.             if(m > n*(n-1)/2)
    128.                 m = n*(n-1)/2;
    129.             else if(m < n-1)
    130.                 m = n-1;

    131.             var i:int;
    132.             for(i=0; i<n; i++)
    133.                 nodeList.push(new Node(Math.random(), Math.random()));

    134.             var edge:Edge;
    135.             var edgeDict:Object = {};

    136.             for(i=1; i<n; i++){
    137.                 var num:int = random(0, i);
    138.                 edge = new Edge(num, i);
    139.                 edgeList.push(edge);
    140.                 edgeDict[edge.hash()] = 1;
    141.             }

    142.             for(i=0; i<m-n+1; i++){
    143.                 do {
    144.                     edge = new Edge(random(0, n), random(0, n));
    145.                 } while(edge.first == edge.second || edge.hash() in edgeDict);

    146.                 edgeList.push(edge);
    147.                 edgeDict[edge.hash()] = 1;
    148.             }
    149.         }
    150.     }
    151. }

    152. class Edge {
    153.     public var first:uint, second:uint;
    154.     public static const FORCE:Number = 0.01;

    155.     public function Edge(first:uint, second:uint){
    156.         this.first = first;
    157.         this.second = second;
    158.     }

    159.     public function hash():String {
    160.         return "graph.Edge min:"+Math.min(first, second)+" max:"+Math.max(first, second);
    161.     }
    162. }

    163. class Node {
    164.     public var x:Number, y:Number, vx:Number, vy:Number;
    165.     public static const MIN_LIMIT:Number = 0.000001, NODE_RADIUS:Number = 3;
    166.     public static const FORCE:Number = 0.0001, FRICTION:Number = 0.96;

    167.     public function Node(x:Number, y:Number){
    168.         this.x = x;
    169.         this.y = y;

    170.         vx = 0;
    171.         vy = 0;
    172.     }
    173.         
    174.     public function update():void {
    175.         vx *= FRICTION;
    176.         vy *= FRICTION;

    177.         if(Math.abs(vx) < MIN_LIMIT) vx = 0;
    178.         if(Math.abs(vy) < MIN_LIMIT) vy = 0;

    179.         x += vx;
    180.         y += vy;
    181.     }
    182. }

    183. function random(start:int, end:int):int {
    184.     if(end < start) throw new ArgumentError("End must be bigger than start");

    185.     return Math.random()*(end-start)+start;
    186. }
    复制代码






    本文来自:http://wonderfl.net/c/4Xpp

    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

  • TA的每日心情
    开心
    2019-2-24 01:34
  • 签到天数: 3 天

    [LV.2]偶尔看看I

    0

    主题

    38

    帖子

    868

    积分

    上士

    Rank: 5Rank: 5

    威望
    20
    贡献
    0
    金币
    14
    钢镚
    0
    发表于 2019-2-24 02:28:09 | 显示全部楼层
    感谢分享!~
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2019-11-20 16:43 , Processed in 0.054182 second(s), 33 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表