1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkCirclePackFrontChainLayoutStrategy.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 "vtkCirclePackFrontChainLayoutStrategy.h"
22 #include "vtkAdjacentVertexIterator.h"
23 #include "vtkCellArray.h"
24 #include "vtkCellData.h"
25 #include "vtkDataArray.h"
26 #include "vtkInformation.h"
27 #include "vtkInformationVector.h"
28 #include "vtkMath.h"
29 #include "vtkObjectFactory.h"
30 #include "vtkPointData.h"
31 #include "vtkTree.h"
32 #include <cmath>
33 #include <limits>
34 #include <list>
35 #include <vector>
36
37 vtkStandardNewMacro(vtkCirclePackFrontChainLayoutStrategy);
38
39 class vtkCirclePackFrontChainLayoutStrategyImplementation
40 {
41
42 public:
43 vtkCirclePackFrontChainLayoutStrategyImplementation() = default;
44 ~vtkCirclePackFrontChainLayoutStrategyImplementation() = default;
45
46 void createCirclePacking(
47 vtkTree* tree, vtkDataArray* sizeArray, vtkDataArray* circlesArray, int height, int width);
48
49 void packTreeNodes(vtkIdType treeNode, double originX, double originY,
50 double enclosingCircleRadius, vtkDataArray* circlesArray, vtkDataArray* sizeArray,
51 vtkTree* tree);
52
53 void packBrotherNodes(std::vector<vtkIdType>& packedNodes, double originX, double originY,
54 double enclosingCircleRadius, vtkDataArray* circlesArray, vtkDataArray* sizeArray,
55 vtkTree* tree);
56
57 void findCircleCenter(vtkIdType Ci, vtkIdType Cm, vtkIdType Cn, vtkDataArray* circlesArray);
58
59 void findIntersectingCircle(vtkIdType Ci, bool& CjAfterCn, std::list<vtkIdType>::iterator& Cj,
60 std::list<vtkIdType>::iterator Cm, std::list<vtkIdType>::iterator Cn,
61 vtkDataArray* circlesArray, std::list<vtkIdType>& frontChain);
62
63 bool validCjAfterCn(vtkIdType Ci, std::list<vtkIdType>::iterator Cm,
64 std::list<vtkIdType>::iterator Cn, vtkDataArray* circlesArray, std::list<vtkIdType>& frontChain,
65 int searchPathLength);
66
67 bool validCjBeforeCm(vtkIdType Ci, std::list<vtkIdType>::iterator Cm,
68 std::list<vtkIdType>::iterator Cn, vtkDataArray* circlesArray, std::list<vtkIdType>& frontChain,
69 int searchPathLength);
70
71 void findCm(double originX, double originY, vtkDataArray* circlesArray,
72 std::list<vtkIdType>::iterator& Cm, std::list<vtkIdType>& frontChain);
73
74 void findCn(std::list<vtkIdType>::iterator Cm, std::list<vtkIdType>::iterator& Cn,
75 std::list<vtkIdType>& frontChain);
76
77 bool circlesIntersect(vtkIdType circleOne, vtkIdType circleTwo, vtkDataArray* circlesArray);
78
79 void deleteSection(std::list<vtkIdType>::iterator circleToStartAt,
80 std::list<vtkIdType>::iterator circleToEndAt, std::list<vtkIdType>& frontChain);
81
82 void incrListIteratorWrapAround(
83 std::list<vtkIdType>::iterator& i, std::list<vtkIdType>& frontChain);
84
85 void decrListIteratorWrapAround(
86 std::list<vtkIdType>::iterator& i, std::list<vtkIdType>& frontChain);
87
88 private:
89 };
90
incrListIteratorWrapAround(std::list<vtkIdType>::iterator & i,std::list<vtkIdType> & frontChain)91 void vtkCirclePackFrontChainLayoutStrategyImplementation::incrListIteratorWrapAround(
92 std::list<vtkIdType>::iterator& i, std::list<vtkIdType>& frontChain)
93 {
94 if (i != frontChain.end())
95 ++i;
96 else
97 i = frontChain.begin();
98 }
99
decrListIteratorWrapAround(std::list<vtkIdType>::iterator & i,std::list<vtkIdType> & frontChain)100 void vtkCirclePackFrontChainLayoutStrategyImplementation::decrListIteratorWrapAround(
101 std::list<vtkIdType>::iterator& i, std::list<vtkIdType>& frontChain)
102 {
103 if (i == frontChain.begin())
104 i = frontChain.end();
105 else if (!frontChain.empty())
106 --i;
107 }
108
createCirclePacking(vtkTree * tree,vtkDataArray * sizeArray,vtkDataArray * circlesArray,int height,int width)109 void vtkCirclePackFrontChainLayoutStrategyImplementation::createCirclePacking(
110 vtkTree* tree, vtkDataArray* sizeArray, vtkDataArray* circlesArray, int height, int width)
111 {
112 double enclosingCircleRadius = height / 2.0;
113 if (width < height)
114 {
115 enclosingCircleRadius = width / 2.0;
116 }
117
118 this->packTreeNodes(tree->GetRoot(), width / 2.0, height / 2.0, enclosingCircleRadius,
119 circlesArray, sizeArray, tree);
120 }
121
packTreeNodes(vtkIdType treeNode,double originX,double originY,double enclosingCircleRadius,vtkDataArray * circlesArray,vtkDataArray * sizeArray,vtkTree * tree)122 void vtkCirclePackFrontChainLayoutStrategyImplementation::packTreeNodes(vtkIdType treeNode,
123 double originX, double originY, double enclosingCircleRadius, vtkDataArray* circlesArray,
124 vtkDataArray* sizeArray, vtkTree* tree)
125 {
126
127 if (tree->IsLeaf(treeNode))
128 {
129 return;
130 }
131 else
132 {
133 if (tree->GetRoot() == treeNode)
134 {
135 double circle[3];
136 circle[0] = originX;
137 circle[1] = originY;
138 circle[2] = enclosingCircleRadius;
139 circlesArray->SetTuple(treeNode, circle);
140 }
141 std::vector<vtkIdType> childNodesPackList;
142 childNodesPackList.reserve(tree->GetNumberOfChildren(treeNode));
143 for (int i = 0; i < tree->GetNumberOfChildren(treeNode); i++)
144 {
145 childNodesPackList.push_back(tree->GetChild(treeNode, i));
146 }
147 this->packBrotherNodes(
148 childNodesPackList, originX, originY, enclosingCircleRadius, circlesArray, sizeArray, tree);
149 }
150 }
151
packBrotherNodes(std::vector<vtkIdType> & packedNodes,double originX,double originY,double enclosingCircleRadius,vtkDataArray * circlesArray,vtkDataArray * sizeArray,vtkTree * tree)152 void vtkCirclePackFrontChainLayoutStrategyImplementation::packBrotherNodes(
153 std::vector<vtkIdType>& packedNodes, double originX, double originY, double enclosingCircleRadius,
154 vtkDataArray* circlesArray, vtkDataArray* sizeArray, vtkTree* tree)
155 {
156
157 if (packedNodes.empty())
158 {
159 return;
160 }
161
162 std::list<vtkIdType> frontChain;
163 double circle[3]; // circle[0] is x,
164 // circle[1] is y,
165 // and circle[2] is the radius
166
167 // Handle only one node
168 if (packedNodes.size() == 1)
169 {
170 frontChain.push_back(packedNodes[0]);
171 circle[0] = 0.0;
172 circle[1] = 0.0;
173 circle[2] = sizeArray->GetTuple1(packedNodes[0]);
174 circlesArray->SetTuple(packedNodes[0], circle);
175 }
176 // Handle two nodes, align circles along x-axis
177 else if (packedNodes.size() == 2)
178 {
179 frontChain.push_back(packedNodes[0]);
180 circle[0] = 0.0 - sizeArray->GetTuple1(packedNodes[0]);
181 circle[1] = 0.0;
182 circle[2] = sizeArray->GetTuple1(packedNodes[0]);
183 circlesArray->SetTuple(packedNodes[0], circle);
184
185 frontChain.push_back(packedNodes[1]);
186 circle[0] = 0.0 + sizeArray->GetTuple1(packedNodes[1]);
187 circle[1] = 0.0;
188 circle[2] = sizeArray->GetTuple1(packedNodes[1]);
189 circlesArray->SetTuple(packedNodes[1], circle);
190 }
191 else
192 {
193 // Base case, find initial front-chain for first three nodes
194 double frad = sizeArray->GetTuple1(packedNodes[0]);
195 double srad = sizeArray->GetTuple1(packedNodes[1]);
196 double trad = sizeArray->GetTuple1(packedNodes[2]);
197
198 // Initially align first two circles along x-axis
199 frontChain.push_back(packedNodes[0]);
200 circle[0] = 0.0 - frad;
201 circle[1] = 0.0;
202 circle[2] = frad;
203 circlesArray->SetTuple(packedNodes[0], circle);
204
205 frontChain.push_back(packedNodes[1]);
206 circle[0] = 0.0 + srad;
207 circle[1] = 0.0;
208 circle[2] = srad;
209 circlesArray->SetTuple(packedNodes[1], circle);
210
211 circle[0] = 0.0;
212 circle[1] = 0.0;
213 circle[2] = trad;
214 circlesArray->SetTuple(packedNodes[2], circle);
215
216 this->findCircleCenter(packedNodes[2], packedNodes[0], packedNodes[1], circlesArray);
217 frontChain.insert(--(frontChain.end()), packedNodes[2]);
218
219 // Adjust the three circle centers so that they are centered around the origin point.
220 // First, find the radius of the interior Soddy circle. This is the circle that is
221 // tangent to all three circles in the interior space defined by the circles.
222 // Simple formula, just google for Soddy circle. We take the positive solution, which is
223 // the interior Soddy circle.
224 double r1 = frad;
225 double r2 = srad;
226 double r3 = trad;
227 double soddyRad = (r1 * r2 * r3) /
228 ((r2 * r3) + (r1 * r2) + (r1 * r3) + 2.0 * sqrt(r1 * r2 * r3 * (r1 + r2 + r3)));
229 // Use the Law of Cosines again to find the angle between the first circle center and the center
230 // of the Soddy circle.
231 double angle = acos((-pow(srad + soddyRad, 2) + pow(frad + soddyRad, 2) + pow(frad + srad, 2)) /
232 (2.0 * (frad + soddyRad) * (frad + srad)));
233 // Find x and y adjustments
234 double yAdjust = (frad + soddyRad) * sin(angle);
235 double xAdjust = (frad + soddyRad) * cos(angle);
236 double c0[3];
237 double c1[3];
238 double c2[3];
239 circlesArray->GetTuple(packedNodes[0], c0);
240 circlesArray->GetTuple(packedNodes[1], c1);
241 circlesArray->GetTuple(packedNodes[2], c2);
242 c0[1] -= yAdjust;
243 c1[1] -= yAdjust;
244 c2[1] -= yAdjust;
245 if (xAdjust > frad)
246 {
247 c0[0] -= (xAdjust - frad);
248 c1[0] -= (xAdjust - frad);
249 c2[0] -= (xAdjust - frad);
250 }
251 else
252 {
253 c0[0] += (frad - xAdjust);
254 c1[0] += (frad - xAdjust);
255 c2[0] += (frad - xAdjust);
256 }
257 circlesArray->SetTuple(packedNodes[0], c0);
258 circlesArray->SetTuple(packedNodes[1], c1);
259 circlesArray->SetTuple(packedNodes[2], c2);
260
261 // Iterate over the remaining brother nodes to find circle packing
262 std::list<vtkIdType>::iterator Cm;
263 std::list<vtkIdType>::iterator Cn;
264 this->findCm(0.0, 0.0, circlesArray, Cm, frontChain);
265 this->findCn(Cm, Cn, frontChain);
266
267 for (int i = 3; i < (int)packedNodes.size(); i++)
268 {
269 circle[0] = 0.0;
270 circle[1] = 0.0;
271 circle[2] = sizeArray->GetTuple1(packedNodes[i]);
272 circlesArray->SetTuple(packedNodes[i], circle);
273
274 std::list<vtkIdType>::iterator Cj;
275 bool CjAfterCn;
276 this->findIntersectingCircle(packedNodes[i], CjAfterCn, Cj, Cm, Cn, circlesArray, frontChain);
277
278 while (Cj != frontChain.end())
279 {
280 // We have an intersection, so handle one of the two cases.
281 // Cj is greater than Cn on the front chain
282 if (CjAfterCn)
283 {
284 this->deleteSection(Cm, Cj, frontChain);
285 Cn = Cj;
286 }
287 // Cj is less than Cm on the front chain
288 else
289 {
290 this->deleteSection(Cj, Cn, frontChain);
291 Cm = Cj;
292 }
293
294 this->findIntersectingCircle(
295 packedNodes[i], CjAfterCn, Cj, Cm, Cn, circlesArray, frontChain);
296 }
297
298 // First case, there is no intersection so just insert Ci between Cm and Cn
299 std::list<vtkIdType>::iterator ti = Cm;
300 incrListIteratorWrapAround(ti, frontChain);
301 frontChain.insert(ti, packedNodes[i]);
302 this->findCn(Cm, Cn, frontChain);
303 }
304 }
305
306 // Scale circle layout to fit within the enclosing circle radius
307 double Xfc = 0.0;
308 double Yfc = 0.0;
309 std::list<vtkIdType>::iterator it;
310 for (it = frontChain.begin(); it != frontChain.end(); ++it)
311 {
312 circlesArray->GetTuple(*it, circle);
313 Xfc += circle[0];
314 Yfc += circle[1];
315 }
316
317 Xfc = Xfc / ((double)frontChain.size());
318 Yfc = Yfc / ((double)frontChain.size());
319
320 double layoutRadius = 0;
321 for (it = frontChain.begin(); it != frontChain.end(); ++it)
322 {
323 circlesArray->GetTuple(*it, circle);
324 double distance = sqrt(pow(circle[0] - Xfc, 2) + pow(circle[1] - Yfc, 2)) + circle[2];
325 if (distance > layoutRadius)
326 {
327 layoutRadius = distance;
328 }
329 }
330
331 double scaleFactor = (layoutRadius == 0) ? 1.0 : (enclosingCircleRadius / layoutRadius);
332
333 // Scale and translate each circle
334 for (int i = 0; i < (int)packedNodes.size(); i++)
335 {
336 circlesArray->GetTuple(packedNodes[i], circle);
337 circle[0] = (circle[0] - Xfc) * scaleFactor + originX;
338 circle[1] = (circle[1] - Yfc) * scaleFactor + originY;
339 circle[2] = circle[2] * scaleFactor;
340 circlesArray->SetTuple(packedNodes[i], circle);
341 }
342
343 // Now that each circle at this level is positioned and scaled,
344 // find the layout for the children of each circle and add the
345 // result to the packing list.
346 for (int i = 0; i < (int)packedNodes.size(); i++)
347 {
348 circlesArray->GetTuple(packedNodes[i], circle);
349 this->packTreeNodes(
350 packedNodes[i], circle[0], circle[1], circle[2], circlesArray, sizeArray, tree);
351 }
352 }
353
validCjAfterCn(vtkIdType Ci,std::list<vtkIdType>::iterator Cm,std::list<vtkIdType>::iterator Cn,vtkDataArray * circlesArray,std::list<vtkIdType> & frontChain,int searchPathLength)354 bool vtkCirclePackFrontChainLayoutStrategyImplementation::validCjAfterCn(vtkIdType Ci,
355 std::list<vtkIdType>::iterator Cm, std::list<vtkIdType>::iterator Cn, vtkDataArray* circlesArray,
356 std::list<vtkIdType>& frontChain, int searchPathLength)
357 {
358 this->findCircleCenter(Ci, *Cm, *Cn, circlesArray);
359
360 int CnSearchPathLength = 0;
361 while (CnSearchPathLength < searchPathLength)
362 {
363 CnSearchPathLength++;
364 decrListIteratorWrapAround(Cn, frontChain);
365 if (Cn == frontChain.end())
366 {
367 decrListIteratorWrapAround(Cn, frontChain);
368 }
369 if (this->circlesIntersect(Ci, *Cn, circlesArray))
370 {
371 return false;
372 }
373 }
374
375 return true;
376 }
377
validCjBeforeCm(vtkIdType Ci,std::list<vtkIdType>::iterator Cm,std::list<vtkIdType>::iterator Cn,vtkDataArray * circlesArray,std::list<vtkIdType> & frontChain,int searchPathLength)378 bool vtkCirclePackFrontChainLayoutStrategyImplementation::validCjBeforeCm(vtkIdType Ci,
379 std::list<vtkIdType>::iterator Cm, std::list<vtkIdType>::iterator Cn, vtkDataArray* circlesArray,
380 std::list<vtkIdType>& frontChain, int searchPathLength)
381 {
382 this->findCircleCenter(Ci, *Cm, *Cn, circlesArray);
383
384 int CmSearchPathLength = 0;
385 while (CmSearchPathLength < searchPathLength)
386 {
387 CmSearchPathLength++;
388 incrListIteratorWrapAround(Cm, frontChain);
389 if (Cm == frontChain.end())
390 {
391 incrListIteratorWrapAround(Cm, frontChain);
392 }
393 if (this->circlesIntersect(Ci, *Cm, circlesArray))
394 {
395 return false;
396 }
397 }
398 return true;
399 }
400
findIntersectingCircle(vtkIdType Ci,bool & CjAfterCn,std::list<vtkIdType>::iterator & Cj,std::list<vtkIdType>::iterator Cm,std::list<vtkIdType>::iterator Cn,vtkDataArray * circlesArray,std::list<vtkIdType> & frontChain)401 void vtkCirclePackFrontChainLayoutStrategyImplementation::findIntersectingCircle(vtkIdType Ci,
402 bool& CjAfterCn, std::list<vtkIdType>::iterator& Cj, std::list<vtkIdType>::iterator Cm,
403 std::list<vtkIdType>::iterator Cn, vtkDataArray* circlesArray, std::list<vtkIdType>& frontChain)
404 {
405 // Start from Cn and look for the first intersection Cj until we have searched half
406 // of the frontChain. Do the same for Cm. Compare the Cm and Cn search lengths and
407 // take the shortest, if any intersecting Cj was found.
408 std::list<vtkIdType>::iterator CjfromCn = frontChain.end();
409 std::list<vtkIdType>::iterator CjfromCm = frontChain.end();
410 std::list<vtkIdType>::iterator lCm = Cm;
411 std::list<vtkIdType>::iterator lCn = Cn;
412 int fcl = (int)frontChain.size();
413 int searchPathLength = (int)ceil(((double)fcl - 2.0) / 2.0);
414
415 this->findCircleCenter(Ci, *Cm, *Cn, circlesArray);
416
417 int CnSearchPathLength = 0;
418 while (CnSearchPathLength < searchPathLength)
419 {
420 CnSearchPathLength++;
421 incrListIteratorWrapAround(lCn, frontChain);
422 if (lCn == frontChain.end())
423 incrListIteratorWrapAround(lCn, frontChain);
424
425 if (this->circlesIntersect(Ci, *lCn, circlesArray))
426 {
427 CjfromCn = lCn;
428 break;
429 }
430 }
431
432 // There is an intersection. Check
433 // to see if the front chain is clear
434 // to be deleted from Cm to Cj.
435 if (CjfromCn != frontChain.end())
436 {
437 Cj = CjfromCn;
438 if (this->validCjAfterCn(Ci, Cm, lCn, circlesArray, frontChain, CnSearchPathLength))
439 {
440 CjAfterCn = true;
441 }
442 else
443 {
444 CjAfterCn = false;
445 }
446 return;
447 }
448
449 int CmSearchPathLength = 0;
450 while (CmSearchPathLength < searchPathLength)
451 {
452 CmSearchPathLength++;
453 decrListIteratorWrapAround(lCm, frontChain);
454 if (lCm == frontChain.end())
455 decrListIteratorWrapAround(lCm, frontChain);
456
457 if (this->circlesIntersect(Ci, *lCm, circlesArray))
458 {
459 CjfromCm = lCm;
460 break;
461 }
462 }
463
464 // There is an intersection. Check
465 // to see if the front chain is clear
466 // to be deleted from Cj to Cn.
467 if (CjfromCm != frontChain.end())
468 {
469 Cj = CjfromCm;
470 if (this->validCjBeforeCm(Ci, lCm, Cn, circlesArray, frontChain, CmSearchPathLength))
471 {
472 CjAfterCn = false;
473 }
474 else
475 {
476 CjAfterCn = true;
477 }
478 return;
479 }
480
481 // No intersection found
482 Cj = frontChain.end();
483 CjAfterCn = false;
484 }
485
findCircleCenter(vtkIdType Ci,vtkIdType Cm,vtkIdType Cn,vtkDataArray * circlesArray)486 void vtkCirclePackFrontChainLayoutStrategyImplementation::findCircleCenter(
487 vtkIdType Ci, vtkIdType Cm, vtkIdType Cn, vtkDataArray* circlesArray)
488 {
489
490 double circle[3];
491 circlesArray->GetTuple(Cm, circle);
492 double rCm = circle[2];
493 double xCm = circle[0];
494 double yCm = circle[1];
495
496 circlesArray->GetTuple(Cn, circle);
497 double rCn = circle[2];
498 double xCn = circle[0];
499 double yCn = circle[1];
500
501 circlesArray->GetTuple(Ci, circle);
502 double rCi = circle[2];
503 double xCi = circle[0];
504 double yCi = circle[1];
505
506 // Find the angle as measured from the x-axis to the line segment between rCm and rCn, with the
507 // origin at rCm.
508 double xc = xCn - xCm;
509 double yc = yCn - yCm;
510 double xAxisAngle = atan2(yc, xc);
511 // Find positive rotation angle
512 if (xAxisAngle < 0)
513 {
514 xAxisAngle = vtkMath::Pi() + (vtkMath::Pi() + xAxisAngle);
515 }
516
517 // Find the distance between the centers of Cm and Cn
518 double CmCnDistance = sqrt(pow(xCn - xCm, 2) + pow(yCn - yCm, 2));
519
520 // Find an interior angle of the triangle defined by all three circle centers using the Law of
521 // Cosines
522 double angle = acos((-pow(rCn + rCi, 2) + pow(rCm + rCi, 2) + pow(CmCnDistance, 2)) /
523 (2.0 * (rCm + rCi) * (CmCnDistance)));
524
525 // Find the center of the third triangle by using the interior angle and the length of the
526 // triangle side
527 xCi = (rCm + rCi) * cos(angle);
528 yCi = (rCm + rCi) * sin(angle);
529
530 // Rotate the center of Ci from the x-axis by xAxisAngle
531 double x = xCi;
532 double y = yCi;
533 xCi = x * cos(xAxisAngle) - y * sin(xAxisAngle);
534 yCi = x * sin(xAxisAngle) + y * cos(xAxisAngle);
535 xCi += xCm;
536 yCi += yCm;
537
538 circlesArray->GetTuple(Ci, circle);
539 circle[0] = xCi;
540 circle[1] = yCi;
541 circlesArray->SetTuple(Ci, circle);
542 }
543
findCm(double originX,double originY,vtkDataArray * circlesArray,std::list<vtkIdType>::iterator & Cm,std::list<vtkIdType> & frontChain)544 void vtkCirclePackFrontChainLayoutStrategyImplementation::findCm(double originX, double originY,
545 vtkDataArray* circlesArray, std::list<vtkIdType>::iterator& Cm, std::list<vtkIdType>& frontChain)
546 {
547 std::list<vtkIdType>::iterator it = frontChain.begin();
548 Cm = it;
549 double circle[3];
550 double minDistance = 0.0;
551 if (!frontChain.empty())
552 {
553 circlesArray->GetTuple(*it, circle);
554 minDistance = pow(circle[0] - originX, 2) + pow(circle[1] - originY, 2);
555 ++it;
556 }
557
558 for (; it != frontChain.end(); ++it)
559 {
560 circlesArray->GetTuple(*it, circle);
561 double distanceSq = pow(circle[0] - originX, 2) + pow(circle[1] - originY, 2);
562
563 if (distanceSq < minDistance)
564 {
565 Cm = it;
566 minDistance = distanceSq;
567 }
568 }
569 }
570
findCn(std::list<vtkIdType>::iterator Cm,std::list<vtkIdType>::iterator & Cn,std::list<vtkIdType> & frontChain)571 void vtkCirclePackFrontChainLayoutStrategyImplementation::findCn(std::list<vtkIdType>::iterator Cm,
572 std::list<vtkIdType>::iterator& Cn, std::list<vtkIdType>& frontChain)
573 {
574 incrListIteratorWrapAround(Cm, frontChain);
575 if (Cm == frontChain.end())
576 {
577 Cn = frontChain.begin();
578 }
579 else
580 {
581 Cn = Cm;
582 }
583 }
584
circlesIntersect(vtkIdType circleOne,vtkIdType circleTwo,vtkDataArray * circlesArray)585 bool vtkCirclePackFrontChainLayoutStrategyImplementation::circlesIntersect(
586 vtkIdType circleOne, vtkIdType circleTwo, vtkDataArray* circlesArray)
587 {
588 double c1[3];
589 double c2[3];
590 circlesArray->GetTuple(circleOne, c1);
591 circlesArray->GetTuple(circleTwo, c2);
592
593 double distanceSq = pow(c1[0] - c2[0], 2) + pow(c1[1] - c2[1], 2);
594
595 if (distanceSq > pow(c1[2] + c2[2], 2))
596 {
597 return false;
598 }
599 else
600 {
601 return true;
602 }
603 }
604
605 // Delete all circles out of fronChain from circleToStartAt to circleToEndAt, not including
606 // circleToStartAt and circleToEndAt. Insert all deleted elements into circlePacking list.
deleteSection(std::list<vtkIdType>::iterator circleToStartAt,std::list<vtkIdType>::iterator circleToEndAt,std::list<vtkIdType> & frontChain)607 void vtkCirclePackFrontChainLayoutStrategyImplementation::deleteSection(
608 std::list<vtkIdType>::iterator circleToStartAt, std::list<vtkIdType>::iterator circleToEndAt,
609 std::list<vtkIdType>& frontChain)
610 {
611 incrListIteratorWrapAround(circleToStartAt, frontChain);
612 while ((circleToStartAt != frontChain.end()) && (circleToStartAt != circleToEndAt))
613 {
614 circleToStartAt = frontChain.erase(circleToStartAt);
615 }
616
617 if (circleToStartAt != circleToEndAt)
618 {
619 circleToStartAt = frontChain.begin();
620 while ((circleToStartAt != frontChain.end()) && (circleToStartAt != circleToEndAt))
621 {
622 circleToStartAt = frontChain.erase(circleToStartAt);
623 }
624 }
625 }
626
vtkCirclePackFrontChainLayoutStrategy()627 vtkCirclePackFrontChainLayoutStrategy::vtkCirclePackFrontChainLayoutStrategy()
628 {
629 this->Width = 1;
630 this->Height = 1;
631 this->pimpl = new vtkCirclePackFrontChainLayoutStrategyImplementation;
632 }
633
~vtkCirclePackFrontChainLayoutStrategy()634 vtkCirclePackFrontChainLayoutStrategy::~vtkCirclePackFrontChainLayoutStrategy()
635 {
636 delete this->pimpl;
637 this->pimpl = nullptr;
638 }
639
Layout(vtkTree * inputTree,vtkDataArray * areaArray,vtkDataArray * sizeArray)640 void vtkCirclePackFrontChainLayoutStrategy::Layout(
641 vtkTree* inputTree, vtkDataArray* areaArray, vtkDataArray* sizeArray)
642 {
643
644 this->pimpl->createCirclePacking(inputTree, sizeArray, areaArray, this->Height, this->Width);
645 }
646
PrintSelf(ostream & os,vtkIndent indent)647 void vtkCirclePackFrontChainLayoutStrategy::PrintSelf(ostream& os, vtkIndent indent)
648 {
649 this->Superclass::PrintSelf(os, indent);
650 os << indent << "Width: " << this->Width << endl;
651 os << indent << "Height: " << this->Height << endl;
652 }
653