forcedirectedlayout.as

用于flash/flex的 as3的 2D图形图像图表的动态生成

package flare.vis.operator.layout
{
	import flare.animate.Transitioner;
	import flare.physics.Particle;
	import flare.physics.Simulation;
	import flare.physics.Spring;
	import flare.vis.data.Data;
	import flare.vis.data.DataSprite;
	import flare.vis.data.EdgeSprite;
	import flare.vis.data.NodeSprite;
	
	/**
	 * Layout that places nodes based on a physics simulation of
	 * interacting forces. By default, nodes repel each other, edges act as
	 * springs, and drag forces (similar to air resistance) are applied. This
	 * algorithm can be run for multiple iterations for a run-once layout
	 * computation or repeatedly run in an animated fashion for a dynamic and
	 * interactive layout (set <code>Visualization.continuousUpdates = true
	 * </code>).
	 * 
	 * <p>The running time of this layout algorithm is the greater of O(N log N)
	 * and O(E), where N is the number of nodes and E the number of edges.
	 * The addition of custom forces to the simulation may affect this.</p>
	 * 
	 * <p>The force directed layout is implemented using the physics simulator
	 * provided by the <code>flare.physics</code> package. The
	 * <code>Simulation</code> used to drive this layout can be set explicitly,
	 * allowing any number of custom force directed layouts to be created
	 * through the selection of <code>IForce</code> modules. Each node in the
	 * layout is mapped to a <code>Particle</code> instance and each edge
	 * to a <code>Spring</code> in the simulation. Once the simulation has been
	 * initialized, you can retrieve these instances through the
	 * <code>node.props.particle</code> and <code>edge.props.spring</code>
	 * properties, respectively.</p>
	 * 
	 * @see flare.physics
	 */
	public class ForceDirectedLayout extends Layout
	{
		private var _sim:Simulation;
		private var _step:Number = 1;
		private var _iter:int = 1;
		private var _gen:uint = 0;
		private var _enforceBounds:Boolean = false;
		
		// simulation defaults
		private var _mass:Number = 1;
		private var _restLength:Number = 30;
		private var _tension:Number = 0.3;
		private var _damping:Number = 0.1;
		
		/** The default mass value for node/particles. */
		public function get defaultParticleMass():Number { return _mass; }
		public function set defaultParticleMass(v:Number):void { _mass = v; }
		
		/** The default spring rest length for edge/springs. */
		public function get defaultSpringLength():Number { return _restLength; }
		public function set defaultSpringLength(v:Number):void { _restLength = v; }
		
		/** The default spring tension for edge/springs. */
		public function get defaultSpringTension():Number { return _tension; }
		public function set defaultSpringTension(v:Number):void { _tension = v; }
		
		/** The number of iterations to run the simulation per invocation
		 *  (default is 1, expecting continuous updates). */
		public function get iterations():int { return _iter; }
		public function set iterations(iter:int):void { _iter = iter; }
		
		/** The number of time ticks to advance the simulation on each
		 *  iteration (default is 1). */
		public function get ticksPerIteration():int { return _step; }
		public function set ticksPerIteration(ticks:int):void { _step = ticks; }
		
		/** The physics simulation driving this layout. */
		public function get simulation():Simulation { return _sim; }
		
		/** Flag indicating if the layout bounds should be enforced. 
		 *  If true, the layoutBounds will limit node placement. */
		public function get enforceBounds():Boolean { return _enforceBounds; }
		public function set enforceBounds(b:Boolean):void { _enforceBounds = b; }
		
		// --------------------------------------------------------------------
		
		/**
		 * Creates a new ForceDirectedLayout.
		 * @param iterations the number of iterations to run the simulation
		 *  per invocation
		 * @param sim the physics simulation to use for the layout. If null
		 *  (the default), default simulation settings will be used
		 */
		public function ForceDirectedLayout(enforceBounds:Boolean=false, 
			iterations:int=1, sim:Simulation=null)
		{
			_enforceBounds = enforceBounds;
			_iter = iterations;
			_sim = (sim==null ? new Simulation(0, 0, 0.1, -10) : sim);
		}
		
		/** @inheritDoc */
		protected override function layout():void
		{
			++_gen; // update generation counter
			init(); // populate simulation
			
			// run simulation
			_sim.bounds = _enforceBounds ? layoutBounds : null;
			for (var i:uint=0; i<_iter; ++i) {
				_sim.tick(_step);
			}
			visualization.data.nodes.visit(update); // update positions
			updateEdgePoints(_t);
		}
		
		// -- value transfer --------------------------------------------------
		
		/**
		 * Transfer the physics simulation results to an item's layout.
		 * @param d a DataSprite
		 * @return true, to signal a visitor to continue
		 */
		protected function update(d:DataSprite):void
		{
			var p:Particle = d.props.particle;
			if (!p.fixed) {
				var o:Object = _t.$(d);
				o.x = p.x;
				o.y = p.y;
			}
		}
		
		// -- simulation management -------------------------------------------
		
		/**
		 * Initializes the Simulation for this ForceDirectedLayout
		 */
		protected function init():void
		{
			var data:Data = visualization.data, o:Object;
			var p:Particle, s:Spring, n:NodeSprite, e:EdgeSprite;
			
			// initialize all simulation entries
			for each (n in data.nodes) {
				p = n.props.particle;
				o = _t.$(n);
				if (p == null) {
					n.props.particle = (p = _sim.addParticle(_mass, o.x, o.y));
					p.fixed = o.fixed;
				} else {
					p.x = o.x;
					p.y = o.y;
					p.fixed = o.fixed;
				}
				p.tag = _gen;
			}
			for each (e in data.edges) {
				s = e.props.spring;
				if (s == null) {
					e.props.spring = (s = _sim.addSpring(
						e.source.props.particle, e.target.props.particle,
						_restLength, _tension, _damping));
				}
				s.tag = _gen;
			}
			
			// set up simulation parameters
			// this needs to be kept separate from the above initialization
			// to ensure all simulation items are created first
			if (mass != null) {
				for each (n in data.nodes) {
					p = n.props.particle;
					p.mass = mass(n);
				}
			}
			for each (e in data.edges) {
				s = e.props.spring;
				if (restLength != null)
					s.restLength = restLength(e);
				if (tension != null)
					s.tension = tension(e);
				if (damping != null)
					s.damping = damping(e);
			}
			
			// clean-up unused items
			for each (p in _sim.particles)
				if (p.tag != _gen) p.kill();
			for each (s in _sim.springs)
				if (s.tag != _gen) s.kill();
		}
		
		/**
		 * Function for assigning mass values to particles. By default, this
		 * simply returns the default mass value. This function can be replaced
		 * to perform custom mass assignment.
		 */
		public var mass:Function = function(d:DataSprite):Number {
			return _mass;
		}
		
		/**
		 * Function for assigning rest length values to springs. By default,
		 * this simply returns the default rest length value. This function can
		 * be replaced to perform custom rest length assignment.
		 */
		public var restLength:Function = function(e:EdgeSprite):Number {
			return _restLength;
		}
		
		/**
		 * Function for assigning tension values to springs. By default, this
		 * method computes spring tension adaptively, based on the connectivity
		 * of the attached particles, to create more stable layouts. More
		 * specifically, the tension is computed as the default tension value
		 * divided by the square root of the maximum degree of the attached
		 * particles. This function can be replaced to perform custom tension
		 * assignment.
		 */
		public var tension:Function = function(e:EdgeSprite):Number {
			var s:Spring = Spring(e.props.spring);
			var n:Number = Math.max(s.p1.degree, s.p2.degree);
			return _tension / Math.sqrt(n);
		}
		
		/**
		 * Function for assigning damping constant values to springs. By
		 * default, this simply uses the spring's computed tension value
		 * divided by 10. This function can be replaced to perform custom
		 * damping assignment.
		 */
		public var damping:Function = function(e:EdgeSprite):Number {
			return Spring(e.props.spring).tension / 10;
		}
		
	} // end of class ForceDirectedLayout
}