Package com.macrofocus.treemap.originalfastvoronoi

Class VoronoiTreemap

java.lang.Object

com.macrofocus.treemap.originalfastvoronoi.VoronoiTreemap

All Implemented Interfaces:

StatusObject, VoronoiTreemapInterface, java.lang.Iterable<VoroNode>

public class VoronoiTreemap
extends java.lang.Object
implements java.lang.Iterable<VoroNode>, StatusObject, VoronoiTreemapInterface

Main Voronoi Treemap class implementing the Voronoi Treemap interface and maintaining the settings.

Field Summary

Fields

Modifier and Type	Field	Description
protected double	errorAreaThreshold
protected boolean	preflowFinished
protected VoroNode	root

Constructor Summary

Constructors

Constructor	Description
VoronoiTreemap()
VoronoiTreemap(StatusObject statusObject)	when a node is finished the status object is notified.

Method Summary

Modifier and Type	Method	Description
void	clear()	Clears the used datastructures.
void	compute()	After setting at least the rootPolygon and the treeStructure(see VoronoiTreemapInterface.setTreeAndWeights(PolygonSimple, ArrayList, ArrayList, ArrayList)), the voronoi Treemap can be computed.
protected VoroNode	createVoroNode(java.util.HashMap<java.lang.Integer,VoroNode> idToNode, java.util.ArrayList<java.lang.Integer> adjacencyLine)
void	finished()
void	finishedNode(int Node, int layer, int[] children, PolygonSimple[] polygons)
boolean	getAggressiveMode()	true: aggressive weight modification false: normal weight modification
double	getCancelErrorThreshold()	maximal error threshold to cancel the optimization process.
boolean	getCancelOnMaxIteration()
boolean	getCancelOnThreshold()	VoronoiTreemapInterface.setCancelOnThreshold(boolean)
boolean	getGuaranteeValidCells()	VoronoiTreemapInterface.setGuaranteeValidCells(boolean)
int	getNumberMaxIterations()	the maximal number of iterations.
double	getPreflowIncrease()
double	getPreflowPercentage()	VoronoiTreemapInterface.setPreflowPercentage(double)
long	getRandomSeed()	Seed which is used for random initialization of the sites.
PolygonSimple	getRootPolygon()	Returns the root polygon.
boolean	getShowLeafs()
double	getShrinkPercentage()	VoronoiTreemapInterface.setShrinkPercentage(double)
StatusObject	getStatusObject()	VoronoiTreemapInterface.setStatusObject(StatusObject)
boolean	getUseBorder()	VoronoiTreemapInterface.setUseBorder(boolean)
boolean	getUseExtrapolation()	VoronoiTreemapInterface.setUseExtrapolation(boolean)
protected void	init()
protected void	initVoroNodes()
boolean	isUseNegativeWeights()	Return whether negative weights for the sites are allowed.
java.util.Iterator<VoroNode>	iterator()
void	setAggressiveMode(boolean mode)	the aggressive mode modifies the weights of the sites very aggressively and is not 100% stable (some cells can get empty), anyway sometimes it yields better local minima.
void	setAreaGoals(java.util.ArrayList<Tuple2ID> areaGoals)	Sets a weighting for each nodes which influences the final area the node polygon has.
void	setCancelOnMaxIteration(boolean cancelOnMaxIterat)	true: The optimization process is canceled when the maximal iteration number is reached.
void	setCancelOnThreshold(boolean cancelOnThreshold)	true: the optimization process is canceled when the area error is below the given threshold.
void	setGuaranteeValidCells(boolean guaranteeInvariant)	true: guarantees that the weight adaption does not cause empty cells.
void	setNumberMaxIterations(int numberMaxIterations)	Sets the default maximal number of iterations done in a single level computation.
void	setNumberThreads(int numberThreads)	If possible the given number of threads will be started to speed up the optimization process.
void	setPreflowIncrease(double preflowIncrease)
void	setPreflowPercentage(double preflowPercentage)	If the desire of a cell (site) to increase its area is above this percentage, then this cell pushes the other cells away.
void	setRandomSeed(long seed)	Sets the seed for the random position generator which is used to initialize the sites.
void	setReferenceMap(java.util.ArrayList<Tuple3ID> relativePositions)	ReferenceMap, which consists of a relative x,y position for each node: each coordinate must be in the range between [0...1]
void	setRootPolygon(PolygonSimple rootPolygon)	Sets the convex root polygon in which the treemap is computed.
void	setRootRectangle(double x, double y, double width, double height)	Sets the a rectangle (as root polygon) in which the treemap is computed.
protected void	setSettingsToVoroNode(VoroNode node)
void	setShrinkPercentage(double shrinkPercentage)	Sets the factor which scales every iteration, so 1-shrinkPercentage is equally the border percentage.
void	setStatusObject(StatusObject statusObject)	This status object is notified when the children of a node are processed and when the whole computation has finished.
void	setTree(java.util.ArrayList<java.util.ArrayList<java.lang.Integer>> treeStructure)	Sets the tree.
void	setTreeAndWeights(PolygonSimple rootPolygon, java.util.ArrayList<java.util.ArrayList<java.lang.Integer>> treeStructure, java.util.ArrayList<Tuple2ID> areaGoals, java.util.ArrayList<Tuple3ID> relativePositions)	All necessary things are set here such that a Voronoi Treemap can be computed.
void	setUseBorder(boolean useBorder)	Sets whether there borders are added for every iteration level or not.
void	setUseExtrapolation(boolean useExtrapolation)	Activates the speed up heuristic which uses some kind of force to make more space for big cells.
void	setUseNegativeWeights(boolean use)	set usage of negative weights for the sites.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

root

protected VoroNode root

errorAreaThreshold

protected double errorAreaThreshold

preflowFinished

protected boolean preflowFinished

Constructor Detail

VoronoiTreemap

public VoronoiTreemap(StatusObject statusObject)

when a node is finished the status object is notified.

VoronoiTreemap

public VoronoiTreemap()

Method Detail

init

protected void init()

initVoroNodes

protected void initVoroNodes()

compute

public void compute()

Description copied from interface: VoronoiTreemapInterface

After setting at least the rootPolygon and the treeStructure(see VoronoiTreemapInterface.setTreeAndWeights(PolygonSimple, ArrayList, ArrayList, ArrayList)), the voronoi Treemap can be computed. For every computed Node finishedNode(...) will be called in the StatusObject. If the computation is completed finished() will be called in the Statusobject.

Specified by:

compute in interface VoronoiTreemapInterface

setSettingsToVoroNode

protected void setSettingsToVoroNode(VoroNode node)

setTreeAndWeights

public void setTreeAndWeights(PolygonSimple rootPolygon,
                              java.util.ArrayList<java.util.ArrayList<java.lang.Integer>> treeStructure,
                              java.util.ArrayList<Tuple2ID> areaGoals,
                              java.util.ArrayList<Tuple3ID> relativePositions)

Description copied from interface: VoronoiTreemapInterface

All necessary things are set here such that a Voronoi Treemap can be computed. AreaGoals and refereceMapPositions can be null.

Specified by:

setTreeAndWeights in interface VoronoiTreemapInterface

createVoroNode

protected final VoroNode createVoroNode(java.util.HashMap<java.lang.Integer,VoroNode> idToNode,
                                        java.util.ArrayList<java.lang.Integer> adjacencyLine)

getShowLeafs

public boolean getShowLeafs()

Specified by:

getShowLeafs in interface VoronoiTreemapInterface

iterator

public java.util.Iterator<VoroNode> iterator()

Specified by:

iterator in interface java.lang.Iterable<VoroNode>

finished

public void finished()

Specified by:

finished in interface StatusObject

setShrinkPercentage

public void setShrinkPercentage(double shrinkPercentage)

Description copied from interface: VoronoiTreemapInterface

Sets the factor which scales every iteration, so 1-shrinkPercentage is equally the border percentage.

Specified by:

setShrinkPercentage in interface VoronoiTreemapInterface

Parameters:

shrinkPercentage - preferred between 0 < shrinkPercentage <= 1

getShrinkPercentage

public double getShrinkPercentage()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setShrinkPercentage(double)

Specified by:

getShrinkPercentage in interface VoronoiTreemapInterface

Returns:

setUseBorder

public void setUseBorder(boolean useBorder)

Description copied from interface: VoronoiTreemapInterface

Sets whether there borders are added for every iteration level or not.

Specified by:

setUseBorder in interface VoronoiTreemapInterface

getUseBorder

public boolean getUseBorder()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setUseBorder(boolean)

Specified by:

getUseBorder in interface VoronoiTreemapInterface

Returns:

setNumberMaxIterations

public void setNumberMaxIterations(int numberMaxIterations)

Description copied from interface: VoronoiTreemapInterface

Sets the default maximal number of iterations done in a single level computation.

Specified by:

setNumberMaxIterations in interface VoronoiTreemapInterface

getNumberMaxIterations

public int getNumberMaxIterations()

Description copied from interface: VoronoiTreemapInterface

the maximal number of iterations.

Specified by:

getNumberMaxIterations in interface VoronoiTreemapInterface

Returns:

cancelOnMaxIterat

setPreflowPercentage

public void setPreflowPercentage(double preflowPercentage)

Description copied from interface: VoronoiTreemapInterface

If the desire of a cell (site) to increase its area is above this percentage, then this cell pushes the other cells away. This option reduces the number of needed iteration if there is high variance in the desired cell sizes.

Specified by:

setPreflowPercentage in interface VoronoiTreemapInterface

getPreflowPercentage

public double getPreflowPercentage()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setPreflowPercentage(double)

Specified by:

getPreflowPercentage in interface VoronoiTreemapInterface

Returns:

setPreflowIncrease

public void setPreflowIncrease(double preflowIncrease)

Specified by:

setPreflowIncrease in interface VoronoiTreemapInterface

Parameters:

preflowIncrease - the preflowIncrease to set

getPreflowIncrease

public double getPreflowIncrease()

Specified by:

getPreflowIncrease in interface VoronoiTreemapInterface

Returns:

the preflowIncrease

setUseExtrapolation

public void setUseExtrapolation(boolean useExtrapolation)

Description copied from interface: VoronoiTreemapInterface

Activates the speed up heuristic which uses some kind of force to make more space for big cells.

Specified by:

setUseExtrapolation in interface VoronoiTreemapInterface

Parameters:

useExtrapolation - the useExtrapolation to set

getUseExtrapolation

public boolean getUseExtrapolation()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setUseExtrapolation(boolean)

Specified by:

getUseExtrapolation in interface VoronoiTreemapInterface

Returns:

the useExtrapolation

setCancelOnThreshold

public void setCancelOnThreshold(boolean cancelOnThreshold)

Description copied from interface: VoronoiTreemapInterface

true: the optimization process is canceled when the area error is below the given threshold.

Specified by:

setCancelOnThreshold in interface VoronoiTreemapInterface

Parameters:

cancelOnThreshold - the cancelOnThreshold to set

getCancelOnThreshold

public boolean getCancelOnThreshold()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setCancelOnThreshold(boolean)

Specified by:

getCancelOnThreshold in interface VoronoiTreemapInterface

Returns:

the cancelOnThreshold

setCancelOnMaxIteration

public void setCancelOnMaxIteration(boolean cancelOnMaxIterat)

Description copied from interface: VoronoiTreemapInterface

true: The optimization process is canceled when the maximal iteration number is reached.

Specified by:

setCancelOnMaxIteration in interface VoronoiTreemapInterface

Parameters:

cancelOnMaxIterat - the cancelOnMaxIterat to set

getCancelOnMaxIteration

public boolean getCancelOnMaxIteration()

Specified by:

getCancelOnMaxIteration in interface VoronoiTreemapInterface

setRootPolygon

public void setRootPolygon(PolygonSimple rootPolygon)

Description copied from interface: VoronoiTreemapInterface

Sets the convex root polygon in which the treemap is computed. The result will always be included into the root polygon. Currently the root polygon has to be convex, if you have a fast implementation for the intersection of non convex polygons, I could easily extend the library to simple polygons.

Specified by:

setRootPolygon in interface VoronoiTreemapInterface

Parameters:

rootPolygon - the root Polygon to be set (must be convex currently)

setRootRectangle

public void setRootRectangle(double x,
                             double y,
                             double width,
                             double height)

Description copied from interface: VoronoiTreemapInterface

Sets the a rectangle (as root polygon) in which the treemap is computed.

Specified by:

setRootRectangle in interface VoronoiTreemapInterface

Parameters:

x - x-coordinate of the upper left point of the rectangle

y - y-coordinate of the upper left point of the rectangle

width - width of the rectangle

height - height of the rectangle

getRootPolygon

public PolygonSimple getRootPolygon()

Description copied from interface: VoronoiTreemapInterface

Returns the root polygon.

Specified by:

getRootPolygon in interface VoronoiTreemapInterface

Returns:

the rootPolygon

setGuaranteeValidCells

public void setGuaranteeValidCells(boolean guaranteeInvariant)

Description copied from interface: VoronoiTreemapInterface

true: guarantees that the weight adaption does not cause empty cells. false:computation is approx. 30 % faster, but exception could be thrown in the optimization process

Specified by:

setGuaranteeValidCells in interface VoronoiTreemapInterface

Parameters:

guaranteeInvariant - guarantee non empty cells

getGuaranteeValidCells

public boolean getGuaranteeValidCells()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setGuaranteeValidCells(boolean)

Specified by:

getGuaranteeValidCells in interface VoronoiTreemapInterface

Returns:

the guaranteeInvariant

setNumberThreads

public void setNumberThreads(int numberThreads)

Description copied from interface: VoronoiTreemapInterface

If possible the given number of threads will be started to speed up the optimization process. Usually this is possible after the computation of the first hierarchy level has been finished.

Specified by:

setNumberThreads in interface VoronoiTreemapInterface

Parameters:

numberThreads - the numberThreads to set

setStatusObject

public void setStatusObject(StatusObject statusObject)

Description copied from interface: VoronoiTreemapInterface

This status object is notified when the children of a node are processed and when the whole computation has finished.

Specified by:

setStatusObject in interface VoronoiTreemapInterface

Parameters:

statusObject - the tellTheEndObject to set

getStatusObject

public StatusObject getStatusObject()

Description copied from interface: VoronoiTreemapInterface

VoronoiTreemapInterface.setStatusObject(StatusObject)

Specified by:

getStatusObject in interface VoronoiTreemapInterface

Returns:

finishedNode

public void finishedNode(int Node,
                         int layer,
                         int[] children,
                         PolygonSimple[] polygons)

Specified by:

finishedNode in interface StatusObject

setAreaGoals

public void setAreaGoals(java.util.ArrayList<Tuple2ID> areaGoals)

Description copied from interface: VoronoiTreemapInterface

Sets a weighting for each nodes which influences the final area the node polygon has. the weightings are normalized so that the sum over the weightings of descendant nodes equals to one. this function must be called after the tree structure is defined (setTree(...)).

Specified by:

setAreaGoals in interface VoronoiTreemapInterface

Parameters:

areaGoals - Tupel2ID with (NodeId, weight)

setReferenceMap

public void setReferenceMap(java.util.ArrayList<Tuple3ID> relativePositions)

Description copied from interface: VoronoiTreemapInterface

ReferenceMap, which consists of a relative x,y position for each node: each coordinate must be in the range between [0...1]

Specified by:

setReferenceMap in interface VoronoiTreemapInterface

Parameters:

relativePositions - Tupel3ID with (NodeId, relative x, relative y), x,y in range [0,1]

setTree

public void setTree(java.util.ArrayList<java.util.ArrayList<java.lang.Integer>> treeStructure)

Description copied from interface: VoronoiTreemapInterface

Sets the tree.

Specified by:

setTree in interface VoronoiTreemapInterface

Parameters:

treeStructure - defines a tree by an adjacency list, node a has children b,c,d (list(a,b,c,d))

isUseNegativeWeights

public boolean isUseNegativeWeights()

Description copied from interface: VoronoiTreemapInterface

Return whether negative weights for the sites are allowed. Negative weights should result in a faster convergence.

Specified by:

isUseNegativeWeights in interface VoronoiTreemapInterface

Returns:

setUseNegativeWeights

public void setUseNegativeWeights(boolean use)

Description copied from interface: VoronoiTreemapInterface

set usage of negative weights for the sites. Negative weights should result in a faster convergence.

Specified by:

setUseNegativeWeights in interface VoronoiTreemapInterface

clear

public void clear()

Description copied from interface: VoronoiTreemapInterface

Clears the used datastructures.

Specified by:

clear in interface VoronoiTreemapInterface

setAggressiveMode

public void setAggressiveMode(boolean mode)

Description copied from interface: VoronoiTreemapInterface

the aggressive mode modifies the weights of the sites very aggressively and is not 100% stable (some cells can get empty), anyway sometimes it yields better local minima.

Specified by:

setAggressiveMode in interface VoronoiTreemapInterface

getAggressiveMode

public boolean getAggressiveMode()

Description copied from interface: VoronoiTreemapInterface

true: aggressive weight modification false: normal weight modification

Specified by:

getAggressiveMode in interface VoronoiTreemapInterface

Returns:

setRandomSeed

public void setRandomSeed(long seed)

Description copied from interface: VoronoiTreemapInterface

Sets the seed for the random position generator which is used to initialize the sites.

Specified by:

setRandomSeed in interface VoronoiTreemapInterface

getRandomSeed

public long getRandomSeed()

Description copied from interface: VoronoiTreemapInterface

Seed which is used for random initialization of the sites.

Specified by:

getRandomSeed in interface VoronoiTreemapInterface

Returns:

getCancelErrorThreshold

public double getCancelErrorThreshold()

Description copied from interface: VoronoiTreemapInterface

maximal error threshold to cancel the optimization process.

Specified by:

getCancelErrorThreshold in interface VoronoiTreemapInterface

Returns: