1#ifndef RNAPUZZLER_CONFIGTREE_H 2#define RNAPUZZLER_CONFIGTREE_H 3 4/* 5 * RNApuzzler configtree 6 * 7 * c Daniel Wiegreffe, Daniel Alexander, Dirk Zeckzer 8 * ViennaRNA package 9 */ 10 11#include <stdlib.h> 12#include <math.h> 13 14#include "ViennaRNA/utils/basic.h" 15 16#include "boundingBoxes.inc" 17#include "drawingconfig.inc" 18#include "vector_math.inc" 19#include "definitions.inc" 20#include "../headers/tBaseInformation_struct.h" 21#include "../headers/config_struct.h" 22#include "../headers/AABB_struct.h" 23#include "../headers/boundingBoxes_struct.h" 24#include "../headers/configtree_struct.h" 25 26/*--------------------------------------------------------------------------*/ 27 28PRIVATE void 29updateAABB(AABB *aabb, 30 stemBox *sBox, 31 loopBox *lBox); 32 33 34PRIVATE short 35isExterior(const treeNode *node); 36 37 38PRIVATE treeNode * 39getExterior(treeNode *node); 40 41 42PRIVATE short 43isInteriorLoop(const treeNode *node); 44 45 46PRIVATE short 47isMultiLoop(const treeNode *node); 48 49 50/** 51 * @brief buildConfigtree 52 * @param pair_table 53 * - definition of the RNAs pairing 54 * @param baseInformation 55 * - array of tBaseInformation that grants information about the RNA 56 * (only config is needed here) 57 * @param x 58 * @param y 59 * @param bulge 60 * - distance between regular stem and bulge base 61 * @return 62 * - a configtree build from the given RNA pairing. 63 * gives information about all configurations (config) applied to the RNA. 64 */ 65PRIVATE treeNode * 66buildConfigtree(const short *const pair_table, 67 const tBaseInformation *baseInformation, 68 const double *x, 69 const double *y, 70 const double bulge); 71 72 73PRIVATE void 74updateBoundingBoxes(treeNode *node, 75 const vrna_plot_options_puzzler_t *puzzler); 76 77 78/** 79 * @brief applyChangesToConfigAndBoundingBoxes 80 * Function to apply a set of config changes to the given treenode. 81 * 82 * By passing -1.0 to radiusNew you will apply the minimum possible radius for this loop while not allowing to shrink the loop. 83 * In case it would actually shrink a default relative increase is applied to the radius. 84 * 85 * By passing 0.0 to radiusNew you set the minimum possible radius no matter if there would be some shrinking or not. 86 * @param tree the node to change 87 * @param deltaCfg array of angles to change (in degree) 88 * @param radiusNew desired radius to set while applying deltas 89 * @param puzzler 90 * @return 1 if the changes were applied, 0 otherwise 91 */ 92PRIVATE void 93applyChangesToConfigAndBoundingBoxes(treeNode *tree, 94 const double *deltaCfg, 95 const double radiusNew, 96 const vrna_plot_options_puzzler_t *puzzler); 97 98 99/** 100 * @brief translateBoundingBoxes 101 * - Performs a translation of a whole branch by a given vector. 102 * Used to apply changes in config to the tree and its bounding boxes. 103 * @param tree 104 * - tree that is being translated 105 * @param vector 106 * - translation vector as double array[2] 107 */ 108PRIVATE void 109translateBoundingBoxes(treeNode *tree, 110 const double *vector); 111 112 113/** 114 * @brief getChildIndex 115 * - gets the index of child node where to find the node with given ID. 116 * @param tree 117 * - configtree you want to search in. 118 * @param childID 119 * - ID of childnode you are looking for. 120 * @return 121 * - child index or -1 if tree does not contain such a childnode. 122 */ 123PRIVATE int 124getChildIndex(const treeNode *tree, 125 const int childID); 126 127 128/** 129 * @brief getChildAngle 130 * - Calculates the angle of a given child node (given by ID) at a loop. 131 * This child does not need to be a direct child node but can be any sort of grand child. 132 * If the given node is a child of the loop, the rotation angle of its center node 133 * will be calculated. 134 * @param root 135 * - tree node acting as parent loop 136 * @param node 137 * - child node of which you want to know the angle 138 * @return 139 * - angle of child node 140 * the resulting angle might be smaller than 0° or greater than 360° 141 */ 142PRIVATE double 143getChildAngle(const treeNode *root, 144 const treeNode *child); 145 146 147/** 148 * @brief getChildAngleByIndex 149 * - Calculates the clockwise angle of a given child node (given by name) at a loop. 150 * This child needs to be a direct child node 151 * The rotation angle of its center node will be calculated. 152 * @param parentNode 153 * - tree node acting as parent loop 154 * @param childIndex 155 * - index of child node of which you want to know the angle 156 * @return 157 * - angle of child node 158 * the resulting angle might be smaller than 0° or greater than 360° 159 */ 160PRIVATE double 161getChildAngleByIndex(const treeNode *parentNode, 162 const int childIndex); 163 164 165/** 166 * @brief getLoopCenter 167 * - Getter for the center coordinates of a tree node's loop. 168 * @param node 169 * - your tree node 170 * @param p 171 * - double[2] return value for the loop's center coordinates 172 */ 173PRIVATE void 174getLoopCenter(const treeNode *node, 175 double p[2]); 176 177 178/** 179 * @brief getStemCenter 180 * - Getter for the center coordinates of a tree node's stem. 181 * @param node 182 * - your tree node 183 * @param p 184 * - double[2] return value for the stem's center coordinates 185 */ 186PRIVATE void 187getStemCenter(const treeNode *node, 188 double p[2]); 189 190 191/** 192 * @brief getChildNode 193 * - searches for the node with given childID in a configtree. 194 * @param tree 195 * - configtree you want to search in. 196 * @param childID 197 * - ID of childnode you are looking for. 198 * @return 199 * - ptr to node or NULL if tree does not contain such a childnode. 200 */ 201PRIVATE treeNode * 202getChildNode(treeNode *tree, 203 const int childID); 204 205 206PRIVATE treeNode * 207getParent(const treeNode *node); 208 209 210PRIVATE treeNode * 211getChild(const treeNode *node, 212 const int index); 213 214 215PRIVATE char 216getNodeName(const treeNode *node); 217 218 219PRIVATE int 220getNodeID(const treeNode *node); 221 222 223PRIVATE void 224printTree(const treeNode *node, 225 const int level); 226 227 228PRIVATE int 229countSubtreeNodes(const treeNode *node); 230 231 232PRIVATE int 233collectSubtreeNodes(treeNode *node, 234 treeNode **const allNodes, 235 const int index); 236 237 238PRIVATE int 239countAncestorNodes(const treeNode *node); 240 241 242PRIVATE void 243collectAncestorNodes(const treeNode *node, 244 treeNode **const ancestorList); 245 246 247PRIVATE double 248getPairedAngle(const treeNode *node); 249 250 251PRIVATE void 252freeTree(treeNode *node); 253 254 255PRIVATE void 256updateAABB(AABB *aabb, 257 stemBox *sBox, 258 loopBox *lBox) 259{ 260 const double stem_ea[2] = { 261 sBox->e[0] * sBox->a[0], 262 sBox->e[0] * sBox->a[1] 263 }; 264 const double stem_eb[2] = { 265 sBox->e[1] * sBox->b[0], 266 sBox->e[1] * sBox->b[1] 267 }; 268 269 int numPoints = 6 + sBox->bulgeCount; 270 271 /* array of relevant points */ 272 double **p = (double **)vrna_alloc(numPoints * sizeof(double *)); 273 274 for (int i = 0; i < numPoints; i++) 275 276 p[i] = (double *)vrna_alloc(2 * sizeof(double)); 277 278 /* corners of stem */ 279 p[0][0] = sBox->c[0] - stem_ea[0] + stem_eb[0]; 280 p[0][1] = sBox->c[1] - stem_ea[1] + stem_eb[1]; 281 p[1][0] = sBox->c[0] + stem_ea[0] + stem_eb[0]; 282 p[1][1] = sBox->c[1] + stem_ea[1] + stem_eb[1]; 283 p[2][0] = sBox->c[0] + stem_ea[0] - stem_eb[0]; 284 p[2][1] = sBox->c[1] + stem_ea[1] - stem_eb[1]; 285 p[3][0] = sBox->c[0] - stem_ea[0] - stem_eb[0]; 286 p[3][1] = sBox->c[1] - stem_ea[1] - stem_eb[1]; 287 288 /* lower left of loop AABB */ 289 p[4][0] = lBox->c[0] - lBox->r; 290 p[4][1] = lBox->c[1] - lBox->r; 291 /* upper right of loop AABB */ 292 p[5][0] = lBox->c[0] + lBox->r; 293 p[5][1] = lBox->c[1] + lBox->r; 294 295 /* bulge points */ 296 double pPrev[2], pNext[2]; 297 for (int i = 0; i < sBox->bulgeCount; i++) 298 299 getBulgeCoordinates(sBox, i, pPrev, p[6 + i], pNext); 300 301 /* set aabb */ 302 aabb->min[0] = p[0][0]; 303 aabb->min[1] = p[0][1]; 304 aabb->max[0] = p[0][0]; 305 aabb->max[1] = p[0][1]; 306 for (int i = 1; i < numPoints; i++) { 307 if (aabb->min[0] > p[i][0]) 308 aabb->min[0] = p[i][0]; 309 310 if (aabb->min[1] > p[i][1]) 311 aabb->min[1] = p[i][1]; 312 313 if (aabb->max[0] < p[i][0]) 314 aabb->max[0] = p[i][0]; 315 316 if (aabb->max[1] < p[i][1]) 317 aabb->max[1] = p[i][1]; 318 } 319 320 /* free allocated memory */ 321 for (int i = 0; i < numPoints; i++) 322 323 free(p[i]); 324 free(p); 325} 326 327 328PRIVATE void 329updateBoundingBoxes(treeNode *node, 330 const vrna_plot_options_puzzler_t *puzzler) 331{ 332 /* 333 * fix this node's loop 334 * then for each child fix the stem and bulges 335 * and call recursively 336 */ 337 338 if (!isExterior(node)) { 339 long numStemBackBones = lround((2.0 * node->sBox->e[0]) / puzzler->unpaired); 340 double stemLength = puzzler->unpaired * numStemBackBones; 341 double distanceStemEndToLoopCenter = sqrt( 342 node->cfg->radius * node->cfg->radius - 0.25 * puzzler->paired * puzzler->paired); 343 double distanceStemCenterToLoopCenter = 0.5 * stemLength + distanceStemEndToLoopCenter; 344 node->lBox->c[0] = node->sBox->c[0] + distanceStemCenterToLoopCenter * node->sBox->a[0]; 345 node->lBox->c[1] = node->sBox->c[1] + distanceStemCenterToLoopCenter * node->sBox->a[1]; 346 node->lBox->r = node->cfg->radius; 347 348 updateAABB(&(node->aabb), node->sBox, node->lBox); 349 } 350 351 double childAngleRad = 0.0; 352 353 for (int i = 0; i < node->childCount; i++) { 354 treeNode *child = getChild(node, i); 355 stemBox *sBox = child->sBox; 356 loopBox *lBox = child->lBox; 357 358 double parentLoopCenter[2]; 359 if (isExterior(node)) { 360 parentLoopCenter[0] = lBox->c[0]; 361 parentLoopCenter[1] = EXTERIOR_Y; 362 } else { 363 getLoopCenter(node, parentLoopCenter); 364 } 365 366 /* fix the stem's extensions */ 367 long numStemBackBones = lround((2.0 * sBox->e[0]) / puzzler->unpaired); 368 double stemLength = puzzler->unpaired * numStemBackBones; 369 sBox->e[0] = 0.5 * stemLength; 370 sBox->e[1] = 0.5 * puzzler->paired; 371 372 /* fix the stem's directions */ 373 if (isExterior(node)) 374 childAngleRad = MATH_PI; 375 else 376 childAngleRad += getArcAngle(node->cfg, i); 377 378 double aFixed[2]; 379 if (isExterior(node)) { 380 aFixed[0] = 0.0; 381 aFixed[1] = 1.0; 382 } else { 383 double gamma = childAngleRad - MATH_PI; 384 rotateVectorByAngle(node->sBox->a, gamma, aFixed); 385 } 386 387 sBox->a[0] = aFixed[0]; 388 sBox->a[1] = aFixed[1]; 389 390 double bFixed[2]; 391 normal(aFixed, bFixed); 392 bFixed[0] *= -1; 393 bFixed[1] *= -1; 394 sBox->b[0] = bFixed[0]; 395 sBox->b[1] = bFixed[1]; 396 397 double s0 = 0; 398 if (!isExterior(node)) 399 400 s0 = sqrt(node->cfg->radius * node->cfg->radius - 0.25 * puzzler->paired * puzzler->paired); 401 402 double distanceStemCenter = s0 + 0.5 * stemLength; 403 404 /* fix the stem's position */ 405 sBox->c[0] = parentLoopCenter[0] + distanceStemCenter * aFixed[0]; 406 sBox->c[1] = parentLoopCenter[1] + distanceStemCenter * aFixed[1]; 407 408 if (stemLength == 0) 409 410 sBox->e[0] = EPSILON_7; 411 } 412 413 for (int i = 0; i < node->childCount; i++) 414 415 updateBoundingBoxes(getChild(node, i), puzzler); 416} 417 418 419PRIVATE void 420applyChangesToConfigAndBoundingBoxes(treeNode *tree, 421 const double *deltaCfg, 422 const double radiusNew, 423 const vrna_plot_options_puzzler_t *puzzler) 424{ 425 /* Apply all changes to config */ 426 config *cfg = tree->cfg; 427 428 /* start with adjusting config radius and angles */ 429 cfgApplyChanges(cfg, getNodeName(tree), deltaCfg, radiusNew, puzzler); 430 431 /* apply changes of config to bounding boxes */ 432 updateBoundingBoxes(tree, puzzler); 433} 434 435 436PRIVATE void 437freeBulges(stemBox *sBox) 438{ 439 if (sBox->bulges != NULL) { 440 for (int currentBulge = 0; currentBulge < sBox->bulgeCount; currentBulge++) 441 442 free(sBox->bulges[currentBulge]); 443 free(sBox->bulges); 444 } 445} 446 447 448PRIVATE void 449freeTree(treeNode *node) 450{ 451 for (int currentChild = 0; currentChild < node->childCount; currentChild++) 452 453 freeTree(getChild(node, currentChild)); 454 455 if (node->cfg) 456 457 cfgFreeConfig(node->cfg); 458 459 if (node->children) 460 461 free(node->children); 462 463 if (node->lBox) 464 465 free(node->lBox); 466 467 if (node->sBox) { 468 freeBulges(node->sBox); 469 free(node->sBox); 470 } 471 472 free(node); 473} 474 475 476PRIVATE int 477countSubtreeNodes(const treeNode *node) 478{ 479 int count = 1; /* count this node */ 480 481 for (int currentChild = 0; currentChild < node->childCount; currentChild++) 482 /* count children and add child count */ 483 count += countSubtreeNodes(getChild(node, currentChild)); 484 485 return count; 486} 487 488 489PRIVATE int 490countAncestorNodes(const treeNode *node) 491{ 492 int count = 0; 493 494 treeNode *ancestor = getParent(node); 495 496 while (ancestor != NULL) { 497 ++count; 498 ancestor = getParent(ancestor); 499 } 500 501 return count; 502} 503 504 505PRIVATE int 506collectSubtreeNodes(treeNode *node, 507 treeNode **const allNodes, 508 const int currentIndex) 509{ 510 allNodes[currentIndex] = node; 511 int nextIndex = currentIndex + 1; /* increase index as this one was just taken */ 512 513 for (int currentChild = 0; currentChild < node->childCount; currentChild++) 514 515 nextIndex = collectSubtreeNodes(getChild(node, currentChild), allNodes, nextIndex); 516 517 return nextIndex; 518} 519 520 521PRIVATE void 522collectAncestorNodes(const treeNode *node, 523 treeNode **const ancestorList) 524{ 525 int currentIndex = 0; 526 treeNode *ancestor = getParent(node); 527 528 while (ancestor != NULL) { 529 ancestorList[currentIndex] = ancestor; 530 ++currentIndex; 531 ancestor = getParent(ancestor); 532 } 533} 534 535 536PRIVATE double 537getPairedAngle(const treeNode *node) 538{ 539 /* get the current node's stem's bounding wedge */ 540 stemBox *sBox = node->sBox; 541 double pStemTopCorner[2]; 542 543 pStemTopCorner[0] = sBox->c[0] + sBox->e[0] * sBox->a[0] + sBox->e[1] * sBox->b[0]; 544 pStemTopCorner[1] = sBox->c[1] + sBox->e[0] * sBox->a[1] + sBox->e[1] * sBox->b[1]; 545 double pLoopCenter[2]; 546 getLoopCenter(node, pLoopCenter); 547 double vLoopCenterToStemTopCorner[2]; 548 vector(pLoopCenter, pStemTopCorner, vLoopCenterToStemTopCorner); 549 double vLoopCenterToStemCenter[2] = { 550 (-1) * sBox->a[0], (-1) * sBox->a[1] 551 }; 552 double minOuterAngle = 553 angleBetweenVectors2D(vLoopCenterToStemCenter, vLoopCenterToStemTopCorner); 554 555 /* all arcs share the same stem angle */ 556 double stemAngle = 2 * minOuterAngle; 557 return stemAngle; 558} 559 560 561PRIVATE short 562isExterior(const treeNode *node) 563{ 564 return getNodeID(node) == 0; 565} 566 567 568treeNode * 569getExterior(treeNode *node) 570{ 571 treeNode *exteriorCandidate = node; 572 573 while (!isExterior(exteriorCandidate)) 574 575 exteriorCandidate = getParent(exteriorCandidate); 576 577 return exteriorCandidate; 578} 579 580 581PRIVATE short 582isInteriorLoop(const treeNode *node) 583{ 584 return 585 !isExterior(node) 586 && node->childCount == 1; 587} 588 589 590PRIVATE short 591isMultiLoop(const treeNode *node) 592{ 593 return 594 !isExterior(node) 595 && node->childCount > 1; 596} 597 598 599PRIVATE int 600getNodeID(const treeNode *node) 601{ 602 if (node != NULL) 603 return node->id; 604 else 605 return -1; 606} 607 608 609PRIVATE char 610getNodeName(const treeNode *node) 611{ 612 /** 613 * @brief cfgMotivBlank 614 * - name of exterior loops and small bulge loops 615 * initialized at cfgGenerateMotivs 616 */ 617 const char cfgMotivBlank = '_'; 618 619 int id = getNodeID(node); 620 621 if (id == -1) 622 623 return cfgMotivBlank; 624 625 int motivId = (id + 33) % 128; 626 while (motivId < 33) 627 628 motivId = (motivId + 33) % 128; 629 char motiv = (char)motivId; 630 631 return motiv; 632} 633 634 635PRIVATE void 636setChild(treeNode *parent, 637 const int index, 638 treeNode *child) 639{ 640 if (0 <= index && index < parent->childCount) 641 642 parent->children[index] = child; 643} 644 645 646/** 647 * @brief treeGetChildCount 648 * - counts the number of children this loop will have in the configtree 649 * @param loopStart 650 * - index of the loops first base 651 * @param pair_table 652 * - the RNA's pairing information 653 * @return 654 * - number of child nodes 655 */ 656PRIVATE int 657treeGetChildCount(const int loopStart, 658 const short *const pair_table) 659{ 660 int childCount = 0; 661 662 int end = pair_table[loopStart]; 663 664 for (int i = loopStart + 1; i < end; ++i) { 665 if (pair_table[i] > i) { 666 /* found new stem */ 667 childCount++; 668 i = pair_table[i]; 669 } 670 } 671 return childCount; 672} 673 674 675/** 676 * @brief createTreeNode 677 * - this method can be referred to as a constructor method for configtree nodes. 678 * @param parent 679 * - parent node (the prior loop), NULL for the root node 680 * @param loopStart 681 * - index of the loops first node, 1 for root node 682 * @param stemStart 683 * - index of the prior stems first node, -1 for root node 684 * @param pair_table 685 * - the RNA's pairing information 686 * @param cfg 687 * - the configuration found in baseInformation for that loop. 688 * NULL for exterior loop (root node) 689 * @return 690 * - an initialized configtree tBaseInformation with set parent, loopStart, cfg, childCount and initialized children array 691 */ 692PRIVATE treeNode * 693createTreeNode(const int id, 694 treeNode *parent, 695 const int loopStart, 696 const int stemStart, 697 const short *const pair_table, 698 config *cfg) 699{ 700 /* allocate children array */ 701 int childCount; 702 703 if (cfg == NULL) 704 childCount = treeGetChildCount(0, pair_table); 705 else 706 childCount = treeGetChildCount(loopStart, pair_table); 707 708 treeNode **children = (childCount > 0) ? (treeNode **)vrna_alloc(childCount * sizeof(treeNode *)) 709 : NULL; 710 711 treeNode *node = (treeNode *)vrna_alloc(1 * sizeof(treeNode)); 712 713 node->id = id; 714 715 node->parent = parent; 716 node->children = children; 717 node->childCount = childCount; 718 719 node->cfg = cfg; 720 node->loop_start = loopStart; 721 node->stem_start = stemStart; 722 723 node->lBox = NULL; 724 node->sBox = NULL; 725 726 return node; 727} 728 729 730/* stem - loop recursion */ 731PRIVATE treeNode * 732treeHandleStem(treeNode *parent, 733 int *nodeID, 734 const int stemStart, 735 const short *const pair_table, 736 const tBaseInformation *baseInformation); 737 738 739/** 740 * @brief treeHandleLoop 741 * - method for configtree construction. 742 * uses recursive calls alternating with treeHandleStem method to get the whole RNA 743 * @param parent 744 * - parent node of the current loop in configtree 745 * @param loopStart 746 * - index of the loop's first base 747 * @param stemStart 748 * - index of the prior stem's first base 749 * @param pairTable 750 * - the RNA's pairing information 751 * @param baseInformation 752 * - array of tBaseInformation annotations (grants config) 753 * @return 754 * - pointer to the subtree (configtree) that has this loop as root 755 */ 756PRIVATE treeNode * 757treeHandleLoop(treeNode *parent, 758 int *nodeID, 759 const int loopStart, 760 const int stemStart, 761 const short *const pair_table, 762 const tBaseInformation *baseInformation) 763{ 764 int addedChildren = 0; 765 766 treeNode *subtree = createTreeNode( 767 *nodeID, 768 parent, 769 loopStart, 770 stemStart, 771 pair_table, 772 baseInformation[loopStart].config); 773 774 int end = pair_table[loopStart]; 775 776 for (int i = loopStart + 1; i < end; ++i) { 777 if (pair_table[i] > i) { 778 /* found new stem */ 779 treeNode *child = treeHandleStem(subtree, nodeID, i, pair_table, baseInformation); 780 child->parent = subtree; 781 setChild(subtree, addedChildren, child); 782 addedChildren++; 783 784 i = pair_table[i]; 785 } 786 } 787 788 return subtree; 789} 790 791 792/** 793 * @brief treeHandleStem 794 * - method for configtree construction. 795 * uses recursive calls alternating with treeHandleLoop method to get the whole RNA 796 * @param parent 797 * - parent node of the current loop in configtree 798 * @param stemStart 799 * - index of the stem's first base 800 * @param pair_table 801 * - the RNA's pairing information 802 * @param baseInformation 803 * - array of tBaseInformation annotations (grants config) 804 * @return 805 * - pointer to the cunsecutive subtree (configtree) that is created from the consecutive loop 806 */ 807PRIVATE treeNode * 808treeHandleStem(treeNode *parent, 809 int *nodeID, 810 const int stemStart, 811 const short *const pair_table, 812 const tBaseInformation *baseInformation) 813{ 814 ++(*nodeID); 815 int i = stemStart; 816 while (baseInformation[i].config == NULL) 817 818 ++i; 819 820 treeNode *child = treeHandleLoop(parent, nodeID, i, stemStart, pair_table, baseInformation); 821 return child; 822} 823 824 825/** 826 * @brief buildBoundingBoxes 827 * @param tree 828 * @param pair_table 829 * @param baseInformation 830 * @param x 831 * @param y 832 * @param bulge 833 * - distance between regular stem and bulge base 834 */ 835PRIVATE void 836buildBoundingBoxes(treeNode *tree, 837 const short *const pair_table, 838 const tBaseInformation *baseInformation, 839 const double *x, 840 const double *y, 841 const double bulge) 842{ 843 short isRoot = (tree->parent == NULL); 844 845 if (!isRoot) { 846 loopBox *lBox = buildLoopBox(tree->loop_start, pair_table, baseInformation, x, y); 847 stemBox *sBox = buildStemBox(tree->stem_start, tree->loop_start, pair_table, x, y, bulge); 848 849 lBox->parent = tree; 850 sBox->parent = tree; 851 852 tree->lBox = lBox; 853 tree->sBox = sBox; 854 855 updateAABB(&(tree->aabb), sBox, lBox); 856 } 857 858 for (int currentChild = 0; currentChild < tree->childCount; currentChild++) { 859 treeNode *child = getChild(tree, currentChild); 860 buildBoundingBoxes(child, pair_table, baseInformation, x, y, bulge); 861 } 862} 863 864 865/* documentation at header file */ 866PRIVATE treeNode * 867buildConfigtree(const short *const pair_table, 868 const tBaseInformation *baseInformation, 869 const double *x, 870 const double *y, 871 const double bulge) 872{ 873 /* create root */ 874 int nodeID = 0; 875 treeNode *root = createTreeNode(nodeID, NULL, 1, -1, pair_table, NULL); 876 877 int addedChildren = 0; 878 int length = pair_table[0]; 879 880 for (int i = 1; i < length; ++i) { 881 if (pair_table[i] > i) { 882 /* found stem */ 883 treeNode *child = treeHandleStem(root, &nodeID, i, pair_table, baseInformation); 884 setChild(root, addedChildren, child); 885 addedChildren++; 886 887 i = pair_table[i]; 888 } 889 } 890 891 buildBoundingBoxes(root, pair_table, baseInformation, x, y, bulge); 892 893 return root; 894} 895 896 897/** 898 * @brief translateBoundingBoxesByVector 899 * - Performs a translation of a whole branch by a given vector. 900 * Used to apply changes in config to the tree and its bounding boxes. 901 * @param tree 902 * - tree that is being translated 903 * @param vector 904 * - translation vector as double array[2] 905 */ 906PRIVATE void 907translateBoundingBoxes(treeNode *tree, 908 const double *vector) 909{ 910 translateStemBox(tree->sBox, vector); 911 translateLoopBox(tree->lBox, vector); 912 updateAABB(&(tree->aabb), tree->sBox, tree->lBox); 913 914 for (int currentChild = 0; currentChild < tree->childCount; currentChild++) 915 916 translateBoundingBoxes(getChild(tree, currentChild), vector); 917} 918 919 920/** 921 * @brief getChildIndex 922 * - gets the index of child node where to find the node with given name. 923 * @param tree 924 * - configtree you want to search in. 925 * @param childID 926 * - ID of childnode you are looking for. 927 * @return 928 * - child index or -1 if tree does not contain such a childnode. 929 */ 930PRIVATE int 931getChildIndex(const treeNode *tree, 932 const int childID) 933{ 934 /* check if there are further nodes to check */ 935 int childIndex = tree->childCount - 1; 936 937 for (int currentChild = 0; 938 currentChild < tree->childCount; 939 ++currentChild) { 940 treeNode *child = getChild(tree, currentChild); 941 942 if (getNodeID(child) > childID) { 943 childIndex = currentChild - 1; 944 break; 945 } 946 } 947 948 return childIndex; 949} 950 951 952/** 953 * @brief getChildAngle 954 * - Calculates the clockwise angle of a given child node (given by name) at a loop. 955 * This child needs to be a direct child node 956 * The rotation angle of its center node will be calculated. 957 * @param parentNode 958 * - tree node acting as parent loop 959 * @param childNode 960 * - child node of which you want to know the angle 961 * @return 962 * - angle of child node 963 * the resulting angle might be smaller than 0° or greater than 360° 964 */ 965PRIVATE double 966getChildAngle(const treeNode *parentNode, 967 const treeNode *childNode) 968{ 969 double parentLoopCenter[2] = { 970 parentNode->lBox->c[0], parentNode->lBox->c[1] 971 }; 972 double parentStemCenter[2] = { 973 parentNode->sBox->c[0], parentNode->sBox->c[1] 974 }; 975 double parentLoopStemVector[2]; 976 977 vector(parentLoopCenter, parentStemCenter, parentLoopStemVector); 978 979 double childLoopCenter[2] = { 980 childNode->lBox->c[0], childNode->lBox->c[1] 981 }; 982 double angle = anglePtPtPt2D(parentStemCenter, parentLoopCenter, childLoopCenter); 983 984 if (!isToTheRightPointVector(parentLoopCenter, parentLoopStemVector, childLoopCenter)) 985 986 angle = MATH_TWO_PI - angle; 987 988 return angle; 989} 990 991 992/** 993 * @brief getChildAngleByIndex 994 * - Calculates the clockwise angle of a given child node (given by name) at a loop. 995 * This child needs to be a direct child node 996 * The rotation angle of its center node will be calculated. 997 * @param parentNode 998 * - tree node acting as parent loop 999 * @param childIndex 1000 * - index of child node of which you want to know the angle 1001 * @return 1002 * - angle of child node 1003 * the resulting angle might be smaller than 0° or greater than 360° 1004 */ 1005PRIVATE double 1006getChildAngleByIndex(const treeNode *parentNode, 1007 const int childIndex) 1008{ 1009 return getChildAngle(parentNode, getChild(parentNode, childIndex)); 1010} 1011 1012 1013/** 1014 * @brief getLoopCenter 1015 * - Getter for the center coordinates of a tree node's loop. 1016 * @param node 1017 * - your tree node 1018 * @param p 1019 * - double[2] return value for the loop's center coordinates 1020 */ 1021PRIVATE void 1022getLoopCenter(const treeNode *node, 1023 double p[2]) 1024{ 1025 getLBoxCenter(node->lBox, p); 1026} 1027 1028 1029/** 1030 * @brief getStemCenter 1031 * - Getter for the center coordinates of a tree node's stem. 1032 * @param node 1033 * - your tree node 1034 * @param p 1035 * - double[2] return value for the stem's center coordinates 1036 */ 1037PRIVATE void 1038getStemCenter(const treeNode *node, 1039 double p[2]) 1040{ 1041 getSBoxCenter(node->sBox, p); 1042} 1043 1044 1045/** 1046 * @brief getChildNode 1047 * - searches for the node with given childname in a configtree. 1048 * @param tree 1049 * - configtree you want to search in. 1050 * @param childID 1051 * - ID of childnode you are looking for. 1052 * @return 1053 * - ptr to node or NULL if tree does not contain such a childnode. 1054 */ 1055PRIVATE treeNode * 1056getChildNode(treeNode *tree, 1057 const int childID) 1058{ 1059 short treeIsRoot = isExterior(tree); 1060 1061 /* check if this is the wanted node */ 1062 if (!treeIsRoot) { 1063 if (getNodeID(tree) == childID) 1064 1065 return tree; 1066 } 1067 1068 /* get index of next child on our path */ 1069 treeNode *child = getChild(tree, getChildIndex(tree, childID)); 1070 1071 if (child == NULL) 1072 return NULL; 1073 else 1074 return getChildNode(child, childID); 1075} 1076 1077 1078PRIVATE treeNode * 1079getChild(const treeNode *node, 1080 const int index) 1081{ 1082 if (node == NULL) 1083 return NULL; 1084 else if (index < 0) 1085 return NULL; 1086 else if (index >= node->childCount) 1087 return NULL; 1088 else 1089 return node->children[index]; 1090} 1091 1092 1093PRIVATE treeNode * 1094getParent(const treeNode *node) 1095{ 1096 if (node == NULL) 1097 return NULL; 1098 else 1099 return node->parent; 1100} 1101 1102 1103#endif 1104