Package com.macrofocus.treemap.voronoi

Class VoronoiAlgorithm<N,Row,Column,Color,Font>

java.lang.Object

com.macrofocus.treemap.AbstractAlgorithm<N,Row,Column,Color,Font>

com.macrofocus.treemap.voronoi.VoronoiAlgorithm<N,Row,Column,Color,Font>

All Implemented Interfaces:

Algorithm<N,Row,Column,Color,Font>

public class VoronoiAlgorithm<N,Row,Column,Color,Font>
extends AbstractAlgorithm<N,Row,Column,Color,Font>

Implementation of the Voronoi algorithm. It is described in:

Michael Balzer, Oliver Deussen "Voronoi Treemaps". In: Proceedings of the 2005 IEEE Symposium on Information Visualization (INFOVIS'05), p. 49-56.

Rectangular algorithms, cause problems with the aspect ratio of the rectangles as well as with identifying the visualized hierarchical structure. The approach of Voronoi Treemaps eliminates these problems through enabling subdivisions of and in polygons. Additionally, this allows for creating Treemap visualizations within areas of arbitrary shape, such as triangles and circles, thereby enabling a more flexible adaptation of Treemaps for a wider range of applications.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	VoronoiAlgorithm.WeightType

Field Summary

Fields

Modifier and Type	Field	Description
protected double	delta

Constructor Summary

Constructors

Constructor	Description
VoronoiAlgorithm()
VoronoiAlgorithm(double epsilon, double delta, int minIterations, int maxIterations, int seed, int maxRestarts, VoronoiAlgorithm.WeightType weightType)	Creates a new object that can produce voronoi treemap layouts.

Method Summary

Modifier and Type	Method	Description
boolean	breadthFirstLayout(java.awt.Shape shape, MutableTreeMapNode parent, MutableTreeMapNode[] children, double sumSizes, int horizontalVanishingPoint, int verticalVanishingPoint, TreeMapWorker worker)	Arrange the items in the given array to fill the given shape.
static double	calculatePolygonArea(java.awt.Polygon polygon)	Calculates the area of a polygon.
boolean	isCompatible(java.awt.Shape shape)	Indicates whether the layout algorithm can handle the given geometry of its parent
boolean	isSpaceFilling()
VoronoiOutputRaster	run(java.awt.Shape unscaledDomain, VoronoiCell[] cells, TreeMapWorker worker, MutableTreeMapNode parent)	Calculates a pixel raster Voronoi based on the "Algorithm 1" discribed Balzer et al.
void	startLayout(java.awt.geom.Rectangle2D bounds, TreeMapModel<N,Row,Column,Color,Font> model, N root, TreeMapWorker worker)	Do nothing by default.
java.lang.String	toString()

Methods inherited from class com.macrofocus.treemap.AbstractAlgorithm

depthFirstLayout, finishLayout, getProperties, isChildContained, isColorParent, isRenderingLeafLabelsSupported, isRenderingParentLabelSupported, iterator, sum

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

delta

protected double delta

Constructor Detail

VoronoiAlgorithm

public VoronoiAlgorithm()

VoronoiAlgorithm

public VoronoiAlgorithm(double epsilon,
                        double delta,
                        int minIterations,
                        int maxIterations,
                        int seed,
                        int maxRestarts,
                        VoronoiAlgorithm.WeightType weightType)

Creates a new object that can produce voronoi treemap layouts.

Parameters:

epsilon - absolute of the maximal allowed error in area (as proportion of the diagram area)

delta - minimum value of weights, must be small but must not be zero, eg. 1e-5

minIterations - minimal number of iterations

maxIterations - maximal number of iterations

seed - seed parameter for the random start positions of the cells

maxRestarts - maximal number of layout restarts with reduced delta

weightType - additively or power weigthed voronoi diagram type

Method Detail

startLayout

public void startLayout(java.awt.geom.Rectangle2D bounds,
                        TreeMapModel<N,Row,Column,Color,Font> model,
                        N root,
                        TreeMapWorker worker)

Do nothing by default.

Specified by:

startLayout in interface Algorithm<N,Row,Column,Color,Font>

Overrides:

startLayout in class AbstractAlgorithm<N,Row,Column,Color,Font>

Parameters:

bounds - the bounds of the view

model - the model

root - the root node

breadthFirstLayout

public boolean breadthFirstLayout(java.awt.Shape shape,
                                  MutableTreeMapNode parent,
                                  MutableTreeMapNode[] children,
                                  double sumSizes,
                                  int horizontalVanishingPoint,
                                  int verticalVanishingPoint,
                                  TreeMapWorker worker)

Arrange the items in the given array to fill the given shape. This is called during the first pass, while traversing the tree top down.

Parameters:

shape - the current rectangle being divided.

parent - the parent node.

children - the items to map.

sumSizes - the size of the parent.

worker - the worker thread

Returns:

true if the layout has been cancelled, false otherwise

run

public VoronoiOutputRaster run(java.awt.Shape unscaledDomain,
                               VoronoiCell[] cells,
                               TreeMapWorker worker,
                               MutableTreeMapNode parent)

Calculates a pixel raster Voronoi based on the "Algorithm 1" discribed Balzer et al. 2005 paper, enhanced with scaling and restart-when-failed functionality.

Parameters:

unscaledDomain - domain inside which the layout is calculated

cells - array of VoronoiCells containing initialized with their desired areas

worker - the worker thread

parent - the parent node (as debug information)

Returns:

the calculated voronoi diagram as pixel raster. null if calculation was not successful

calculatePolygonArea

public static double calculatePolygonArea(java.awt.Polygon polygon)

Calculates the area of a polygon.

Parameters:

polygon - the polygon

Returns:

the calculated area of the polygon

isCompatible

public boolean isCompatible(java.awt.Shape shape)

Description copied from interface: Algorithm

Indicates whether the layout algorithm can handle the given geometry of its parent

Parameters:

shape - the geometry of its parent

Returns:

true if it can lay out the children using the specified geometrical shape

isSpaceFilling

public boolean isSpaceFilling()

Specified by:

isSpaceFilling in interface Algorithm<N,Row,Column,Color,Font>

Overrides:

isSpaceFilling in class AbstractAlgorithm<N,Row,Column,Color,Font>

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns: