git.mjollnir.org Git - moodle.git/blob

   1 package flare.vis.operator.layout
   2 {
   3         import flare.animate.Transitioner;
   4         import flare.util.Arrays;
   5         import flare.vis.data.NodeSprite;
   6
   7         import flash.geom.Rectangle;
   8
   9         /**
  10          * Layout that places tree nodes in a radial layout, laying out subsequent
  11          * depth levels of a tree on circles of progressively increasing radius.
  12          * This layout can be used for both node-link diagrams, where nodes are
  13          * connected by edges, and for radial space-filling ("starburst") diagrams.
  14          * To generate space-filling layouts, nodes should have their shape
  15          * property set to <code>Shapes.WEDGE</code> and the layout instance should
  16          * have the <code>useNodeSize<code> property set to false.
  17          *
  18          * <p>The algorithm used is an adaptation of a technique by Ka-Ping Yee,
  19          * Danyel Fisher, Rachna Dhamija, and Marti Hearst, published in the paper
  20          * <a href="http://citeseer.ist.psu.edu/448292.html">Animated Exploration of
  21          * Dynamic Graphs with Radial Layout</a>, InfoVis 2001. This algorithm computes
  22          * a radial layout which factors in possible variation in sizes, and maintains
  23          * both orientation and ordering constraints to facilitate smooth and
  24          * understandable transitions between layout configurations.
  25          * </p>
  26          */
  27         public class RadialTreeLayout extends Layout
  28         {
  29                 // -- Properties ------------------------------------------------------
  30
  31                 /** Property name for storing parameters for this layout. */
  32                 public static const PARAMS:String = "radialTreeLayoutParams";
  33                 /** The default radius increment between depth levels. */
  34                 public static const DEFAULT_RADIUS:int = 50;
  35
  36             private var _maxDepth:int = 0;
  37             private var _radiusInc:Number = DEFAULT_RADIUS;
  38             private var _theta1:Number = Math.PI/2;
  39             private var _theta2:Number = Math.PI/2 + 2*Math.PI;
  40             private var _sortAngles:Boolean = true;
  41             private var _setTheta:Boolean = false;
  42             private var _autoScale:Boolean = true;
  43             private var _useNodeSize:Boolean = true;
  44             private var _prevRoot:NodeSprite = null;
  45
  46                 private var _t:Transitioner;
  47
  48                 /** The radius increment between depth levels. */
  49                 public function get radiusIncrement():Number { return _radiusInc; }
  50                 public function set radiusIncrement(r:Number):void { _radiusInc = r; }
  51
  52                 /** Flag determining if nodes should be sorted by angles to help
  53                  *  maintain ordering across different spanning-tree configurations.
  54                  *  This sorting is important for understandable transitions when using
  55                  *  a radial layout of a general graph. However, it is unnecessary for
  56                  *  tree structures and increases the running time of layout. */
  57                 public function get sortAngles():Boolean { return _sortAngles; }
  58                 public function set sortAngles(b:Boolean):void { _sortAngles = b; }
  59
  60                 /** Flag indicating if the layout should automatically be scaled to
  61                  *  fit within the layout bounds. */
  62                 public function get autoScale():Boolean { return _autoScale; }
  63                 public function set autoScale(b:Boolean):void { _autoScale = b; }
  64
  65                 /** The initial angle for the radial layout. */
  66                 public function get startAngle():Number { return _theta1; }
  67                 public function set startAngle(a:Number):void {
  68                         _theta2 += a - _theta1;
  69                         _theta1 = a;
  70                         _setTheta = true;
  71                 }
  72
  73                 /** The total angular width the layout should use (2*pi by default).*/
  74                 public function get angularWidth():Number { return _theta2 - _theta1; }
  75                 public function set angularWidth(w:Number):void {
  76                         _theta2 = _theta1 + w;
  77                         _setTheta = true;
  78                 }
  79
  80                 /** Flag indicating if node's <code>size</code> property should be
  81                  *  used to determine layout spacing. If a space-filling radial
  82                  *  layout is desired, this value must be false for the layout
  83                  *  to be accurate. */
  84                 public function get useNodeSize():Boolean { return _useNodeSize; }
  85                 public function set useNodeSize(b:Boolean):void {
  86                         _useNodeSize = b;
  87                 }
  88
  89                 // -- Methods ---------------------------------------------------------
  90
  91                 /**
  92                  * Creates a new RadialTreeLayout.
  93                  * @param radius the radius increment between depth levels
  94                  * @param sortAngles flag indicating if nodes should be sorted by angle
  95                  *  to maintain node ordering across spanning-tree configurations
  96                  * @param autoScale flag indicating if the layout should automatically
  97                  *  be scaled to fit within the layout bounds
  98                  */
  99                 public function RadialTreeLayout(radius:Number=DEFAULT_RADIUS,
 100                         sortAngles:Boolean=true, autoScale:Boolean=true)
 101                 {
 102                         _radiusInc = radius;
 103                         _sortAngles = sortAngles;
 104                         _autoScale = autoScale;
 105                 }
 106
 107                 /** @inheritDoc */
 108                 public override function operate(t:Transitioner=null):void
 109                 {
 110                         _t = (t!=null ? t : Transitioner.DEFAULT);
 111
 112                         var n:NodeSprite = layoutRoot as NodeSprite;
 113                         if (n == null) { _t = null; return; }
 114                         var np:Params = params(n);
 115
 116                         // calc relative widths and maximum tree depth
 117                 // performs one pass over the tree
 118                 _maxDepth = 0;
 119                 calcAngularWidth(n, 0);
 120
 121                         if (_autoScale) setScale(layoutBounds);
 122                         if (!_setTheta) calcAngularBounds(n);
 123
 124                         // perform the layout
 125                 if (_maxDepth > 0) {
 126                         layout(n, _radiusInc, _theta1, _theta2);
 127                 } else if (n.childDegree > 0) {
 128                         n.visitTreeDepthFirst(function(n:NodeSprite):void {
 129                         _t.$(n).radius = 0;
 130                         _t.$(n).alpha = 0;
 131                         _t.$(n).mouseEnabled = false;
 132                         if (n.parentEdge != null) {
 133                                 _t.$(n.parentEdge).alpha = 0;
 134                         }
 135                 });
 136                 }
 137
 138                 // update properties of the root node
 139                 np.angle = _theta2 - _theta1;
 140                 update(n, 0, 0, np.angle, true);
 141                         updateEdgePoints();
 142                         _t = null;
 143                 }
 144
 145                 private function setScale(bounds:Rectangle):void
 146                 {
 147                 var r:Number = Math.min(bounds.width, bounds.height)/2.0;
 148                 if (_maxDepth > 0) _radiusInc = r / (_maxDepth+1);
 149             }
 150
 151             /**
 152              * Calculates the angular bounds of the layout, attempting to
 153              * preserve the angular orientation of the display across transitions.
 154              */
 155             private function calcAngularBounds(r:NodeSprite):void
 156             {
 157                 if (_prevRoot == null || r == _prevRoot)
 158                 {
 159                     _prevRoot = r; return;
 160                 }
 161
 162                 // try to find previous parent of root
 163                 var p:NodeSprite = _prevRoot, pp:NodeSprite;
 164                 while (true) {
 165                         pp = p.parentNode;
 166                     if (pp == r) {
 167                         break;
 168                     } else if (pp == null) {
 169                         _prevRoot = r;
 170                         return;
 171                     }
 172                     p = pp;
 173                 }
 174
 175                 // compute offset due to children's angular width
 176                 var dt:Number = 0;
 177
 178                 for each (var n:NodeSprite in sortedChildren(r)) {
 179                         if (n == p) break;
 180                         dt += params(n).width;
 181                 }
 182
 183                 var rw:Number = params(r).width;
 184                 var pw:Number = params(p).width;
 185                 dt = -2*Math.PI * (dt+pw/2)/rw;
 186
 187                 // set angular bounds
 188                 _theta1 = dt + Math.atan2(p.y-r.y, p.x-r.x);
 189                 _theta2 = _theta1 + 2*Math.PI;
 190                 _prevRoot = r;
 191             }
 192
 193                 /**
 194              * Computes relative measures of the angular widths of each
 195              * expanded subtree. Node diameters are taken into account
 196              * to improve space allocation for variable-sized nodes.
 197              *
 198              * This method also updates the base angle value for nodes
 199              * to ensure proper ordering of nodes.
 200              */
 201             private function calcAngularWidth(n:NodeSprite, d:int):Number
 202             {
 203                 if (d > _maxDepth) _maxDepth = d;
 204                 var aw:Number = 0, diameter:Number = 0;
 205                 if (_useNodeSize && d > 0) {
 206                         //diameter = 1;
 207                         diameter = n.expanded && n.childDegree > 0 ? 0 : _t.$(n).size;
 208                 } else if (d > 0) {
 209                         var w:Number = n.width, h:Number = n.height;
 210                         diameter = Math.sqrt(w*w+h*h)/d;
 211                         if (isNaN(diameter)) diameter = 0;
 212                 }
 213
 214                 if (n.expanded && n.childDegree > 0) {
 215                         for (var c:NodeSprite=n.firstChildNode; c!=null; c=c.nextNode)
 216                         {
 217                                 aw += calcAngularWidth(c, d+1);
 218                         }
 219                         aw = Math.max(diameter, aw);
 220                 } else {
 221                         aw = diameter;
 222                 }
 223                         params(n).width = aw;
 224                 return aw;
 225             }
 226
 227                 private static function normalize(angle:Number):Number
 228                 {
 229                 while (angle > 2*Math.PI)
 230                     angle -= 2*Math.PI;
 231                 while (angle < 0)
 232                     angle += 2*Math.PI;
 233                 return angle;
 234             }
 235
 236             private static function minDist(a1:Number, a2:Number):Number
 237             {
 238                 var d1:Number = a2 - a1;
 239                 var d2:Number = Math.abs(d1 - 2*Math.PI);
 240                 var d3:Number = Math.abs(d1 + 2*Math.PI);
 241                         var dd:Number = Math.min(d1, d2, d3);
 242
 243                 if (dd == d1) {
 244                         return a2;
 245                 } else if (dd == d2) {
 246                         return a2 - 2*Math.PI;
 247                 } else {
 248                         return a2 + 2*Math.PI;
 249                 }
 250             }
 251
 252                 private function sortedChildren(n:NodeSprite):Array
 253                 {
 254                         var cc:int = n.childDegree;
 255                         if (cc == 0) return Arrays.EMPTY;
 256                         var angles:Array = new Array(cc);
 257
 258                 if (_sortAngles) {
 259                         // update base angle for node ordering
 260                                 var base:Number = -_theta1;
 261                                 var p:NodeSprite = n.parentNode;
 262                         if (p != null) base = normalize(Math.atan2(p.y-n.y, n.x-p.x));
 263
 264                         // collect the angles
 265                         var c:NodeSprite = n.firstChildNode;
 266                         for (var i:uint=0; i<cc; ++i, c=c.nextNode) {
 267                                 angles[i] = normalize(-base + Math.atan2(c.y-n.y,n.x-c.x));
 268                         }
 269                         // get array of indices, sorted by angle
 270                         angles = angles.sort(Array.NUMERIC | Array.RETURNINDEXEDARRAY);
 271                         // switch in the actual nodes and return
 272                         for (i=0; i<cc; ++i) {
 273                                 angles[i] = n.getChildNode(angles[i]);
 274                         }
 275                     } else {
 276                         for (i=0; i<cc; ++i) {
 277                                 angles[i] = n.getChildNode(i);
 278                         }
 279                     }
 280
 281                 return angles;
 282             }
 283
 284                 /**
 285              * Compute the layout.
 286              * @param n the root of the current subtree under consideration
 287              * @param r the radius, current distance from the center
 288              * @param theta1 the start (in radians) of this subtree's angular region
 289              * @param theta2 the end (in radians) of this subtree's angular region
 290              */
 291             private function layout(n:NodeSprite, r:Number, theta1:Number, theta2:Number):void
 292             {
 293                 var dtheta:Number = (theta2-theta1);
 294                 var dtheta2:Number = dtheta / 2.0;
 295                 var width:Number = params(n).width;
 296                 var cfrac:Number, nfrac:Number = 0;
 297
 298                 for each (var c:NodeSprite in sortedChildren(n)) {
 299                         var cp:Params = params(c);
 300                     cfrac = cp.width / width;
 301                     if (c.expanded && c.childDegree > 0)
 302                     {
 303                         layout(c, r+_radiusInc, theta1 + nfrac*dtheta,
 304                                                 theta1 + (nfrac+cfrac)*dtheta);
 305                     }
 306                     else if (c.childDegree > 0)
 307                     {
 308                         var cr:Number = r + _radiusInc;
 309                         var ca:Number = theta1 + nfrac*dtheta + cfrac*dtheta2;
 310
 311                         c.visitTreeDepthFirst(function(n:NodeSprite):void {
 312                                 update(n, cr, minDist(n.angle, ca), 0, false);
 313                         });
 314                     }
 315
 316                     var a:Number = minDist(c.angle, theta1 + nfrac*dtheta + cfrac*dtheta2);
 317                     cp.angle = cfrac * dtheta;
 318                     update(c, r, a, cp.angle, true);
 319                     nfrac += cfrac;
 320                 }
 321             }
 322
 323                 private function update(n:NodeSprite, r:Number, a:Number,
 324                                                                 aw:Number, v:Boolean) : void
 325                 {
 326                         var o:Object = _t.$(n), alpha:Number = v ? 1 : 0;
 327                         o.radius = r;
 328                         o.angle = a;
 329                         o.h = r + _radiusInc/2;
 330                         o.v = r - _radiusInc/2;
 331                         o.w = aw;
 332                         o.u = a - aw/2;
 333                         o.alpha = alpha;
 334                         o.mouseEnabled = v;
 335                         if (n.parentEdge != null)
 336                                 _t.$(n.parentEdge).alpha = alpha;
 337                 }
 338
 339                 private function params(n:NodeSprite):Params
 340                 {
 341                         var p:Params = n.props[PARAMS];
 342                         if (p == null) {
 343                                 p = new Params();
 344                                 n.props[PARAMS] = p;
 345                         }
 346                         return p;
 347                 }
 348
 349         } // end of class RadialTreeLayout
 350 }
 351
 352 class Params {
 353         public var width:Number = 0;
 354         public var angle:Number = 0;
 355 }