001: /*
002: * $Header: /cvs/j3dfly/J3dEditor/src/org/jdesktop/j3dedit/treelayout/CircularTreeLayout.java,v 1.1 2005/04/20 22:21:31 paulby Exp $
003: *
004: * Sun Public License Notice
005: *
006: * The contents of this file are subject to the Sun Public License Version
007: * 1.0 (the "License"). You may not use this file except in compliance with
008: * the License. A copy of the License is available at http://www.sun.com/
009: *
010: * The Original Code is the Java 3D(tm) Scene Graph Editor.
011: * The Initial Developer of the Original Code is Paul Byrne.
012: * Portions created by Paul Byrne are Copyright (C) 2002.
013: * All Rights Reserved.
014: *
015: * Contributor(s): Paul Byrne.
016: *
017: **/
018: package org.jdesktop.j3dedit.treelayout;
019:
020: import java.awt.*;
021: import java.util.ArrayList;
022:
023: /**
024: * Generic algorithm for computing the layout of a tree who's nodes
025: * implement the @see TreeNode interface in a circular form
026: *
027: * @author Paul Byrne
028: * @version $Id: CircularTreeLayout.java,v 1.1 2005/04/20 22:21:31 paulby Exp $
029: */
030: public class CircularTreeLayout extends TreeLayout {
031:
032: private ArrayList levelSizes = new ArrayList();
033: private double[] levelMaxAngles;
034:
035: private int levelSpacing = 50; // Distance between each level
036:
037: /**
038: * Calculate the number of nodes in each level of the tree
039: * Also note in each Group the maximum level of all children
040: */
041: private int calculateLevelSizes(TreeNode node, int level) {
042: int depth = level - 1;
043: if (level + 1 > levelSizes.size()) {
044: levelSizes.add(new Integer(node.numChildren()));
045: } else {
046: Integer integer = (Integer) levelSizes.get(level);
047: int add = integer.intValue() + node.numChildren();
048: levelSizes.set(level, new Integer(add));
049: }
050:
051: if (node.numChildren() > 0)
052: depth = level;
053:
054: int childLevels;
055: for (int i = 0; i < node.numChildren(); i++) {
056: childLevels = calculateLevelSizes(node.getChild(i),
057: level + 1);
058: if (childLevels > depth)
059: depth = childLevels;
060: }
061:
062: node.setLayoutData(new CircularTreeLayoutData());
063: ((CircularTreeLayoutData) node.getLayoutData()).childDepth = depth;
064:
065: return depth;
066: }
067:
068: public TreeNode doPick(TreeNode root, int x, int y) {
069: TreeNode ret = null;
070:
071: if (root.picked(x, y))
072: ret = root;
073:
074: for (int i = 0; i < root.numChildren() && ret == null; i++)
075: ret = doPick(root.getChild(i), x, y);
076:
077: return ret;
078: }
079:
080: public void doLayout(TreeNode root) {
081:
082: // Compute number of nodes in each level of the tree
083: levelSizes.clear();
084: levelSizes.add(new Integer(1)); // Level 0 (root) has one node
085: calculateLevelSizes(root, 1);
086:
087: int index = 0;
088: int largestLevel = 0;
089: for (int i = 0; i < levelSizes.size(); i++) {
090: if (((Integer) levelSizes.get(i)).intValue() > largestLevel) {
091: index = i;
092: largestLevel = ((Integer) levelSizes.get(i)).intValue();
093: }
094: }
095:
096: levelMaxAngles = new double[levelSizes.size()];
097: for (int i = 0; i < levelMaxAngles.length; i++)
098: levelMaxAngles[i] = 0;
099:
100: double angle = 2 * Math.PI
101: / ((Integer) levelSizes.get(index)).intValue();
102:
103: /**
104: * Radial distance between each level
105: */
106: double levelRadius = (root.getPreferredSize().width / Math
107: .tan(angle))
108: / index;
109: levelRadius = Math.abs(levelRadius);
110:
111: if (levelRadius < levelSpacing)
112: levelRadius = levelSpacing;
113:
114: //System.out.println( "Angle "+Math.toDegrees( angle )+" levelRadius "+levelRadius);
115:
116: Point computedPos = new Point();
117: computedPos.x = (int) (levelRadius * levelSizes.size())
118: - root.getMinimumSize().width / 2;
119: computedPos.y = (int) (levelRadius * levelSizes.size())
120: - root.getMinimumSize().height / 2;
121: if (!(root.getLink() instanceof CircularTreeLink))
122: root.setLink(new CircularTreeLink(root, levelSpacing));
123:
124: root.setComputedPosition(computedPos);
125:
126: //Rectangle subtreeSize = new Rectangle( 0,0, (int)(levelRadius * levelSizes.size()*2), (int)(levelRadius * levelSizes.size()*2) );
127: //root.setSubtreeSize( subtreeSize );
128:
129: layoutTree(levelRadius * levelSizes.size(), 0, levelRadius, 0,
130: root);
131:
132: double largestAngle = Math.PI * 2;
133: largestLevel = -1;
134: for (int i = 0; i < levelMaxAngles.length; i++)
135: if (levelMaxAngles[i] > largestAngle) {
136: largestAngle = levelMaxAngles[i];
137: largestLevel = i;
138: }
139:
140: if (largestLevel != -1) {
141: // Caclulcate the arc length of the largestLevel
142: double len = largestAngle * (largestLevel * levelRadius);
143:
144: // Calculate the levelRadius so that len will fit within 360 degrees
145: levelRadius = len / (2 * Math.PI) / largestLevel;
146:
147: for (int i = 0; i < levelMaxAngles.length; i++)
148: levelMaxAngles[i] = 0;
149:
150: //subtreeSize = new Rectangle( 0,0, (int)(levelRadius * levelSizes.size()*2), (int)(levelRadius * levelSizes.size()*2) );
151: //root.setSubtreeSize( subtreeSize );
152:
153: layoutTree(levelRadius * levelSizes.size(), 0, levelRadius,
154: 0, root);
155: }
156: }
157:
158: private void layoutTree(double maxRadius, double angle,
159: double levelRadius, int level, TreeNode node) {
160: CircularTreeLayoutData layoutData = (CircularTreeLayoutData) node
161: .getLayoutData();
162: //System.out.println( ((J3dEditor.J3dNodeTreeNode)node).getNode() + " "+layoutData);
163: Rectangle subtreeSize = null;
164:
165: double a = 0;
166: double centerChildren;
167:
168: if (node.numChildren() > 0) {
169: a = Math.atan(node.getPreferredSize().width
170: / (levelRadius * (level + 1)));
171:
172: if (levelMaxAngles[layoutData.childDepth] != 0
173: && angle - levelMaxAngles[layoutData.childDepth] < a) {
174: angle = levelMaxAngles[layoutData.childDepth] + a;
175: }
176: }
177:
178: if (levelMaxAngles[level] != 0
179: && angle - levelMaxAngles[level] < a) {
180: angle = levelMaxAngles[level] + a;
181: }
182:
183: for (int i = 0; i < node.numChildren(); i++) {
184: layoutTree(maxRadius, angle + (a * i), levelRadius,
185: level + 1, node.getChild(i));
186:
187: if (subtreeSize == null)
188: subtreeSize = new Rectangle(node.getChild(i)
189: .getSubtreeSize());
190: else
191: subtreeSize.add(node.getChild(i).getSubtreeSize());
192: }
193:
194: // Center parent with children - don't like it
195: // if (node.numChildren()>1) {
196: // centerChildren = ((CircularTreeLayoutData)node.getChild(node.numChildren()-1).getLayoutData()).angle -
197: // ((CircularTreeLayoutData)node.getChild(0).getLayoutData()).angle;
198: // centerChildren = centerChildren/2;
199: // } else
200:
201: // Place parent under first child
202: if (node.numChildren() > 0)
203: centerChildren = ((CircularTreeLayoutData) node.getChild(0)
204: .getLayoutData()).angle;
205: else
206: centerChildren = angle;
207:
208: setPosition(maxRadius, node, level, levelRadius, centerChildren);
209:
210: if (subtreeSize == null)
211: subtreeSize = new Rectangle(node.getComputedPosition(),
212: node.getPreferredSize());
213: else
214: subtreeSize.add(new Rectangle(node.getComputedPosition(),
215: node.getPreferredSize()));
216:
217: node.setSubtreeSize(subtreeSize);
218:
219: if (node.numChildren() > 0) {
220: Link link = node.getLink();
221: if (!(link instanceof CircularTreeLink))
222: node.setLink(link = new CircularTreeLink(node,
223: levelSpacing));
224:
225: ((CircularTreeLink) link).updateLink(maxRadius, a, level,
226: levelRadius, centerChildren);
227: } else
228: node.setLink(null);
229: }
230:
231: /**
232: * @param childIndex Index number of this child in it's parent group
233: */
234: private void setPosition(double center, TreeNode node, int level,
235: double levelRadius, double angle) {
236: double radius = level * levelRadius;
237:
238: Point computedPos = new Point();
239:
240: computedPos.x = (int) (center + Math.sin(angle) * radius)
241: - node.getMinimumSize().width / 2;
242: computedPos.y = (int) (center + Math.cos(angle) * radius)
243: - node.getMinimumSize().height / 2;
244:
245: if (angle > levelMaxAngles[level])
246: levelMaxAngles[level] = angle;
247:
248: node.setComputedPosition(computedPos);
249: ((CircularTreeLayoutData) node.getLayoutData()).angle = angle;
250:
251: //System.out.println( node.getClass().getName()+" "+computedPos );
252: }
253: }
|