1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkTreeLayoutStrategy.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15 /*-------------------------------------------------------------------------
16 Copyright 2008 Sandia Corporation.
17 Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
18 the U.S. Government retains certain rights in this software.
19 -------------------------------------------------------------------------*/
20
21 #include "vtkTreeLayoutStrategy.h"
22
23 #include "vtkAbstractArray.h"
24 #include "vtkAdjacentVertexIterator.h"
25 #ifdef VTK_USE_BOOST
26 #include "vtkBoostBreadthFirstSearchTree.h"
27 #endif
28 #include "vtkDataArray.h"
29 #include "vtkDoubleArray.h"
30 #include "vtkIdTypeArray.h"
31 #include "vtkMath.h"
32 #include "vtkObjectFactory.h"
33 #include "vtkPointData.h"
34 #include "vtkPoints.h"
35 #include "vtkSmartPointer.h"
36 #include "vtkTransform.h"
37 #include "vtkTree.h"
38 #include "vtkTreeDFSIterator.h"
39
40 vtkStandardNewMacro(vtkTreeLayoutStrategy);
41
vtkTreeLayoutStrategy()42 vtkTreeLayoutStrategy::vtkTreeLayoutStrategy()
43 {
44 this->Angle = 90;
45 this->Radial = false;
46 this->LogSpacingValue = 1.0;
47 this->LeafSpacing = 0.9;
48 this->DistanceArrayName = NULL;
49 this->Rotation = 0.0;
50 this->ReverseEdges = false;
51 }
52
~vtkTreeLayoutStrategy()53 vtkTreeLayoutStrategy::~vtkTreeLayoutStrategy()
54 {
55 this->SetDistanceArrayName(NULL);
56 }
57
58 // Tree layout method
Layout()59 void vtkTreeLayoutStrategy::Layout()
60 {
61 // Do I have a graph to lay out? Does it have any vertices?
62 if (this->Graph == NULL || this->Graph->GetNumberOfVertices() <= 0)
63 {
64 return;
65 }
66
67 vtkTree* tree = vtkTree::SafeDownCast(this->Graph);
68 if (tree == NULL)
69 {
70 #ifdef VTK_USE_BOOST
71 // Use the BFS search tree to perform the layout
72 vtkBoostBreadthFirstSearchTree* bfs = vtkBoostBreadthFirstSearchTree::New();
73 bfs->CreateGraphVertexIdArrayOn();
74 bfs->SetReverseEdges(this->ReverseEdges);
75 bfs->SetInputData(this->Graph);
76 bfs->Update();
77 tree = vtkTree::New();
78 tree->ShallowCopy(bfs->GetOutput());
79 bfs->Delete();
80 if (tree->GetNumberOfVertices() != this->Graph->GetNumberOfVertices())
81 {
82 vtkErrorMacro("Tree layout only works on connected graphs");
83 tree->Delete();
84 return;
85 }
86 #else
87 vtkErrorMacro("Layout only works on vtkTree unless VTK_USE_BOOST is on.");
88 return;
89 #endif
90 }
91
92 vtkPoints *newPoints = vtkPoints::New();
93 newPoints->SetNumberOfPoints(tree->GetNumberOfVertices());
94
95 vtkDoubleArray *anglesArray = vtkDoubleArray::New();
96 if( this->Radial )
97 {
98 anglesArray->SetName( "subtended_angles" );
99 anglesArray->SetNumberOfComponents(2);
100 anglesArray->SetNumberOfTuples(tree->GetNumberOfVertices());
101 vtkDataSetAttributes *data = tree->GetVertexData();
102 data->AddArray(anglesArray);
103 }
104
105 // Check if the distance array is defined.
106 vtkDataArray* distanceArr = NULL;
107 if (this->DistanceArrayName != NULL)
108 {
109 vtkAbstractArray* aa = tree->GetVertexData()->
110 GetAbstractArray(this->DistanceArrayName);
111 if (!aa)
112 {
113 vtkErrorMacro("Distance array not found.");
114 return;
115 }
116 distanceArr = vtkDataArray::SafeDownCast(aa);
117 if (!distanceArr)
118 {
119 vtkErrorMacro("Distance array must be a data array.");
120 return;
121 }
122 }
123 double maxDistance = 1.0;
124 if (distanceArr)
125 {
126 maxDistance = distanceArr->GetMaxNorm();
127 }
128
129 // Count the number of leaves in the tree
130 // and get the maximum depth
131 vtkIdType leafCount = 0;
132 vtkIdType maxLevel = 0;
133 vtkIdType lastLeafLevel = 0;
134 vtkTreeDFSIterator* iter = vtkTreeDFSIterator::New();
135 iter->SetTree(tree);
136 while (iter->HasNext())
137 {
138 vtkIdType vertex = iter->Next();
139 if (tree->IsLeaf(vertex))
140 {
141 leafCount++;
142 lastLeafLevel = tree->GetLevel(vertex);
143 }
144 if (tree->GetLevel(vertex) > maxLevel)
145 {
146 maxLevel = tree->GetLevel(vertex);
147 }
148 }
149
150 // Divide the "extra spacing" between tree branches among all internal nodes.
151 // When the angle is 360, we want to divide by
152 // internalCount - 1 (taking out just the root),
153 // so that there is extra space where the tree meets itself.
154 // When the angle is lower (here we say 270 or lower),
155 // we should to divide by internalCount - lastLeafLevel,
156 // so that the tree ends exactly at the sweep angle end points.
157 // To do this, we interpolate between these values.
158 vtkIdType internalCount = tree->GetNumberOfVertices() - leafCount;
159 double alpha = (this->Angle - 270) / 90;
160 if (alpha < 0.0)
161 {
162 alpha = 0.0;
163 }
164 double internalCountInterp = alpha*(internalCount - 1) + (1.0 - alpha)*(internalCount - lastLeafLevel);
165 double internalSpacing = 0.0;
166 if (internalCountInterp != 0.0)
167 {
168 internalSpacing = (1.0 - this->LeafSpacing) / internalCountInterp;
169 }
170
171 // Divide the spacing between tree leaves among all leaf nodes.
172 // This is similar to the interpolation for internal spacing.
173 // When the angle is close to 360, we want space between the first and last leaf nodes.
174 // When the angle is lower (less than 270), we fill the full sweep angle so divide
175 // by leafCount - 1 to take out this extra space.
176 double leafCountInterp = alpha*leafCount + (1.0 - alpha)*(leafCount - 1);
177 double leafSpacing = this->LeafSpacing / leafCountInterp;
178
179 double spacing = this->LogSpacingValue;
180
181 // The distance between level L-1 and L is s^L.
182 // Thus, if s < 1 then the distance between levels gets smaller in higher levels,
183 // if s = 1 the distance remains the same, and
184 // if s > 1 the distance get larger.
185 // The height (distance from the root) of level L, then, is
186 // s + s^2 + s^3 + ... + s^L, where s is the log spacing value.
187 // The max height (used for normalization) is
188 // s + s^2 + s^3 + ... + s^maxLevel.
189 // The quick formula for computing this is
190 // sum_{i=1}^{n} s^i = (s^(n+1) - 1)/(s - 1) - 1 if s != 1
191 // = n if s == 1
192 double maxHeight = maxLevel;
193 double eps = 1e-8;
194 double diff = spacing - 1.0 > 0 ? spacing - 1.0 : 1.0 - spacing;
195 if (diff > eps)
196 {
197 maxHeight = (pow(spacing, maxLevel+1.0) - 1.0)/(spacing - 1.0) - 1.0;
198 }
199
200 vtkSmartPointer<vtkAdjacentVertexIterator> it =
201 vtkSmartPointer<vtkAdjacentVertexIterator>::New();
202 double curPlace = 0;
203 iter->SetMode(vtkTreeDFSIterator::FINISH);
204 while (iter->HasNext())
205 {
206 vtkIdType vertex = iter->Next();
207
208 double height;
209 if (distanceArr != NULL)
210 {
211 height = spacing * distanceArr->GetTuple1(vertex) / maxDistance;
212 }
213 else
214 {
215 if (diff <= eps)
216 {
217 height = tree->GetLevel(vertex)/maxHeight;
218 }
219 else
220 {
221 height = ((pow(spacing, tree->GetLevel(vertex)+1.0) - 1.0)/(spacing - 1.0) - 1.0)/maxHeight;
222 }
223 }
224
225 double x, y;
226 if (this->Radial)
227 {
228 double ang;
229 if (tree->IsLeaf(vertex))
230 {
231
232 // 1) Compute the position in the arc
233 // 2) Spin around so that the tree leaves are at
234 // the bottom and centered
235 // 3) Convert to radians
236 double angleInDegrees = curPlace * this->Angle;
237
238 angleInDegrees -= (90+this->Angle/2);
239
240 // Convert to radians
241 ang = angleInDegrees * vtkMath::Pi() / 180.0;
242
243 curPlace += leafSpacing;
244
245 //add the subtended angles to an array for possible use later...
246 double subtended_angle[2];
247 double total_arc = (curPlace*this->Angle) - (90.+this->Angle/2.) - angleInDegrees;
248 double angle1 = angleInDegrees - (total_arc/2.) + 360.;
249 double angle2 = angleInDegrees + (total_arc/2.) + 360.;
250 subtended_angle[0] = angle1;
251 subtended_angle[1] = angle2;
252 anglesArray->SetTuple( vertex, subtended_angle );
253 }
254 else
255 {
256 curPlace += internalSpacing;
257 tree->GetChildren(vertex, it);
258 double minAng = 2*vtkMath::Pi();
259 double maxAng = 0.0;
260 double angSinSum = 0.0;
261 double angCosSum = 0.0;
262 bool first = true;
263 while (it->HasNext())
264 {
265 vtkIdType child = it->Next();
266 double pt[3];
267 newPoints->GetPoint(child, pt);
268 double leafAngle = atan2(pt[1], pt[0]);
269 if (leafAngle < 0)
270 {
271 leafAngle += 2*vtkMath::Pi();
272 }
273 if (first)
274 {
275 minAng = leafAngle;
276 first = false;
277 }
278 if (!it->HasNext())
279 {
280 maxAng = leafAngle;
281 }
282 angSinSum += sin(leafAngle);
283 angCosSum += cos(leafAngle);
284 }
285 // This is how to take the average of the two angles minAng, maxAng
286 ang = atan2(sin(minAng) + sin(maxAng), cos(minAng) + cos(maxAng));
287
288 // Make sure the angle is on the same "side" as the average angle.
289 // If not, add pi to the angle. This handles some border cases.
290 double avgAng = atan2(angSinSum, angCosSum);
291 if (sin(ang)*sin(avgAng) + cos(ang)*cos(avgAng) < 0)
292 {
293 ang += vtkMath::Pi();
294 }
295
296 //add the subtended angles to an array for possible use later...
297 double subtended_angle[2];
298 double angle1 = vtkMath::DegreesFromRadians( minAng );
299 double angle2 = vtkMath::DegreesFromRadians( maxAng );
300
301 subtended_angle[0] = angle1;
302 subtended_angle[1] = angle2;
303 anglesArray->SetTuple( vertex, subtended_angle );
304 }
305 x = height * cos(ang);
306 y = height * sin(ang);
307 }
308 else
309 {
310 double width = 2.0 * tan(vtkMath::Pi()*this->Angle / 180.0 / 2.0);
311 y = -height;
312 if (tree->IsLeaf(vertex))
313 {
314 x = width * curPlace;
315 curPlace += leafSpacing;
316 }
317 else
318 {
319 curPlace += internalSpacing;
320 tree->GetChildren(vertex, it);
321 double minX = VTK_DOUBLE_MAX;
322 double maxX = VTK_DOUBLE_MIN;
323 while (it->HasNext())
324 {
325 vtkIdType child = it->Next();
326 double pt[3];
327 newPoints->GetPoint(child, pt);
328 if (pt[0] < minX)
329 {
330 minX = pt[0];
331 }
332 if (pt[0] > maxX)
333 {
334 maxX = pt[0];
335 }
336 }
337 x = (minX + maxX) / 2.0;
338 }
339 }
340 newPoints->SetPoint(vertex, x, y, 0.0);
341 }
342
343 // Rotate coordinates
344 if (this->Rotation != 0.0)
345 {
346 vtkSmartPointer<vtkTransform> t = vtkSmartPointer<vtkTransform>::New();
347 t->RotateZ(this->Rotation);
348 double x[3];
349 double y[3];
350 for (vtkIdType p = 0; p < newPoints->GetNumberOfPoints(); ++p)
351 {
352 newPoints->GetPoint(p, x);
353 t->TransformPoint(x, y);
354 newPoints->SetPoint(p, y);
355 }
356 }
357
358 // Copy coordinates back into the original graph
359 if (vtkTree::SafeDownCast(this->Graph))
360 {
361 this->Graph->SetPoints(newPoints);
362 }
363 #ifdef VTK_USE_BOOST
364 else
365 {
366 // Reorder the points based on the mapping back to graph vertex ids
367 vtkPoints* reordered = vtkPoints::New();
368 reordered->SetNumberOfPoints(newPoints->GetNumberOfPoints());
369 for (vtkIdType i = 0; i < reordered->GetNumberOfPoints(); i++)
370 {
371 reordered->SetPoint(i, 0, 0, 0);
372 }
373 vtkIdTypeArray* graphVertexIdArr = vtkIdTypeArray::SafeDownCast(
374 tree->GetVertexData()->GetAbstractArray("GraphVertexId"));
375 for (vtkIdType i = 0; i < graphVertexIdArr->GetNumberOfTuples(); i++)
376 {
377 reordered->SetPoint(graphVertexIdArr->GetValue(i), newPoints->GetPoint(i));
378 }
379 this->Graph->SetPoints(reordered);
380 tree->Delete();
381 reordered->Delete();
382 }
383 #endif
384
385 // Clean up.
386 iter->Delete();
387 newPoints->Delete();
388 anglesArray->Delete();
389 }
390
PrintSelf(ostream & os,vtkIndent indent)391 void vtkTreeLayoutStrategy::PrintSelf(ostream& os, vtkIndent indent)
392 {
393 this->Superclass::PrintSelf(os,indent);
394 os << indent << "Angle: " << this->Angle << endl;
395 os << indent << "Radial: " << (this->Radial ? "true" : "false") << endl;
396 os << indent << "LogSpacingValue: " << this->LogSpacingValue << endl;
397 os << indent << "LeafSpacing: " << this->LeafSpacing << endl;
398 os << indent << "Rotation: " << this->Rotation << endl;
399 os << indent << "DistanceArrayName: "
400 << (this->DistanceArrayName ? this->DistanceArrayName : "(null)") << endl;
401 os << indent << "ReverseEdges: " << this->ReverseEdges << endl;
402 }
403
404
405