1 /* 2 * RectilinearTreeLayout.java 3 * 4 * Copyright (C) 2006-2014 Andrew Rambaut 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU General Public License 8 * as published by the Free Software Foundation; either version 2 9 * of the License, or (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 19 */ 20 21 package figtree.treeviewer.treelayouts; 22 23 import jebl.evolution.graphs.Node; 24 import jebl.evolution.trees.RootedTree; 25 26 import java.awt.*; 27 import java.awt.geom.*; 28 import java.util.List; 29 30 /** 31 * @author Andrew Rambaut 32 * @version $Id$ 33 * 34 * $HeadURL$ 35 * 36 * $LastChangedBy$ 37 * $LastChangedDate$ 38 * $LastChangedRevision$ 39 */ 40 public class RectilinearTreeLayout extends AbstractTreeLayout { 41 42 private double curvature = 0.0; 43 private boolean alignTipLabels = false; 44 45 private double fishEye = 0.0; 46 private double pointOfInterest = 0.5; 47 private int tipCount = 0; 48 49 private double rootLengthProportion = 0.01; 50 51 private double yPosition; 52 private double yIncrement; 53 54 private double maxXPosition; 55 56 getXAxisType()57 public AxisType getXAxisType() { 58 return AxisType.CONTINUOUS; 59 } 60 getYAxisType()61 public AxisType getYAxisType() { 62 return AxisType.DISCRETE; 63 } 64 isShowingRootBranch()65 public boolean isShowingRootBranch() { 66 return true; 67 } 68 maintainAspectRatio()69 public boolean maintainAspectRatio() { 70 return false; 71 } 72 getRootLengthProportion()73 public double getRootLengthProportion() { 74 return rootLengthProportion; 75 } 76 setRootLengthProportion(double rootLengthProportion)77 public void setRootLengthProportion(double rootLengthProportion) { 78 this.rootLengthProportion = rootLengthProportion; 79 fireTreeLayoutChanged(); 80 } 81 getHeightOfPoint(Point2D point)82 public double getHeightOfPoint(Point2D point) { 83 return point.getX(); 84 } 85 getAxisLine(double height)86 public Shape getAxisLine(double height) { 87 double x = height; 88 double y1 = 0.0; 89 double y2 = 1.0; 90 return new Line2D.Double(x, y1, x, y2); 91 } 92 getHeightArea(double height1, double height2)93 public Shape getHeightArea(double height1, double height2) { 94 double x = height1; 95 double y = 0.0; 96 double w = Math.abs(height2 - height1); 97 double h = 1.0; 98 return new Rectangle2D.Double(x, y, w, h); 99 } 100 isAlignTipLabels()101 public boolean isAlignTipLabels() { 102 return alignTipLabels; 103 } 104 getCurvature()105 public double getCurvature() { 106 return curvature; 107 } 108 getFishEye()109 public double getFishEye() { 110 return fishEye; 111 } 112 getPointOfInterest()113 public double getPointOfInterest() { 114 return pointOfInterest; 115 } 116 setAlignTipLabels(boolean alignTipLabels)117 public void setAlignTipLabels(boolean alignTipLabels) { 118 this.alignTipLabels = alignTipLabels; 119 fireTreeLayoutChanged(); 120 } 121 setCurvature(double curvature)122 public void setCurvature(double curvature) { 123 this.curvature = curvature; 124 fireTreeLayoutChanged(); 125 } 126 setFishEye(double fishEye)127 public void setFishEye(double fishEye) { 128 this.fishEye = fishEye; 129 fireTreeLayoutChanged(); 130 } 131 setPointOfInterest(double x, double y)132 public void setPointOfInterest(double x, double y) { 133 this.pointOfInterest = y; 134 fireTreeLayoutChanged(); 135 } 136 isShowingColouring()137 public boolean isShowingColouring() { 138 return (branchColouringAttribute != null && curvature == 0.0); 139 } 140 layout(RootedTree tree, TreeLayoutCache cache)141 public void layout(RootedTree tree, TreeLayoutCache cache) { 142 143 cache.clear(); 144 145 maxXPosition = 0.0; 146 147 yPosition = 0.0; 148 tipCount = tree.getExternalNodes().size(); 149 yIncrement = 1.0 / (tipCount - 1); 150 151 Node root = tree.getRootNode(); 152 setRootLength(rootLengthProportion * tree.getHeight(root)); 153 154 maxXPosition = 0.0; 155 getMaxXPosition(tree, root, getRootLength()); 156 157 Point2D rootPoint = constructNode(tree, root, 0.0, getRootLength(), cache); 158 159 constructNodeAreas(tree, root, new Area(), cache); 160 161 // construct a root branch line 162 double ty = transformY(rootPoint.getY()); 163 Line2D line = new Line2D.Double(0.0, ty, rootPoint.getX(), ty); 164 165 // add the line to the map of branch paths 166 cache.branchPaths.put(root, line); 167 168 } 169 constructNode(final RootedTree tree, final Node node, final double xParent, final double xPosition, TreeLayoutCache cache)170 private Point2D constructNode(final RootedTree tree, final Node node, final double xParent, final double xPosition, TreeLayoutCache cache) { 171 172 Point2D nodePoint; 173 174 if (hilightAttributeName != null && node.getAttribute(hilightAttributeName) != null) { 175 constructHilight(tree, node, xParent, xPosition, cache); 176 } 177 178 if (!tree.isExternal(node)) { 179 180 if (collapsedAttributeName != null && node.getAttribute(collapsedAttributeName) != null) { 181 nodePoint = constructCollapsedNode(tree, node, xPosition, cache); 182 } else if (cartoonAttributeName != null && node.getAttribute(cartoonAttributeName) != null) { 183 nodePoint = constructCartoonNode(tree, node, xPosition, cache); 184 } else { 185 186 double yPos = 0.0; 187 188 List<Node> children = tree.getChildren(node); 189 190 boolean rotate = false; 191 if (node.getAttribute("!rotate") != null && 192 ((Boolean)node.getAttribute("!rotate"))) { 193 rotate = true; 194 } 195 196 for (int i = 0; i < children.size(); i++) { 197 int index = i; 198 if (rotate) { 199 index = children.size() - i - 1; 200 } 201 Node child = children.get(index); 202 double length = tree.getLength(child); 203 Point2D childPoint = constructNode(tree, child, xPosition, xPosition + length, cache); 204 yPos += childPoint.getY(); 205 } 206 207 // the y-position of the node is the average of the child nodes 208 yPos /= children.size(); 209 210 nodePoint = new Point2D.Double(xPosition, yPos); 211 final double ty = transformY(yPos); 212 213 // start point 214 final float x0 = (float) nodePoint.getX(); 215 final float y0 = (float) ty; 216 217 for (Node child : children) { 218 219 Point2D childPoint = cache.nodePoints.get(child); 220 221 GeneralPath branchPath = new GeneralPath(); 222 223 // end point 224 final float x1 = (float) childPoint.getX(); 225 final float y1 = (float) transformY(childPoint.getY()); 226 227 if (curvature == 0.0) { 228 Object[] colouring = null; 229 if (branchColouringAttribute != null) { 230 colouring = (Object[])child.getAttribute(branchColouringAttribute); 231 } 232 if (colouring != null) { 233 // If there is a colouring, then we break the path up into 234 // segments. This should allow us to iterate along the segments 235 // and colour them as we draw them. 236 237 float nodeHeight = (float) tree.getHeight(node); 238 float childHeight = (float) tree.getHeight(child); 239 240 // to help this, we are going to draw the branch backwards 241 branchPath.moveTo(x1, y1); 242 float x = x1; 243 for (int i = 0; i < colouring.length - 1; i+=2) { 244 // float height = ((Number)colouring[i+1]).floatValue(); 245 // float p = (height - childHeight) / (nodeHeight - childHeight); 246 float interval = ((Number)colouring[i+1]).floatValue(); 247 float p = interval / (nodeHeight - childHeight); 248 x -= ((x1 - x0) * p); 249 branchPath.lineTo(x, y1); 250 } 251 branchPath.lineTo(x0, y1); 252 branchPath.lineTo(x0, y0); 253 } else { 254 branchPath.moveTo(x1, y1); 255 branchPath.lineTo(x0, y1); 256 branchPath.lineTo(x0, y0); 257 } 258 } else if (curvature == 1.0) { 259 // The extreme is to use a triangular look 260 branchPath.moveTo(x0, y0); 261 branchPath.lineTo(x1, y1); 262 } else { 263 // if the curvature is on then we simply don't 264 // do tree colouring - I just can't be bothered to 265 // implement it (and it would probably be confusing anyway). 266 float x2 = x1 - ((x1 - x0) * (float) (1.0 - curvature)); 267 float y2 = y0 + ((y1 - y0) * (float) (1.0 - curvature)); 268 269 branchPath.moveTo(x1, y1); 270 branchPath.lineTo(x2, y1); 271 branchPath.quadTo(x0, y1, x0, y2); 272 branchPath.lineTo(x0, y0); 273 } 274 275 // add the branchPath to the map of branch paths 276 cache.branchPaths.put(child, branchPath); 277 278 double x3 = (nodePoint.getX() + childPoint.getX()) / 2; 279 Line2D branchLabelPath = new Line2D.Double( 280 x3 - 1.0, y1, 281 x3 + 1.0, y1); 282 283 cache.branchLabelPaths.put(child, branchLabelPath); 284 } 285 286 Line2D nodeLabelPath = new Line2D.Double( 287 nodePoint.getX(), ty, 288 nodePoint.getX() + 1.0, ty); 289 290 cache.nodeLabelPaths.put(node, nodeLabelPath); 291 292 Line2D nodeShapePath = new Line2D.Double( 293 nodePoint.getX(), ty, 294 nodePoint.getX() - 1.0, ty); 295 cache.nodeShapePaths.put(node, nodeShapePath); 296 } 297 } else { 298 299 nodePoint = new Point2D.Double(xPosition, yPosition); 300 double ty = transformY(yPosition); 301 302 Line2D tipLabelPath; 303 304 if (alignTipLabels) { 305 306 tipLabelPath = new Line2D.Double( 307 maxXPosition, ty, 308 maxXPosition + 1.0, ty); 309 310 Line2D calloutPath = new Line2D.Double( 311 nodePoint.getX(), ty, 312 maxXPosition, ty); 313 314 cache.calloutPaths.put(node, calloutPath); 315 316 } else { 317 tipLabelPath = new Line2D.Double( 318 nodePoint.getX(), ty, 319 nodePoint.getX() + 1.0, ty); 320 321 } 322 323 cache.tipLabelPaths.put(node, tipLabelPath); 324 325 Line2D nodeShapePath = new Line2D.Double( 326 nodePoint.getX(), ty, 327 nodePoint.getX() - 1.0, ty); 328 cache.nodeShapePaths.put(node, nodeShapePath); 329 330 yPosition += yIncrement; 331 332 } 333 334 // add the node point to the map of node points 335 cache.nodePoints.put(node, nodePoint); 336 337 return nodePoint; 338 } 339 constructNodeAreas(final RootedTree tree, final Node node, final Area parentNodeArea, TreeLayoutCache cache)340 private void constructNodeAreas(final RootedTree tree, final Node node, final Area parentNodeArea, TreeLayoutCache cache) { 341 342 if (!tree.isExternal(node) && 343 (collapsedAttributeName == null || node.getAttribute(collapsedAttributeName) == null) && 344 (cartoonAttributeName == null || node.getAttribute(cartoonAttributeName) == null)) { 345 346 List<Node> children = tree.getChildren(node); 347 348 boolean rotate = false; 349 if (node.getAttribute("!rotate") != null && 350 ((Boolean)node.getAttribute("!rotate"))) { 351 rotate = true; 352 } 353 354 int index = (rotate ? children.size() - 1 : 0); 355 Node child1 = children.get(index); 356 Area childArea1 = new Area(); 357 358 constructNodeAreas(tree, child1, childArea1, cache); 359 360 Rectangle2D branchBounds1 = cache.getBranchPath(child1).getBounds2D(); 361 362 index = (rotate ? 0 : children.size() - 1); 363 Node child2 = children.get(index); 364 Area childArea2 = new Area(); 365 constructNodeAreas(tree, child2, childArea2, cache); 366 367 Rectangle2D branchBounds2 = cache.getBranchPath(child2).getBounds2D(); 368 369 GeneralPath nodePath = new GeneralPath(); 370 371 // start point 372 final float x0 = (float) branchBounds1.getX(); 373 final float y0 = (float) (branchBounds1.getY() + branchBounds1.getHeight()); 374 nodePath.moveTo(x0, y0); 375 376 if (curvature == 0.0) { 377 378 final float y1 = (float) branchBounds1.getY(); 379 nodePath.lineTo(x0, y1); 380 381 nodePath.lineTo((float)maxXPosition, y1); 382 383 final float y2 = (float) (branchBounds2.getY() + branchBounds2.getHeight()); 384 nodePath.lineTo((float)maxXPosition, y2); 385 386 nodePath.lineTo(x0, y2); 387 388 } else if (curvature == 1.0) { 389 // The extreme is to use a triangular look 390 391 final float x1 = (float) (branchBounds1.getX() + branchBounds1.getWidth()); 392 final float y1 = (float) branchBounds1.getY(); 393 nodePath.lineTo(x1, y1); 394 395 nodePath.lineTo((float)maxXPosition, y1); 396 397 final float y2 = (float) (branchBounds2.getY() + branchBounds2.getHeight()); 398 nodePath.lineTo((float)maxXPosition, y2); 399 400 final float x2 = (float) (branchBounds2.getX() + branchBounds2.getWidth()); 401 nodePath.lineTo(x2, y2); 402 } else { 403 final float x1 = (float) (branchBounds1.getX() + branchBounds1.getWidth()); 404 final float y1 = (float) branchBounds1.getY(); 405 406 float x2 = x1 - ((x1 - x0) * (float) (1.0 - curvature)); 407 float y2 = y0 - ((y0 - y1) * (float) (1.0 - curvature)); 408 409 nodePath.lineTo(x0, y2); 410 nodePath.quadTo(x0, y1, x2, y1); 411 412 nodePath.lineTo((float)maxXPosition, y1); 413 414 final float y3 = (float) (branchBounds2.getY() + branchBounds2.getHeight()); 415 nodePath.lineTo((float)maxXPosition, y3); 416 417 final float x3 = (float) (branchBounds2.getX() + branchBounds2.getWidth()); 418 final float x4 = x3 - ((x3 - x0) * (float) (1.0 - curvature)); 419 final float y4 = y0 + ((y3 - y0) * (float) (1.0 - curvature)); 420 421 nodePath.lineTo(x4, y3); 422 nodePath.quadTo(x0, y3, x0, y4); 423 } 424 425 nodePath.lineTo(x0, y0); 426 nodePath.closePath(); 427 428 Area nodeArea = new Area(nodePath); 429 430 parentNodeArea.add(nodeArea); 431 parentNodeArea.add(childArea1); 432 parentNodeArea.add(childArea2); 433 434 nodeArea.subtract(childArea1); 435 nodeArea.subtract(childArea2); 436 437 cache.nodeAreas.put(node, nodeArea); 438 } 439 } 440 constructCartoonNode(RootedTree tree, Node node, double xPosition, TreeLayoutCache cache)441 private Point2D constructCartoonNode(RootedTree tree, Node node, double xPosition, TreeLayoutCache cache) { 442 443 Point2D nodePoint; 444 445 Object[] values = (Object[])node.getAttribute(cartoonAttributeName); 446 int tipCount = (Integer)values[0]; 447 double tipHeight = (Double)values[1]; 448 double height = tree.getHeight(node); 449 double maxXPos = xPosition + height - tipHeight; 450 451 double minYPos = yPosition; 452 yPosition += yIncrement * (tipCount - 1); 453 double maxYPos = yPosition; 454 yPosition += yIncrement; 455 456 // the y-position of the node is the average of the child nodes 457 double yPos = (maxYPos + minYPos) / 2; 458 459 nodePoint = new Point2D.Double(xPosition, yPos); 460 461 GeneralPath collapsedShape = new GeneralPath(); 462 463 // start point 464 float x0 = (float)nodePoint.getX(); 465 float y0 = (float)transformY(nodePoint.getY()); 466 467 // end point 468 float x1 = (float)maxXPos; 469 float y1 = (float)transformY(minYPos); 470 471 float y2 = (float)transformY(maxYPos); 472 473 collapsedShape.moveTo(x0, y0); 474 collapsedShape.lineTo(x1, y1); 475 collapsedShape.lineTo(x1, y2); 476 collapsedShape.closePath(); 477 478 // add the collapsedShape to the map of branch paths 479 cache.collapsedShapes.put(node, collapsedShape); 480 481 Line2D nodeLabelPath = new Line2D.Double( 482 nodePoint.getX(), y0, 483 nodePoint.getX() + 1.0, y0); 484 485 cache.nodeLabelPaths.put(node, nodeLabelPath); 486 487 Line2D nodeBarPath = new Line2D.Double( 488 nodePoint.getX(), y0, 489 nodePoint.getX() - 1.0, y0); 490 491 cache.nodeShapePaths.put(node, nodeBarPath); 492 493 if (showingCartoonTipLabels) { 494 constructCartoonTipLabelPaths(tree, node, maxXPos, new double[] { minYPos }, cache); 495 } 496 497 return nodePoint; 498 } 499 constructCartoonTipLabelPaths(RootedTree tree, Node node, double xPosition, double[] yPosition, TreeLayoutCache cache)500 private void constructCartoonTipLabelPaths(RootedTree tree, Node node, 501 double xPosition, double[] yPosition, 502 TreeLayoutCache cache) { 503 504 if (!tree.isExternal(node)) { 505 for (Node child : tree.getChildren(node)) { 506 constructCartoonTipLabelPaths(tree, child, xPosition, yPosition, cache); 507 } 508 } else { 509 510 Point2D nodePoint = new Point2D.Double(xPosition, yPosition[0]); 511 double x0 = nodePoint.getX(); 512 double y0 = transformY(nodePoint.getY()); 513 514 Line2D tipLabelPath; 515 516 if (alignTipLabels) { 517 518 tipLabelPath = new Line2D.Double(maxXPosition, y0, maxXPosition + 1.0, y0); 519 520 Line2D calloutPath = new Line2D.Double(x0, y0, maxXPosition, y0); 521 522 cache.calloutPaths.put(node, calloutPath); 523 524 } else { 525 tipLabelPath = new Line2D.Double(x0, y0, x0 + 1.0, y0); 526 527 } 528 529 cache.tipLabelPaths.put(node, tipLabelPath); 530 531 yPosition[0] += yIncrement; 532 533 } 534 } 535 constructCollapsedNode(RootedTree tree, Node node, double xPosition, TreeLayoutCache cache)536 private Point2D constructCollapsedNode(RootedTree tree, Node node, double xPosition, TreeLayoutCache cache) { 537 538 Point2D nodePoint; 539 540 Object[] values = (Object[])node.getAttribute(collapsedAttributeName); 541 double tipHeight = (Double)values[1]; 542 double height = tree.getHeight(node); 543 double maxXPos = xPosition + height - tipHeight; 544 545 double minYPos = yPosition - (yIncrement * 0.5); 546 double maxYPos = minYPos + yIncrement; 547 yPosition += yIncrement; 548 549 // the y-position of the node is the average of the child nodes 550 double yPos = (maxYPos + minYPos) / 2; 551 552 nodePoint = new Point2D.Double(xPosition, yPos); 553 double ty = transformY(yPos); 554 555 GeneralPath collapsedShape = new GeneralPath(); 556 557 // start point 558 float x0 = (float)nodePoint.getX(); 559 float y0 = (float)ty; 560 561 // end point 562 float x1 = (float)maxXPos; 563 float y1 = (float)transformY(minYPos); 564 565 float y2 = (float)transformY(maxYPos); 566 567 collapsedShape.moveTo(x0, y0); 568 collapsedShape.lineTo(x1, y1); 569 collapsedShape.lineTo(x1, y2); 570 collapsedShape.closePath(); 571 572 // add the collapsedShape to the map of branch paths 573 cache.collapsedShapes.put(node, collapsedShape); 574 575 Line2D nodeLabelPath = new Line2D.Double(xPosition, ty, xPosition + 1.0, ty); 576 577 cache.nodeLabelPaths.put(node, nodeLabelPath); 578 579 Line2D nodeBarPath = new Line2D.Double(xPosition, ty, xPosition - 1.0, ty); 580 581 cache.nodeShapePaths.put(node, nodeBarPath); 582 583 Line2D tipLabelPath; 584 585 if (alignTipLabels) { 586 587 tipLabelPath = new Line2D.Double( 588 maxXPosition, ty, 589 maxXPosition + 1.0, ty); 590 591 Line2D calloutPath = new Line2D.Double( 592 maxXPos, ty, 593 maxXPosition, ty); 594 595 cache.calloutPaths.put(node, calloutPath); 596 597 } else { 598 tipLabelPath = new Line2D.Double(maxXPos, ty, maxXPos + 1.0, ty); 599 } 600 601 cache.tipLabelPaths.put(node, tipLabelPath); 602 603 return nodePoint; 604 } 605 constructHilight(RootedTree tree, Node node, double xParent, double xPosition, TreeLayoutCache cache)606 private void constructHilight(RootedTree tree, Node node, double xParent, double xPosition, TreeLayoutCache cache) { 607 608 Object[] values = (Object[])node.getAttribute(hilightAttributeName); 609 int tipCount = (Integer)values[0]; 610 double tipHeight = (Double)values[1]; 611 double height = tree.getHeight(node); 612 613 GeneralPath hilightShape = new GeneralPath(); 614 615 float x0 = (float)((xPosition + xParent) / 2.0); 616 float x1 = (float)(xPosition + height /*- tipHeight*/); 617 double tmp = yPosition - (yIncrement / 2); 618 float y0 = (float)transformY(tmp); 619 float y1 = (float)transformY(tmp + (yIncrement * tipCount)); 620 621 hilightShape.moveTo(x0, y0); 622 hilightShape.lineTo(x1, y0); 623 hilightShape.lineTo(x1, y1); 624 hilightShape.lineTo(x0, y1); 625 hilightShape.closePath(); 626 627 // add the collapsedShape to the map of branch paths 628 cache.hilightNodes.add(node); 629 cache.hilightShapes.put(node, hilightShape); 630 } 631 getMaxXPosition(RootedTree tree, Node node, double xPosition)632 private void getMaxXPosition(RootedTree tree, Node node, double xPosition) { 633 634 if (!tree.isExternal(node)) { 635 636 List<Node> children = tree.getChildren(node); 637 638 for (Node child : children) { 639 double length = tree.getLength(child); 640 getMaxXPosition(tree, child, xPosition + length); 641 } 642 643 } else { 644 if (xPosition > maxXPosition) { 645 maxXPosition = xPosition; 646 } 647 } 648 } 649 transformY(double y)650 private double transformY(double y) { 651 if (fishEye == 0.0) { 652 return y; 653 } 654 655 double scale = 1.0 / (fishEye * tipCount); 656 double dist = pointOfInterest - y; 657 double min = 1.0 - (pointOfInterest / (scale + pointOfInterest)); 658 double max = 1.0 - ((pointOfInterest - 1.0) / (scale - (pointOfInterest - 1.0))); 659 660 double c = 1.0 - (dist < 0 ? (dist / (scale - dist)) : (dist / (scale + dist))); 661 662 return (c - min) / (max - min); 663 } 664 665 666 }