[2768] | 1 | using System;
|
---|
| 2 | using System.Diagnostics;
|
---|
| 3 | using Netron.Diagramming.Core.Analysis;
|
---|
| 4 | using System.Drawing;
|
---|
| 5 | using System.Collections.Generic;
|
---|
| 6 | using System.Text;
|
---|
| 7 | using System.Windows.Forms;
|
---|
| 8 | using System.ComponentModel;
|
---|
| 9 |
|
---|
| 10 | namespace Netron.Diagramming.Core
|
---|
| 11 | {
|
---|
| 12 | /// <summary>
|
---|
| 13 | /// <para>TreeLayout instance that computes a radial layout, laying out subsequent
|
---|
| 14 | /// depth levels of a tree on circles of progressively increasing radius.
|
---|
| 15 | /// </para>
|
---|
| 16 | ///
|
---|
| 17 | /// <para>The algorithm used is that of Ka-Ping Yee, Danyel Fisher, Rachna Dhamija,
|
---|
| 18 | /// and Marti Hearst in their research paper
|
---|
| 19 | /// <a href="http://citeseer.ist.psu.edu/448292.html">Animated Exploration of
|
---|
| 20 | /// Dynamic Graphs with Radial Layout</a>, InfoVis 2001. This algorithm computes
|
---|
| 21 | /// a radial layout which factors in possible variation in sizes, and maintains
|
---|
| 22 | /// both orientation and ordering constraints to facilitate smooth and
|
---|
| 23 | /// understandable transitions between layout configurations.
|
---|
| 24 | /// </para>
|
---|
| 25 | /// </summary>
|
---|
| 26 | class RadialTreeLayout : TreeLayoutBase
|
---|
| 27 | {
|
---|
| 28 | #region Fields
|
---|
| 29 | public static int DEFAULT_RADIUS = 550;
|
---|
| 30 | private static int MARGIN = 30;
|
---|
| 31 |
|
---|
| 32 | protected int m_maxDepth = 0;
|
---|
| 33 | protected double m_radiusInc;
|
---|
| 34 | protected double m_theta1, m_theta2;
|
---|
| 35 | protected bool m_setTheta = false;
|
---|
| 36 | protected bool m_autoScale = true;
|
---|
| 37 |
|
---|
| 38 | protected PointF m_origin;
|
---|
| 39 | protected INode m_prevRoot;
|
---|
| 40 | private Dictionary<string, Params> Pars;
|
---|
| 41 | BackgroundWorker worker;
|
---|
| 42 | #endregion
|
---|
| 43 |
|
---|
| 44 | #region Properties
|
---|
| 45 |
|
---|
| 46 |
|
---|
| 47 | /// <summary>
|
---|
| 48 | /// Gets or sets the RadiusIncrement
|
---|
| 49 | /// </summary>
|
---|
| 50 | public double RadiusIncrement
|
---|
| 51 | {
|
---|
| 52 | get { return m_radiusInc; }
|
---|
| 53 | set { m_radiusInc = value; }
|
---|
| 54 | }
|
---|
| 55 |
|
---|
| 56 | public bool AutoScale
|
---|
| 57 | {
|
---|
| 58 | get { return m_autoScale; }
|
---|
| 59 | set { m_autoScale = value; }
|
---|
| 60 | }
|
---|
| 61 |
|
---|
| 62 | #endregion
|
---|
| 63 |
|
---|
| 64 | #region Constructor
|
---|
| 65 | ///<summary>
|
---|
| 66 | ///Default constructor
|
---|
| 67 | ///</summary>
|
---|
| 68 | public RadialTreeLayout(IController controller)
|
---|
| 69 | : base("Radial TreeLayout", controller)
|
---|
| 70 | {
|
---|
| 71 | }
|
---|
| 72 | private bool Init()
|
---|
| 73 | {
|
---|
| 74 | m_radiusInc = DEFAULT_RADIUS;
|
---|
| 75 | m_prevRoot = null;
|
---|
| 76 | m_theta1 = 0;
|
---|
| 77 | m_theta2 = m_theta1 + Math.PI * 2;
|
---|
| 78 |
|
---|
| 79 | this.Graph = this.Model as IGraph;
|
---|
| 80 |
|
---|
| 81 | if (Graph == null)
|
---|
| 82 | throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
|
---|
| 83 |
|
---|
| 84 | this.LayoutRoot = this.Controller.Model.LayoutRoot;//could be null if not set in the GUI
|
---|
| 85 | Graph.ClearSpanningTree();
|
---|
| 86 | Graph.MakeSpanningTree(LayoutRoot as INode);
|
---|
| 87 |
|
---|
| 88 | Pars = new Dictionary<string, Params>();
|
---|
| 89 | if (Graph.Nodes.Count == 0)
|
---|
| 90 | return false;
|
---|
| 91 | if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections
|
---|
| 92 | return false;
|
---|
| 93 |
|
---|
| 94 |
|
---|
| 95 | Params par;
|
---|
| 96 |
|
---|
| 97 | foreach (INode node in Graph.Nodes)
|
---|
| 98 | {
|
---|
| 99 | par = new Params();
|
---|
| 100 | Pars.Add(node.Uid.ToString(), par);
|
---|
| 101 | }
|
---|
| 102 | return true;
|
---|
| 103 | }
|
---|
| 104 | #endregion
|
---|
| 105 |
|
---|
| 106 | #region Methods
|
---|
| 107 | public void setAngularBounds(double theta, double width)
|
---|
| 108 | {
|
---|
| 109 | m_theta1 = theta;
|
---|
| 110 | m_theta2 = theta + width;
|
---|
| 111 | m_setTheta = true;
|
---|
| 112 | }
|
---|
| 113 |
|
---|
| 114 | private void Layout()
|
---|
| 115 | {
|
---|
| 116 |
|
---|
| 117 |
|
---|
| 118 | INode n = LayoutRoot as INode;
|
---|
| 119 | Params np = Pars[n.Uid.ToString()];
|
---|
| 120 | // calc relative widths and maximum tree depth
|
---|
| 121 | // performs one pass over the tree
|
---|
| 122 | m_maxDepth = 0;
|
---|
| 123 | calcAngularWidth(n, 0);
|
---|
| 124 |
|
---|
| 125 | if (m_autoScale) setScale(Bounds);
|
---|
| 126 | if (!m_setTheta) calcAngularBounds(n);
|
---|
| 127 |
|
---|
| 128 | // perform the layout
|
---|
| 129 | if (m_maxDepth > 0)
|
---|
| 130 | layout(n, m_radiusInc, m_theta1, m_theta2);
|
---|
| 131 |
|
---|
| 132 | // update properties of the root node
|
---|
| 133 | setX(n, null, m_origin.X);
|
---|
| 134 | setY(n, null, m_origin.Y);
|
---|
| 135 | np.angle = m_theta2 - m_theta1;
|
---|
| 136 | }
|
---|
| 137 |
|
---|
| 138 | protected void setScale(RectangleF bounds)
|
---|
| 139 | {
|
---|
| 140 | double r = Math.Min(Bounds.Width, Bounds.Height) / 2.0D;
|
---|
| 141 | if (m_maxDepth > 0)
|
---|
| 142 | m_radiusInc = 3 * (r - MARGIN) / m_maxDepth;
|
---|
| 143 | }
|
---|
| 144 | private void calcAngularBounds(INode r)
|
---|
| 145 | {
|
---|
| 146 | if (m_prevRoot == null || r == m_prevRoot) //|| !m_prevRoot.isValid()
|
---|
| 147 | {
|
---|
| 148 | m_prevRoot = r;
|
---|
| 149 | return;
|
---|
| 150 | }
|
---|
| 151 |
|
---|
| 152 | // try to find previous parent of root
|
---|
| 153 | INode p = m_prevRoot;
|
---|
| 154 | while (true)
|
---|
| 155 | {
|
---|
| 156 | INode pp = (INode)p.ParentNode;
|
---|
| 157 | if (pp == r)
|
---|
| 158 | {
|
---|
| 159 | break;
|
---|
| 160 | }
|
---|
| 161 | else if (pp == null)
|
---|
| 162 | {
|
---|
| 163 | m_prevRoot = r;
|
---|
| 164 | return;
|
---|
| 165 | }
|
---|
| 166 | p = pp;
|
---|
| 167 | }
|
---|
| 168 |
|
---|
| 169 | // compute offset due to children's angular width
|
---|
| 170 | double dt = 0;
|
---|
| 171 | CollectionBase<INode> iter = sortedChildren(r);
|
---|
| 172 | foreach (INode n in iter)
|
---|
| 173 | {
|
---|
| 174 | if (n == p) break;
|
---|
| 175 | dt += Pars[n.Uid.ToString()].width;
|
---|
| 176 | }
|
---|
| 177 | double rw = Pars[r.Uid.ToString()].width;
|
---|
| 178 | double pw = Pars[p.Uid.ToString()].width;
|
---|
| 179 | dt = -Math.PI * 2 * (dt + pw / 2) / rw;
|
---|
| 180 |
|
---|
| 181 | // set angular bounds
|
---|
| 182 | m_theta1 = dt + Math.Atan2(p.Y - r.Y, p.X - r.X);
|
---|
| 183 | m_theta2 = m_theta1 + Math.PI * 2;
|
---|
| 184 | m_prevRoot = r;
|
---|
| 185 | }
|
---|
| 186 | private double calcAngularWidth(INode n, int d)
|
---|
| 187 | {
|
---|
| 188 | if (d > m_maxDepth) m_maxDepth = d;
|
---|
| 189 | double aw = 0;
|
---|
| 190 |
|
---|
| 191 | RectangleF bounds = n.Rectangle;
|
---|
| 192 | double w = Bounds.Width, h = Bounds.Height;
|
---|
| 193 | double diameter = d == 0 ? 0 : Math.Sqrt(w * w + h * h) / d;
|
---|
| 194 |
|
---|
| 195 | if (n.IsExpanded && n.ChildCount > 0)
|
---|
| 196 | {
|
---|
| 197 |
|
---|
| 198 | foreach (INode c in n.Children)
|
---|
| 199 | {
|
---|
| 200 | aw += calcAngularWidth(c, d + 1);
|
---|
| 201 | }
|
---|
| 202 | aw = Math.Max(diameter, aw);
|
---|
| 203 | }
|
---|
| 204 | else
|
---|
| 205 | {
|
---|
| 206 | aw = diameter;
|
---|
| 207 | }
|
---|
| 208 | Pars[n.Uid.ToString()].width = aw;
|
---|
| 209 | return aw;
|
---|
| 210 | }
|
---|
| 211 |
|
---|
| 212 | private static double normalize(double angle)
|
---|
| 213 | {
|
---|
| 214 | while (angle > Math.PI * 2)
|
---|
| 215 | {
|
---|
| 216 | angle -= Math.PI * 2;
|
---|
| 217 | }
|
---|
| 218 | while (angle < 0)
|
---|
| 219 | {
|
---|
| 220 | angle += Math.PI * 2;
|
---|
| 221 | }
|
---|
| 222 | return angle;
|
---|
| 223 | }
|
---|
| 224 |
|
---|
| 225 | private CollectionBase<INode> sortedChildren(INode n)
|
---|
| 226 | {
|
---|
| 227 | double basevalue = 0;
|
---|
| 228 | // update basevalue angle for node ordering
|
---|
| 229 | INode p = n.ParentNode;
|
---|
| 230 | if (p != null)
|
---|
| 231 | {
|
---|
| 232 | basevalue = normalize(Math.Atan2(p.Y - n.Y, p.X - n.X));
|
---|
| 233 | }
|
---|
| 234 | int cc = n.ChildCount;
|
---|
| 235 | if (cc == 0) return null;
|
---|
| 236 |
|
---|
| 237 | INode c = (INode)n.FirstChild;
|
---|
| 238 |
|
---|
| 239 | // TODO: this is hacky and will break when filtering
|
---|
| 240 | // how to know that a branch is newly expanded?
|
---|
| 241 | // is there an alternative property we should check?
|
---|
| 242 | //if ( !c.isStartVisible() )
|
---|
| 243 | //{
|
---|
| 244 | // // use natural ordering for previously invisible nodes
|
---|
| 245 | // return n.Children;
|
---|
| 246 | //}
|
---|
| 247 |
|
---|
| 248 |
|
---|
| 249 |
|
---|
| 250 | double[] angle = new double[cc];
|
---|
| 251 | int[] idx = new int[cc];
|
---|
| 252 | for (int i = 0; i < cc; ++i, c = c.NextSibling)
|
---|
| 253 | {
|
---|
| 254 | idx[i] = i;
|
---|
| 255 | angle[i] = normalize(-basevalue + Math.Atan2(c.Y - n.Y, c.X - n.X));
|
---|
| 256 | }
|
---|
| 257 |
|
---|
| 258 | Array.Sort(angle, idx);//or is it the other way around
|
---|
| 259 | CollectionBase<INode> col = new CollectionBase<INode>();
|
---|
| 260 | CollectionBase<INode> children = n.Children;
|
---|
| 261 | for (int i = 0; i < cc; ++i)
|
---|
| 262 | {
|
---|
| 263 | col.Add(children[idx[i]]);
|
---|
| 264 | }
|
---|
| 265 | return col;
|
---|
| 266 |
|
---|
| 267 | // return iterator over sorted children
|
---|
| 268 | //return new Iterator() {
|
---|
| 269 | // int cur = 0;
|
---|
| 270 | // public Object next() {
|
---|
| 271 | // return n.getChild(idx[cur++]);
|
---|
| 272 | // }
|
---|
| 273 | // public bool hasNext() {
|
---|
| 274 | // return cur < idx.Length;
|
---|
| 275 | // }
|
---|
| 276 | // public void remove() {
|
---|
| 277 | // throw new UnsupportedOperationException();
|
---|
| 278 | // }
|
---|
| 279 | //};
|
---|
| 280 | }
|
---|
| 281 | protected void layout(INode n, double r, double theta1, double theta2)
|
---|
| 282 | {
|
---|
| 283 | double dtheta = (theta2 - theta1);
|
---|
| 284 | double dtheta2 = dtheta / 2.0;
|
---|
| 285 | double width = Pars[n.Uid.ToString()].width;
|
---|
| 286 | double cfrac, nfrac = 0.0;
|
---|
| 287 | foreach (INode c in sortedChildren(n))
|
---|
| 288 | {
|
---|
| 289 | Params cp = Pars[c.Uid.ToString()];
|
---|
| 290 | cfrac = cp.width / width;
|
---|
| 291 | if (c.IsExpanded && c.ChildCount > 0)
|
---|
| 292 | {
|
---|
| 293 | layout(c, r + m_radiusInc, theta1 + nfrac * dtheta, theta1 + (nfrac + cfrac) * dtheta);
|
---|
| 294 | }
|
---|
| 295 | setPolarLocation(c, n, r, theta1 + nfrac * dtheta + cfrac * dtheta2);
|
---|
| 296 | cp.angle = cfrac * dtheta;
|
---|
| 297 | nfrac += cfrac;
|
---|
| 298 | }
|
---|
| 299 |
|
---|
| 300 | }
|
---|
| 301 | protected void setPolarLocation(INode n, INode p, double r, double t)
|
---|
| 302 | {
|
---|
| 303 | setX(n, p, m_origin.X + r * Math.Cos(t));
|
---|
| 304 | setY(n, p, m_origin.Y + r * Math.Sin(t));
|
---|
| 305 | }
|
---|
| 306 | public override void Run()
|
---|
| 307 | {
|
---|
| 308 | Run(2000);
|
---|
| 309 | }
|
---|
| 310 | public override void Run(int time)
|
---|
| 311 | {
|
---|
| 312 | worker = new BackgroundWorker();
|
---|
| 313 | worker.DoWork += new DoWorkEventHandler(worker_DoWork);
|
---|
| 314 | worker.RunWorkerAsync(time);
|
---|
| 315 | }
|
---|
| 316 |
|
---|
| 317 | public override void Stop()
|
---|
| 318 | {
|
---|
| 319 | if (worker != null && worker.IsBusy)
|
---|
| 320 | worker.CancelAsync();
|
---|
| 321 | }
|
---|
| 322 |
|
---|
| 323 | private void worker_DoWork(object sender, DoWorkEventArgs e)
|
---|
| 324 | {
|
---|
| 325 | this.Controller.View.Suspend();
|
---|
| 326 | Init();
|
---|
| 327 | Layout();
|
---|
| 328 | this.Controller.View.Resume();
|
---|
| 329 | }
|
---|
| 330 |
|
---|
| 331 |
|
---|
| 332 | #endregion
|
---|
| 333 |
|
---|
| 334 | /// <summary>
|
---|
| 335 | /// Paramter blob to temporarily keep working data of one node.
|
---|
| 336 | /// </summary>
|
---|
| 337 | class Params
|
---|
| 338 | {
|
---|
| 339 | public double width = 0;
|
---|
| 340 | public double angle = 0;
|
---|
| 341 | public Object clone()
|
---|
| 342 | {
|
---|
| 343 | Params p = new Params();
|
---|
| 344 | p.width = this.width;
|
---|
| 345 | p.angle = this.angle;
|
---|
| 346 | return p;
|
---|
| 347 | }
|
---|
| 348 | }
|
---|
| 349 |
|
---|
| 350 | }
|
---|
| 351 |
|
---|
| 352 | }
|
---|