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 | }
|
---|
73 | private bool Init()
|
---|
74 | {
|
---|
75 | m_radiusInc = DEFAULT_RADIUS;
|
---|
76 | m_prevRoot = null;
|
---|
77 | m_theta1 = 0;
|
---|
78 | m_theta2 = m_theta1 + Math.PI * 2;
|
---|
79 |
|
---|
80 | this.Graph = this.Model as IGraph;
|
---|
81 |
|
---|
82 | if (Graph == null)
|
---|
83 | throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
|
---|
84 |
|
---|
85 | this.LayoutRoot = this.Controller.Model.LayoutRoot;//could be null if not set in the GUI
|
---|
86 | Graph.ClearSpanningTree();
|
---|
87 | Graph.MakeSpanningTree(LayoutRoot as INode);
|
---|
88 |
|
---|
89 | Pars = new Dictionary<string, Params>();
|
---|
90 | if (Graph.Nodes.Count == 0)
|
---|
91 | return false;
|
---|
92 | if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections
|
---|
93 | return false;
|
---|
94 |
|
---|
95 |
|
---|
96 | Params par;
|
---|
97 |
|
---|
98 | foreach (INode node in Graph.Nodes)
|
---|
99 | {
|
---|
100 | par = new Params();
|
---|
101 | Pars.Add(node.Uid.ToString(), par);
|
---|
102 | }
|
---|
103 | return true;
|
---|
104 | }
|
---|
105 | #endregion
|
---|
106 |
|
---|
107 | #region Methods
|
---|
108 | public void setAngularBounds(double theta, double width)
|
---|
109 | {
|
---|
110 | m_theta1 = theta;
|
---|
111 | m_theta2 = theta + width;
|
---|
112 | m_setTheta = true;
|
---|
113 | }
|
---|
114 |
|
---|
115 | private void Layout()
|
---|
116 | {
|
---|
117 |
|
---|
118 |
|
---|
119 | INode n = LayoutRoot as INode;
|
---|
120 | Params np = Pars[n.Uid.ToString()];
|
---|
121 | // calc relative widths and maximum tree depth
|
---|
122 | // performs one pass over the tree
|
---|
123 | m_maxDepth = 0;
|
---|
124 | calcAngularWidth(n, 0);
|
---|
125 |
|
---|
126 | if (m_autoScale) setScale(Bounds);
|
---|
127 | if (!m_setTheta) calcAngularBounds(n);
|
---|
128 |
|
---|
129 | // perform the layout
|
---|
130 | if (m_maxDepth > 0)
|
---|
131 | layout(n, m_radiusInc, m_theta1, m_theta2);
|
---|
132 |
|
---|
133 | // update properties of the root node
|
---|
134 | setX(n, null, m_origin.X);
|
---|
135 | setY(n, null, m_origin.Y);
|
---|
136 | np.angle = m_theta2 - m_theta1;
|
---|
137 | }
|
---|
138 |
|
---|
139 | protected void setScale(RectangleF bounds)
|
---|
140 | {
|
---|
141 | double r = Math.Min(Bounds.Width, Bounds.Height) / 2.0D;
|
---|
142 | if (m_maxDepth > 0)
|
---|
143 | m_radiusInc = 3 * (r - MARGIN) / m_maxDepth;
|
---|
144 | }
|
---|
145 | private void calcAngularBounds(INode r)
|
---|
146 | {
|
---|
147 | if (m_prevRoot == null || r == m_prevRoot) //|| !m_prevRoot.isValid()
|
---|
148 | {
|
---|
149 | m_prevRoot = r;
|
---|
150 | return;
|
---|
151 | }
|
---|
152 |
|
---|
153 | // try to find previous parent of root
|
---|
154 | INode p = m_prevRoot;
|
---|
155 | while (true)
|
---|
156 | {
|
---|
157 | INode pp = (INode)p.ParentNode;
|
---|
158 | if (pp == r)
|
---|
159 | {
|
---|
160 | break;
|
---|
161 | }
|
---|
162 | else if (pp == null)
|
---|
163 | {
|
---|
164 | m_prevRoot = r;
|
---|
165 | return;
|
---|
166 | }
|
---|
167 | p = pp;
|
---|
168 | }
|
---|
169 |
|
---|
170 | // compute offset due to children's angular width
|
---|
171 | double dt = 0;
|
---|
172 | CollectionBase<INode> iter = sortedChildren(r);
|
---|
173 | foreach (INode n in iter)
|
---|
174 | {
|
---|
175 | if (n == p) break;
|
---|
176 | dt += Pars[n.Uid.ToString()].width;
|
---|
177 | }
|
---|
178 | double rw = Pars[r.Uid.ToString()].width;
|
---|
179 | double pw = Pars[p.Uid.ToString()].width;
|
---|
180 | dt = -Math.PI * 2 * (dt + pw / 2) / rw;
|
---|
181 |
|
---|
182 | // set angular bounds
|
---|
183 | m_theta1 = dt + Math.Atan2(p.Y - r.Y, p.X - r.X);
|
---|
184 | m_theta2 = m_theta1 + Math.PI * 2;
|
---|
185 | m_prevRoot = r;
|
---|
186 | }
|
---|
187 | private double calcAngularWidth(INode n, int d)
|
---|
188 | {
|
---|
189 | if (d > m_maxDepth) m_maxDepth = d;
|
---|
190 | double aw = 0;
|
---|
191 |
|
---|
192 | RectangleF bounds = n.Rectangle;
|
---|
193 | double w = Bounds.Width, h = Bounds.Height;
|
---|
194 | double diameter = d == 0 ? 0 : Math.Sqrt(w * w + h * h) / d;
|
---|
195 |
|
---|
196 | if (n.IsExpanded && n.ChildCount > 0)
|
---|
197 | {
|
---|
198 |
|
---|
199 | foreach (INode c in n.Children)
|
---|
200 | {
|
---|
201 | aw += calcAngularWidth(c, d + 1);
|
---|
202 | }
|
---|
203 | aw = Math.Max(diameter, aw);
|
---|
204 | }
|
---|
205 | else
|
---|
206 | {
|
---|
207 | aw = diameter;
|
---|
208 | }
|
---|
209 | Pars[n.Uid.ToString()].width = aw;
|
---|
210 | return aw;
|
---|
211 | }
|
---|
212 |
|
---|
213 | private static double normalize(double angle)
|
---|
214 | {
|
---|
215 | while (angle > Math.PI * 2)
|
---|
216 | {
|
---|
217 | angle -= Math.PI * 2;
|
---|
218 | }
|
---|
219 | while (angle < 0)
|
---|
220 | {
|
---|
221 | angle += Math.PI * 2;
|
---|
222 | }
|
---|
223 | return angle;
|
---|
224 | }
|
---|
225 |
|
---|
226 | private CollectionBase<INode> sortedChildren(INode n)
|
---|
227 | {
|
---|
228 | double basevalue = 0;
|
---|
229 | // update basevalue angle for node ordering
|
---|
230 | INode p = n.ParentNode;
|
---|
231 | if (p != null)
|
---|
232 | {
|
---|
233 | basevalue = normalize(Math.Atan2(p.Y - n.Y, p.X - n.X));
|
---|
234 | }
|
---|
235 | int cc = n.ChildCount;
|
---|
236 | if (cc == 0) return null;
|
---|
237 |
|
---|
238 | INode c = (INode)n.FirstChild;
|
---|
239 |
|
---|
240 | // TODO: this is hacky and will break when filtering
|
---|
241 | // how to know that a branch is newly expanded?
|
---|
242 | // is there an alternative property we should check?
|
---|
243 | //if ( !c.isStartVisible() )
|
---|
244 | //{
|
---|
245 | // // use natural ordering for previously invisible nodes
|
---|
246 | // return n.Children;
|
---|
247 | //}
|
---|
248 |
|
---|
249 |
|
---|
250 |
|
---|
251 | double[] angle = new double[cc];
|
---|
252 | int[] idx = new int[cc];
|
---|
253 | for (int i = 0; i < cc; ++i, c = c.NextSibling)
|
---|
254 | {
|
---|
255 | idx[i] = i;
|
---|
256 | angle[i] = normalize(-basevalue + Math.Atan2(c.Y - n.Y, c.X - n.X));
|
---|
257 | }
|
---|
258 |
|
---|
259 | Array.Sort(angle, idx);//or is it the other way around
|
---|
260 | CollectionBase<INode> col = new CollectionBase<INode>();
|
---|
261 | CollectionBase<INode> children = n.Children;
|
---|
262 | for (int i = 0; i < cc; ++i)
|
---|
263 | {
|
---|
264 | col.Add(children[idx[i]]);
|
---|
265 | }
|
---|
266 | return col;
|
---|
267 |
|
---|
268 | // return iterator over sorted children
|
---|
269 | //return new Iterator() {
|
---|
270 | // int cur = 0;
|
---|
271 | // public Object next() {
|
---|
272 | // return n.getChild(idx[cur++]);
|
---|
273 | // }
|
---|
274 | // public bool hasNext() {
|
---|
275 | // return cur < idx.Length;
|
---|
276 | // }
|
---|
277 | // public void remove() {
|
---|
278 | // throw new UnsupportedOperationException();
|
---|
279 | // }
|
---|
280 | //};
|
---|
281 | }
|
---|
282 | protected void layout(INode n, double r, double theta1, double theta2)
|
---|
283 | {
|
---|
284 | double dtheta = (theta2 - theta1);
|
---|
285 | double dtheta2 = dtheta / 2.0;
|
---|
286 | double width = Pars[n.Uid.ToString()].width;
|
---|
287 | double cfrac, nfrac = 0.0;
|
---|
288 | foreach (INode c in sortedChildren(n))
|
---|
289 | {
|
---|
290 | Params cp = Pars[c.Uid.ToString()];
|
---|
291 | cfrac = cp.width / width;
|
---|
292 | if (c.IsExpanded && c.ChildCount > 0)
|
---|
293 | {
|
---|
294 | layout(c, r + m_radiusInc, theta1 + nfrac * dtheta, theta1 + (nfrac + cfrac) * dtheta);
|
---|
295 | }
|
---|
296 | setPolarLocation(c, n, r, theta1 + nfrac * dtheta + cfrac * dtheta2);
|
---|
297 | cp.angle = cfrac * dtheta;
|
---|
298 | nfrac += cfrac;
|
---|
299 | }
|
---|
300 |
|
---|
301 | }
|
---|
302 | protected void setPolarLocation(INode n, INode p, double r, double t)
|
---|
303 | {
|
---|
304 | setX(n, p, m_origin.X + r * Math.Cos(t));
|
---|
305 | setY(n, p, m_origin.Y + r * Math.Sin(t));
|
---|
306 | }
|
---|
307 | public override void Run()
|
---|
308 | {
|
---|
309 | Run(2000);
|
---|
310 | }
|
---|
311 | public override void Run(int time)
|
---|
312 | {
|
---|
313 | worker = new BackgroundWorker();
|
---|
314 | worker.DoWork += new DoWorkEventHandler(worker_DoWork);
|
---|
315 | worker.RunWorkerAsync(time);
|
---|
316 | }
|
---|
317 |
|
---|
318 | public override void Stop()
|
---|
319 | {
|
---|
320 | if (worker != null && worker.IsBusy)
|
---|
321 | worker.CancelAsync();
|
---|
322 | }
|
---|
323 |
|
---|
324 | private void worker_DoWork(object sender, DoWorkEventArgs e)
|
---|
325 | {
|
---|
326 | this.Controller.View.Suspend();
|
---|
327 | Init();
|
---|
328 | Layout();
|
---|
329 | this.Controller.View.Resume();
|
---|
330 | }
|
---|
331 |
|
---|
332 |
|
---|
333 | #endregion
|
---|
334 |
|
---|
335 | /// <summary>
|
---|
336 | /// Paramter blob to temporarily keep working data of one node.
|
---|
337 | /// </summary>
|
---|
338 | class Params
|
---|
339 | {
|
---|
340 | public double width = 0;
|
---|
341 | public double angle = 0;
|
---|
342 | public Object clone()
|
---|
343 | {
|
---|
344 | Params p = new Params();
|
---|
345 | p.width = this.width;
|
---|
346 | p.angle = this.angle;
|
---|
347 | return p;
|
---|
348 | }
|
---|
349 | }
|
---|
350 |
|
---|
351 | }
|
---|
352 |
|
---|
353 | }
|
---|