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 }