1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkStackedTreeLayoutStrategy.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 "vtkStackedTreeLayoutStrategy.h"
22
23 #include "vtkCellArray.h"
24 #include "vtkCellData.h"
25 #include "vtkDoubleArray.h"
26 #include "vtkMath.h"
27 #include "vtkInformation.h"
28 #include "vtkInformationVector.h"
29 #include "vtkObjectFactory.h"
30 #include "vtkPoints.h"
31 #include "vtkPointData.h"
32 #include "vtkFloatArray.h"
33 #include "vtkDataArray.h"
34 #include "vtkIntArray.h"
35 #include "vtkTree.h"
36 #include "vtkTreeDFSIterator.h"
37 #include "vtkTreeLevelsFilter.h"
38
39 #include "vtkSmartPointer.h"
40 #define VTK_CREATE(type, name) \
41 vtkSmartPointer<type> name = vtkSmartPointer<type>::New()
42
43 vtkStandardNewMacro(vtkStackedTreeLayoutStrategy);
44
vtkStackedTreeLayoutStrategy()45 vtkStackedTreeLayoutStrategy::vtkStackedTreeLayoutStrategy()
46 {
47 this->InteriorRadius = 6.0;
48 this->RingThickness = 1.0;
49 this->RootStartAngle = 0.;
50 this->RootEndAngle = 360.;
51 this->UseRectangularCoordinates = false;
52 this->Reverse = false;
53 this->InteriorLogSpacingValue = 1.0;
54 }
55
~vtkStackedTreeLayoutStrategy()56 vtkStackedTreeLayoutStrategy::~vtkStackedTreeLayoutStrategy()
57 {
58 }
59
PrintSelf(ostream & os,vtkIndent indent)60 void vtkStackedTreeLayoutStrategy::PrintSelf(ostream& os, vtkIndent indent)
61 {
62 this->Superclass::PrintSelf(os,indent);
63 os << indent << "InteriorRadius: " << this->InteriorRadius << endl;
64 os << indent << "RingThickness: " << this->RingThickness << endl;
65 os << indent << "RootStartAngle: " << this->RootStartAngle << endl;
66 os << indent << "RootEndAngle: " << this->RootEndAngle << endl;
67 os << indent << "UseRectangularCoordinates: " << this->UseRectangularCoordinates << endl;
68 os << indent << "Reverse: " << this->Reverse << endl;
69 os << indent << "InteriorLogSpacingValue: " << this->InteriorLogSpacingValue << endl;
70 }
71
Layout(vtkTree * inputTree,vtkDataArray * coordsArray,vtkDataArray * sizeArray)72 void vtkStackedTreeLayoutStrategy::Layout(vtkTree* inputTree,
73 vtkDataArray* coordsArray,
74 vtkDataArray* sizeArray)
75 {
76 if( !inputTree || inputTree->GetNumberOfVertices() == 0 )
77 {
78 return;
79 }
80 if (!coordsArray)
81 {
82 vtkErrorMacro("Area array not defined.");
83 return;
84 }
85
86 vtkDataSetAttributes* data = inputTree->GetVertexData();
87
88 VTK_CREATE(vtkDoubleArray, textRotationArray);
89 textRotationArray->SetName( "TextRotation" );
90 textRotationArray->SetNumberOfComponents(1);
91 textRotationArray->SetNumberOfTuples(inputTree->GetNumberOfVertices());
92 data->AddArray( textRotationArray );
93
94 VTK_CREATE(vtkDoubleArray, textBoundedSizeArray);
95 textBoundedSizeArray->SetName( "TextBoundedSize" );
96 textBoundedSizeArray->SetNumberOfComponents(2);
97 textBoundedSizeArray->SetNumberOfTuples(inputTree->GetNumberOfVertices());
98 data->AddArray( textBoundedSizeArray );
99
100 double outer_radius = 0.0;
101 if (this->Reverse)
102 {
103 VTK_CREATE(vtkTreeLevelsFilter, levelFilter);
104 VTK_CREATE(vtkTree, newTree);
105 newTree->ShallowCopy( inputTree );
106 levelFilter->SetInputData( newTree );
107 levelFilter->Update();
108 vtkTree* levelTree = levelFilter->GetOutput();
109
110 vtkIntArray *levelArray = vtkIntArray::SafeDownCast(
111 levelTree->GetVertexData()->GetAbstractArray("level"));
112 int max_level = 0;
113 for( int i = 0; i < levelTree->GetNumberOfVertices(); i++ )
114 {
115 int level = levelArray->GetValue(i);
116 if( level > max_level )
117 {
118 max_level = level;
119 }
120 }
121 outer_radius = max_level*this->RingThickness + this->InteriorRadius;
122 }
123
124 // Get the root vertex and set it
125 vtkIdType rootId = inputTree->GetRoot();
126 float coords[4] = {this->RootStartAngle, this->RootEndAngle, 0.0, 0.0};
127 if (this->Reverse)
128 {
129 coords[2] = outer_radius - this->RingThickness;
130 coords[3] = outer_radius;
131 }
132 else
133 {
134 coords[3] = this->InteriorRadius;
135 }
136 coordsArray->SetTuple(rootId, coords);
137
138 // Now layout the children vertices
139 this->LayoutChildren(inputTree, coordsArray, sizeArray,
140 inputTree->GetNumberOfChildren(rootId),
141 rootId, 0, coords[2], coords[3], coords[0], coords[1]);
142
143 vtkPoints* points = vtkPoints::New();
144 vtkIdType numVerts = inputTree->GetNumberOfVertices();
145 points->SetNumberOfPoints(numVerts);
146 for( vtkIdType i = 0; i < numVerts; i++ )
147 {
148 double sector_coords[4];
149 coordsArray->GetTuple( i, sector_coords );
150 double x, y, z;
151 if( this->UseRectangularCoordinates )
152 {
153 x = 0.5*(sector_coords[0] + sector_coords[1]);
154 y = 0.5*(sector_coords[2] + sector_coords[3]);
155 z = 0.;
156
157 textRotationArray->SetValue( i, 0 );
158 textBoundedSizeArray->SetValue( 2*i, sector_coords[1] - sector_coords[0]);
159 textBoundedSizeArray->SetValue( 2*i + 1, sector_coords[3] - sector_coords[2] );
160 }
161 else
162 {
163 if( i == rootId )
164 {
165 x = y = z = 0.;
166
167 textRotationArray->SetValue( i, 0 );
168 textBoundedSizeArray->SetValue( 2*i, 0 );
169 textBoundedSizeArray->SetValue( 2*i + 1, 0 );
170 }
171 else
172 {
173 double r = (0.5*(sector_coords[3] - sector_coords[2])) + sector_coords[2];
174 double theta = sector_coords[0] + (0.5*(sector_coords[1]-sector_coords[0]));
175 x = r * cos( vtkMath::RadiansFromDegrees( theta ) );
176 y = r * sin( vtkMath::RadiansFromDegrees( theta ) );
177 z = 0.;
178
179 double sector_arc_length = r * vtkMath::RadiansFromDegrees(sector_coords[1] - sector_coords[0]);
180 double radial_arc_length = sector_coords[3] - sector_coords[2];
181 double aspect_ratio = sector_arc_length / radial_arc_length;
182 if( aspect_ratio > 1 )
183 {
184 //sector length is greater than radial length;
185 // align text with the sector
186 if( theta > 0. && theta < 180. )
187 {
188 textRotationArray->SetValue( i, theta - 90. );
189 }
190 else
191 {
192 textRotationArray->SetValue( i, theta + 90. );
193 }
194 textBoundedSizeArray->SetValue( 2*i, sector_arc_length );
195 textBoundedSizeArray->SetValue( 2*i + 1, radial_arc_length );
196 }
197 else
198 {
199 //radial length is greater than sector length;
200 // align text radially...
201 if( theta > 90. && theta < 270. )
202 {
203 textRotationArray->SetValue( i, theta - 180. );
204 }
205 else
206 {
207 textRotationArray->SetValue( i, theta );
208 }
209 textBoundedSizeArray->SetValue( 2*i, radial_arc_length );
210 textBoundedSizeArray->SetValue( 2*i + 1, sector_arc_length );
211 }
212 }
213 }
214 points->SetPoint(i, x, y, z);
215 }
216 inputTree->SetPoints(points);
217 points->Delete();
218 }
219
LayoutEdgePoints(vtkTree * inputTree,vtkDataArray * sectorsArray,vtkDataArray * vtkNotUsed (sizeArray),vtkTree * outputTree)220 void vtkStackedTreeLayoutStrategy::LayoutEdgePoints(
221 vtkTree* inputTree,
222 vtkDataArray* sectorsArray,
223 vtkDataArray* vtkNotUsed(sizeArray),
224 vtkTree* outputTree)
225 {
226 VTK_CREATE(vtkTreeLevelsFilter, levelFilter);
227 VTK_CREATE(vtkTree, newTree);
228 newTree->ShallowCopy( inputTree );
229 levelFilter->SetInputData( newTree );
230 levelFilter->Update();
231 vtkTree* levelTree = levelFilter->GetOutput();
232 outputTree->ShallowCopy( levelTree );
233
234 vtkIntArray* levelArray = vtkIntArray::SafeDownCast(
235 levelTree->GetVertexData()->GetAbstractArray("level"));
236
237 double exteriorRadius = VTK_DOUBLE_MAX;
238 double sector_coords[4];
239 int max_level = 0;
240 for( int i = 0; i < outputTree->GetNumberOfVertices(); i++ )
241 {
242 int level = levelArray->GetValue(i);
243 if( level > max_level )
244 {
245 max_level = level;
246 }
247 if (inputTree->IsLeaf(i))
248 {
249 sectorsArray->GetTuple( i, sector_coords );
250 if (sector_coords[2] < exteriorRadius)
251 {
252 exteriorRadius = sector_coords[2];
253 }
254 }
255 }
256
257 double spacing = this->InteriorLogSpacingValue;
258
259 // The distance between level L-1 and L is s^L.
260 // Thus, if s < 1 then the distance between levels gets smaller in higher levels,
261 // if s = 1 the distance remains the same, and
262 // if s > 1 the distance get larger.
263 // The height (distance from the root) of level L, then, is
264 // s + s^2 + s^3 + ... + s^L, where s is the log spacing value.
265 // The max height (used for normalization) is
266 // s + s^2 + s^3 + ... + s^maxLevel.
267 // The quick formula for computing this is
268 // sum_{i=1}^{n} s^i = (s^(n+1) - 1)/(s - 1) - 1 if s != 1
269 // = n if s == 1
270 double maxHeight = max_level;
271 double eps = 1e-8;
272 double diff = spacing - 1.0 > 0 ? spacing - 1.0 : 1.0 - spacing;
273 if (diff > eps)
274 {
275 maxHeight = (pow(spacing, max_level+1.0) - 1.0)/(spacing - 1.0) - 1.0;
276 }
277
278 vtkPoints* points = vtkPoints::New();
279 vtkIdType rootId = outputTree->GetRoot();
280 vtkIdType numVerts = outputTree->GetNumberOfVertices();
281 points->SetNumberOfPoints(numVerts);
282 for( vtkIdType i = 0; i < numVerts; i++ )
283 {
284 if( !this->UseRectangularCoordinates && i == rootId )
285 {
286 points->SetPoint( i, 0, 0, 0 );
287 continue;
288 }
289
290 sectorsArray->GetTuple( i, sector_coords );
291
292 double x = 0.0;
293 double y = 0.0;
294 double z = 0.0;
295 if( this->UseRectangularCoordinates )
296 {
297 if( inputTree->IsLeaf(i) )
298 {
299 if( this->Reverse )
300 {
301 y = sector_coords[2];
302 }
303 else
304 {
305 y = sector_coords[3];
306 }
307 }
308 else
309 {
310 if( this->Reverse )
311 {
312 y = this->InteriorRadius - this->RingThickness*(maxHeight + maxHeight - inputTree->GetLevel(i));
313 }
314 else
315 {
316 y = this->InteriorRadius + this->RingThickness*(maxHeight + maxHeight - inputTree->GetLevel(i));
317 }
318 }
319 x = 0.5*(sector_coords[0] + sector_coords[1]);
320 z = 0.;
321 }
322 else
323 {
324 double r;
325 if( inputTree->IsLeaf(i) )
326 {
327 r = sector_coords[2];
328 }
329 else
330 {
331 if (diff <= eps)
332 {
333 r = outputTree->GetLevel(i)/maxHeight;
334 }
335 else
336 {
337 r = ((pow(spacing, outputTree->GetLevel(i)+1.0) - 1.0)/(spacing - 1.0) - 1.0)/maxHeight;
338 }
339 // scale the spacing value based on the radius of the
340 // circle we have to work with...
341 r *= exteriorRadius;
342 }
343
344 double theta = sector_coords[0] + (0.5*(sector_coords[1]-sector_coords[0]));
345 x = r * cos( vtkMath::RadiansFromDegrees( theta ) );
346 y = r * sin( vtkMath::RadiansFromDegrees( theta ) );
347 z = 0.;
348 }
349 points->SetPoint(i, x, y, z);
350 }
351 outputTree->SetPoints(points);
352 points->Delete();
353 }
354
LayoutChildren(vtkTree * tree,vtkDataArray * coordsArray,vtkDataArray * sizeArray,vtkIdType nchildren,vtkIdType parent,vtkIdType begin,float parentInnerRad,float parentOuterRad,float parentStartAng,float parentEndAng)355 void vtkStackedTreeLayoutStrategy::LayoutChildren(
356 vtkTree *tree, vtkDataArray *coordsArray, vtkDataArray *sizeArray,
357 vtkIdType nchildren, vtkIdType parent, vtkIdType begin,
358 float parentInnerRad, float parentOuterRad,
359 float parentStartAng, float parentEndAng)
360 {
361 double new_interior_rad = 0.0;
362 double new_outer_rad = 0.0;
363 if (this->Reverse)
364 {
365 new_interior_rad = parentInnerRad - this->RingThickness;
366 new_outer_rad = parentInnerRad;
367 }
368 else
369 {
370 new_interior_rad = parentOuterRad;
371 new_outer_rad = new_interior_rad + this->RingThickness;
372 }
373 //FIXME - we may want to do this instead...
374 //double new_outer_rad = new_interior_rad +this->RingThickness[level];
375
376 double radial_spacing = this->ShrinkPercentage * this->RingThickness;
377 new_outer_rad -= radial_spacing;
378 //new_interior_rad += 0.5*radial_spacing;
379
380 //now calculate the width of each of the sectors for each vertex
381 // first calculate the total summed weight for each of the children vertices
382 double total_weighted_sum = 0;
383 vtkIdType i;
384 for( i = begin; i < nchildren; i++)
385 {
386 if (sizeArray)
387 {
388 total_weighted_sum +=
389 static_cast<float>(sizeArray->GetTuple1(tree->GetChild(parent, i)));
390 }
391 else
392 {
393 total_weighted_sum += 1.0;
394 }
395 }
396
397 // If we are doing radial layout, put extra space on the full rings
398 // so the first and last children don't butt up against each other.
399 vtkIdType num_spaces = nchildren - 1;
400 double parent_angle = parentEndAng - parentStartAng;
401 if (!this->UseRectangularCoordinates && parent_angle == 360.0)
402 {
403 num_spaces = nchildren;
404 }
405 double available_angle = parent_angle;
406 double conversion = vtkMath::Pi()/180.0;
407 double spacing = 0.0;
408 if (nchildren > 1)
409 {
410 double parent_length;
411 if (this->UseRectangularCoordinates)
412 {
413 parent_length = parent_angle;
414 }
415 else
416 {
417 parent_length = conversion * parent_angle * new_outer_rad;
418 }
419 double spacing_length;
420 if (radial_spacing * num_spaces > 0.25 * parent_length)
421 {
422 spacing_length = 0.25 * parent_length;
423 }
424 else
425 {
426 spacing_length = radial_spacing * num_spaces;
427 }
428 double total_space;
429 if (this->UseRectangularCoordinates)
430 {
431 total_space = spacing_length;
432 }
433 else
434 {
435 total_space = spacing_length / new_outer_rad / conversion;
436 }
437 spacing = total_space / num_spaces;
438 available_angle -= total_space;
439 }
440
441 float coords[4];
442 double current_angle = parentStartAng;
443 for( i = begin; i < nchildren; i++)
444 {
445 int id = tree->GetChild(parent, i);
446 float cur_size = 1.0;
447 if (sizeArray)
448 {
449 cur_size = static_cast<float>(sizeArray->GetTuple1(id));
450 }
451 double this_arc = available_angle *
452 ( cur_size / total_weighted_sum );
453
454 coords[2] = new_interior_rad;
455 coords[3] = new_outer_rad;
456 coords[0] = current_angle;
457 coords[1] = current_angle + this_arc;
458
459 coordsArray->SetTuple(id, coords);
460
461 current_angle += this_arc + spacing;
462
463 vtkIdType numNewChildren = tree->GetNumberOfChildren(id);
464 if (numNewChildren > 0)
465 {
466 this->LayoutChildren(tree, coordsArray, sizeArray, numNewChildren, id, 0,
467 coords[2], coords[3], coords[0], coords[1]);
468 }
469 }
470 }
471
FindVertex(vtkTree * otree,vtkDataArray * array,float pnt[2])472 vtkIdType vtkStackedTreeLayoutStrategy::FindVertex(
473 vtkTree* otree,
474 vtkDataArray* array,
475 float pnt[2])
476 {
477 if (this->UseRectangularCoordinates)
478 {
479 float blimits[4];
480 vtkIdType vertex = otree->GetRoot();
481 if(vertex < 0)
482 {
483 return vertex;
484 }
485 vtkFloatArray *boundsInfo = vtkFloatArray::SafeDownCast(array);
486
487 // Now try to find the vertex that contains the point
488 boundsInfo->GetTupleValue(vertex, blimits); // Get the extents of the root
489 if( ((pnt[1] > blimits[2]) && (pnt[1] < blimits[3])) &&
490 ((pnt[0] > blimits[0]) && (pnt[0] < blimits[1])) )
491 {
492 // Point is at the root vertex.
493 return vertex;
494 }
495
496 // Now traverse the children to try and find
497 // the vertex that contains the point
498 vtkIdType child;
499 VTK_CREATE(vtkTreeDFSIterator, it);
500 it->SetTree( otree );
501 it->SetStartVertex( vertex );
502
503 while (it->HasNext())
504 {
505 child = it->Next();
506 boundsInfo->GetTupleValue(child, blimits); // Get the extents of the child
507 bool beyond_radial_bounds = false;
508 bool beyond_angle_bounds = false;
509 if( (pnt[1] < blimits[2]) || (pnt[1] > blimits[3]))
510 beyond_radial_bounds = true;
511 if( (pnt[0] < blimits[0]) || (pnt[0] > blimits[1]))
512 beyond_angle_bounds = true;
513
514 if( beyond_radial_bounds || beyond_angle_bounds )
515 {
516 continue;
517 }
518 // If we are here then the point is contained by the child
519 return child;
520 }
521 }
522 else
523 {
524 // Radial layout
525 float polar_location[2];
526 polar_location[0] = sqrt( ( pnt[0] * pnt[0] ) + ( pnt[1] * pnt[1] ) );
527 polar_location[1] = vtkMath::DegreesFromRadians( atan2( pnt[1], pnt[0] ) );
528 if( polar_location[1] < 0 )
529 polar_location[1] += 360.;
530
531 float blimits[4];
532 vtkIdType vertex = otree->GetRoot();
533 if(vertex < 0)
534 {
535 return vertex;
536 }
537 vtkFloatArray *boundsInfo = vtkFloatArray::SafeDownCast(array);
538
539 // Now try to find the vertex that contains the point
540 boundsInfo->GetTupleValue(vertex, blimits); // Get the extents of the root
541 if( ((polar_location[0] > blimits[2]) && (polar_location[0] < blimits[3])) &&
542 ((polar_location[1] > blimits[0]) && (polar_location[1] < blimits[1])) )
543 {
544 // Point is at the root vertex.
545 // but we don't want the root to be pickable, so return -1.
546 // This won't work for blimits spanning the 0/360 rollover, but the test below
547 // catches that case.
548 return -1;
549 }
550
551 // Now traverse the children to try and find
552 // the vertex that contains the point
553 vtkIdType child;
554 VTK_CREATE(vtkTreeDFSIterator, it);
555 it->SetTree( otree );
556 it->SetStartVertex( vertex );
557
558 while (it->HasNext())
559 {
560 child = it->Next();
561 // if the root boundary starts anywhere but zero, the root node will have passed
562 // the earlier test. This will skip the root and prevent it from being picked.
563 if (child == vertex)
564 {
565 continue;
566 }
567 boundsInfo->GetTupleValue(child, blimits); // Get the extents of the child
568
569 // the range checking below doesn't work if either or both of blimits > 360
570 if ((blimits[0] > 360.0) && (blimits[1] > 360.0))
571 {
572 blimits[0] -= 360.0;
573 blimits[1] -= 360.0;
574 }
575 else if ((blimits[0] < 360.0) && (blimits[1] > 360.0) && (polar_location[1] < 360.0))
576 { // if the range spans the rollover at 0/360 on the circle
577 if (polar_location[1] < 90.0)
578 {
579 blimits[0] = 0.0;
580 blimits[1] -= 360.0;
581 }
582 else if (polar_location[1] > 270.)
583 {
584 blimits[1] = 360.0;
585 }
586 }
587 bool beyond_radial_bounds = false;
588 bool beyond_angle_bounds = false;
589 if( (polar_location[0] < blimits[2]) || (polar_location[0] > blimits[3]))
590 beyond_radial_bounds = true;
591 if( (polar_location[1] < blimits[0]) || (polar_location[1] > blimits[1]))
592 beyond_angle_bounds = true;
593
594 if( beyond_radial_bounds || beyond_angle_bounds )
595 {
596 continue;
597 }
598 // If we are here then the point is contained by the child
599 return child;
600 }
601 }
602 return -1;
603 }
604
605