001 /*--------------------------------------------------------------------------+
002 $Id: StripeTreeMapAlgorithm.java 26931 2010-03-17 14:53:13Z besenreu $
003 | |
004 | Copyright 2005-2010 Technische Universitaet Muenchen |
005 | |
006 | Licensed under the Apache License, Version 2.0 (the "License"); |
007 | you may not use this file except in compliance with the License. |
008 | You may obtain a copy of the License at |
009 | |
010 | http://www.apache.org/licenses/LICENSE-2.0 |
011 | |
012 | Unless required by applicable law or agreed to in writing, software |
013 | distributed under the License is distributed on an "AS IS" BASIS, |
014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015 | See the License for the specific language governing permissions and |
016 | limitations under the License. |
017 +--------------------------------------------------------------------------*/
018 package edu.tum.cs.commons.treemap;
019
020 import java.awt.geom.Rectangle2D;
021 import java.util.ArrayList;
022 import java.util.List;
023
024
025 /**
026 * The strip layout algorithm adapted from Bederson, Shneiderman, Wattenberg:
027 * "Ordered and Quantum Treemaps".
028 * <p>
029 * This is useful as it tries to minimize the aspect ratio of the generated
030 * squares while maintaining the original order.
031 *
032 * @author Benjamin Hummel
033 * @author $Author: besenreu $
034 * @version $Rev: 26931 $
035 * @levd.rating GREEN Hash: 1B6839F786A1CE254964E4259A7B321C
036 */
037 public class StripeTreeMapAlgorithm implements ITreeMapLayoutAlgorithm {
038
039 /** {@inheritDoc} */
040 public <T> void layout(ITreeMapNode<T> tree, Rectangle2D target) {
041 tree.setLayoutRectangle(target);
042 layoutChildren(tree);
043 }
044
045 /** Layouts the children of the given node (if it has any). */
046 private <T> void layoutChildren(ITreeMapNode<T> node) {
047 if (node.getChildren().isEmpty()) {
048 return;
049 }
050 Rectangle2D rect = node.getLayoutRectangle();
051 double scale = rect.getWidth() * rect.getHeight() / node.getArea();
052
053 double layoutX = rect.getMinX();
054 double lastX = 0;
055 List<ITreeMapNode<T>> l = new ArrayList<ITreeMapNode<T>>();
056 List<ITreeMapNode<T>> lastList = new ArrayList<ITreeMapNode<T>>();
057 for (ITreeMapNode<T> child : node.getChildren()) {
058 double oldAspect = calcAvgAspect(l, rect.getHeight(), scale);
059 l.add(child);
060 double newAspect = calcAvgAspect(l, rect.getHeight(), scale);
061
062 if (oldAspect < newAspect) {
063 l.remove(l.size() - 1);
064 lastX = layoutX;
065 lastList.clear();
066 lastList.addAll(l);
067
068 layoutX += layoutList(l, rect.getHeight(), layoutX, rect
069 .getMinY(), scale);
070 l.clear();
071 l.add(child);
072 }
073 }
074
075 // last list might be too small, so potentially merge with previous one
076 lastList.addAll(l);
077 if (calcAvgAspect(lastList, rect.getHeight(), scale) < calcAvgAspect(l,
078 rect.getHeight(), scale)) {
079 layoutList(lastList, rect.getHeight(), lastX, rect.getMinY(), scale);
080 } else {
081 layoutList(l, rect.getHeight(), layoutX, rect.getMinY(), scale);
082 }
083 }
084
085 /**
086 * Calculates the average aspect ratio of the given list of nodes if the
087 * provided height may be used.
088 */
089 private <T> double calcAvgAspect(List<ITreeMapNode<T>> l,
090 double layoutHeight, double areaScale) {
091 if (l.isEmpty()) {
092 return 1e8;
093 }
094 double area = 0;
095 for (ITreeMapNode<T> node : l) {
096 area += node.getArea();
097 }
098 double layoutWidth = area * areaScale / layoutHeight;
099 double aspectSum = 0;
100 for (ITreeMapNode<T> node : l) {
101 double localHeight = node.getArea() * areaScale / layoutWidth;
102 double localAspect = Math.max(layoutWidth / localHeight,
103 localHeight / layoutWidth);
104 aspectSum += localAspect;
105 }
106 return aspectSum / l.size();
107 }
108
109 /**
110 * Layout the given list of nodes in one column.
111 *
112 * @param l
113 * the list of nodes.
114 * @param layoutHeight
115 * the height of the column.
116 * @param layoutX
117 * the x start value.
118 * @param layoutY
119 * the y start value.
120 * @param areaScale
121 * the scale factor used to convert from node area to layout
122 * area.
123 * @return the layout width of the column.
124 */
125 private <T> double layoutList(List<ITreeMapNode<T>> l, double layoutHeight,
126 double layoutX, double layoutY, double areaScale) {
127 double nodeArea = 0;
128 for (ITreeMapNode<T> node : l) {
129 nodeArea += node.getArea();
130 }
131 double layoutWidth = nodeArea * areaScale / layoutHeight;
132 for (ITreeMapNode<T> node : l) {
133 double nodeHeight = node.getArea() * areaScale / layoutWidth;
134 node.setLayoutRectangle(new Rectangle2D.Double(layoutX, layoutY,
135 layoutWidth, nodeHeight));
136 layoutY += nodeHeight;
137 layoutChildren(node);
138 }
139 return layoutWidth;
140 }
141 }