y.layout.router.polyline
Class DynamicObstacleDecomposition

java.lang.Object
  y.layout.router.polyline.DynamicObstacleDecomposition

All Implemented Interfaces:

DynamicDecomposition, ObstaclePartition, Partition

public class DynamicObstacleDecomposition
extends Object
implements ObstaclePartition, DynamicDecomposition

An ObstaclePartition that decomposes its area dynamically and implements the DynamicDecomposition interface.

The partitioning strategy is based on binary space partitioning. It divides the partition space recursively in two cells until each cell is completely covered from one or more obstacles or completely empty.

Nested Class Summary

Nested classes/interfaces inherited from interface y.layout.router.polyline.DynamicDecomposition

DynamicDecomposition.Listener

Constructor Summary

DynamicObstacleDecomposition()
Constructs a dynamic obstacle decomposition.

Method Summary

void	addDynamicDecompositionListener(DynamicDecomposition.Listener listener) Adds the given dynamic decomposition listener to receive PartitionCell subdivision and creation events from this decomposition.
void	clear() Clears the partition data so the ObstaclePartition can be reused and ObstaclePartition.init(java.util.List, y.geom.YRectangle) initialized} with new Obstacles.
protected void	fireCreateCellEvent(PartitionCell createdCell) Notifies all registered dynamic decomposition listeners about the newly created cell.
protected void	fireFinalizeCellEvent(PartitionCell finalizedCell) Notifies all registered dynamic decomposition listeners about the finalized cell.
protected void	fireSubdividedEvent(PartitionCell cell, List subCells) Notifies all registered dynamic decomposition listeners about a subdivision.
YRectangle	getBounds() Returns the bounds of the decomposition area.
List	getCells(Obstacle obstacle) Returns the PartitionCell in which the given obstacle lies.
List	getCells(YRectangle rect) Returns the PartitionCells in which the given rectangle lies.
double	getCutObstacleCost() Returns the costs incurred for every obstacle that must be cut in a subdivision.
protected double	getGeometricCutCosts(double cut, double min, double max, double orthogonalMin, double orthogonalMax) Calculates the cost of a cut with respect to the geometry of the sub-cells.
List	getNeighbors(PartitionCell cell) Returns the neighbor cells of the given cell.
protected double	getObstacleCutCosts(int numObstaclesInFirstHalf, int numObstaclesInSecondHalf, int numObstaclesOnCut) Calculates the cost of a cut with respect to the subdivided obstacles.
List	getObstacles(PartitionCell cell) Returns the obstacles that lie in the given cell.
double	getUnbalancedObstaclesCost() Returns the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.
double	getUnbalancedRatioCost() Returns the costs incurred if the subdivision produces unbalanced rectangles.
void	init(List obstacles, YRectangle partitionBounds) Initializes this dynamic obstacle decomposition with the given obstacles and partition bounds.
void	removeDynamicDecompositionListener(DynamicDecomposition.Listener listener) Removes the given dynamic decomposition listener so that it no longer receives PartitionCell subdivision and creation events from this decomposition.
void	setCutObstacleCost(double cutObstacleCost) Sets the costs incurred for every obstacle that must be cut in a subdivision.
void	setUnbalancedObstaclesCost(double unbalancedObstaclesCost) Sets the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.
void	setUnbalancedRatioCost(double unbalancedRatioCost) Sets the costs incurred if the subdivision produces unbalanced rectangles.

Methods inherited from class java.lang.Object

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

Constructor Detail

DynamicObstacleDecomposition

public DynamicObstacleDecomposition()

Constructs a dynamic obstacle decomposition.

Method Detail

getCutObstacleCost

public double getCutObstacleCost()

Returns the costs incurred for every obstacle that must be cut in a subdivision.

Returns:

the costs incurred for every obstacle that must be cut in a subdivision.

setCutObstacleCost

public void setCutObstacleCost(double cutObstacleCost)

Sets the costs incurred for every obstacle that must be cut in a subdivision.

Parameters:

cutObstacleCost - the costs incurred for every obstacle that must be cut in a subdivision.

getUnbalancedObstaclesCost

public double getUnbalancedObstaclesCost()

Returns the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.

Returns:

the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.

setUnbalancedObstaclesCost

public void setUnbalancedObstaclesCost(double unbalancedObstaclesCost)

Sets the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.

Parameters:

unbalancedObstaclesCost - the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.

getUnbalancedRatioCost

public double getUnbalancedRatioCost()

Returns the costs incurred if the subdivision produces unbalanced rectangles.

Returns:

the costs incurred if the subdivision produces unbalanced rectangles.

setUnbalancedRatioCost

public void setUnbalancedRatioCost(double unbalancedRatioCost)

Sets the costs incurred if the subdivision produces unbalanced rectangles.

Parameters:

unbalancedRatioCost - the costs incurred if the subdivision produces unbalanced rectangles.

addDynamicDecompositionListener

public void addDynamicDecompositionListener(DynamicDecomposition.Listener listener)

Adds the given dynamic decomposition listener to receive PartitionCell subdivision and creation events from this decomposition. These events occur when the decomposition changes the partition by subdividing cells into sub-cells or new cell are created.

Specified by:

addDynamicDecompositionListener in interface DynamicDecomposition

Parameters:

listener - the dynamic decomposition listener.

See Also:

DynamicDecomposition.Listener

removeDynamicDecompositionListener

public void removeDynamicDecompositionListener(DynamicDecomposition.Listener listener)

Removes the given dynamic decomposition listener so that it no longer receives PartitionCell subdivision and creation events from this decomposition.

Specified by:

removeDynamicDecompositionListener in interface DynamicDecomposition

Parameters:

listener - the dynamic decomposition listener.

See Also:

DynamicDecomposition.Listener

fireSubdividedEvent

protected void fireSubdividedEvent(PartitionCell cell,
                                   List subCells)

Notifies all registered dynamic decomposition listeners about a subdivision.

Parameters:

cell - The cell that has been subdivided.

subCells - The new sub cells of the divided cell.

See Also:

DynamicDecomposition.Listener

fireFinalizeCellEvent

protected void fireFinalizeCellEvent(PartitionCell finalizedCell)

Notifies all registered dynamic decomposition listeners about the finalized cell.

Parameters:

finalizedCell - The cell that has been finalized.

See Also:

DynamicDecomposition.Listener

fireCreateCellEvent

protected void fireCreateCellEvent(PartitionCell createdCell)

Notifies all registered dynamic decomposition listeners about the newly created cell.

Parameters:

createdCell - The newly created cell.

See Also:

DynamicDecomposition.Listener

init

public void init(List obstacles,
                 YRectangle partitionBounds)

Initializes this dynamic obstacle decomposition with the given obstacles and partition bounds. This method must be called before any other method is invoked.

Specified by:

init in interface ObstaclePartition

Parameters:

obstacles - A list of Obstacle objects.

partitionBounds - The bounds of the partition.

clear

public void clear()

Description copied from interface: ObstaclePartition

Clears the partition data so the ObstaclePartition can be reused and ObstaclePartition.init(java.util.List, y.geom.YRectangle) initialized} with new Obstacles.

Specified by:

clear in interface ObstaclePartition

getObstacleCutCosts

protected double getObstacleCutCosts(int numObstaclesInFirstHalf,
                                     int numObstaclesInSecondHalf,
                                     int numObstaclesOnCut)

Calculates the cost of a cut with respect to the subdivided obstacles. The cost ranges between 0 and 1.

Parameters:

numObstaclesInFirstHalf - The number of obstacles that lie completely in the first half.

numObstaclesInSecondHalf - The number of obstacles that lie completely in the second half.

numObstaclesOnCut - The number of obstacles that lie on the cut.

Returns:

Costs of a cut with respect to the subdivided obstacles.

getGeometricCutCosts

protected double getGeometricCutCosts(double cut,
                                      double min,
                                      double max,
                                      double orthogonalMin,
                                      double orthogonalMax)

Calculates the cost of a cut with respect to the geometry of the sub-cells. The cost ranges between 0 and 1.

Parameters:

cut - The coordinate of the cut.

min - The left side of the subdivided cell.

max - The right side of the subdivided cell.

orthogonalMin - The upper side of the subdivided cell.

orthogonalMax - The lower side of the subdivided cell.

Returns:

Costs of a cut with respect to the geometry of the sub-cells.

getNeighbors

public List getNeighbors(PartitionCell cell)

Returns the neighbor cells of the given cell.

Specified by:

getNeighbors in interface Partition

Parameters:

cell - The cell to get the neighbors for.

Returns:

The neighbor cells of the given cell.

getObstacles

public List getObstacles(PartitionCell cell)

Returns the obstacles that lie in the given cell.

Specified by:

getObstacles in interface ObstaclePartition

Parameters:

cell - The cell to get the obstacles for.

Returns:

The obstacles that lie in the given cell.

getCells

public List getCells(Obstacle obstacle)

Returns the PartitionCell in which the given obstacle lies.

Specified by:

getCells in interface ObstaclePartition

Parameters:

obstacle - The obstacle to get the cells for.

Returns:

The cells in which the given obstacle lies.

getCells

public List getCells(YRectangle rect)

Returns the PartitionCells in which the given rectangle lies.

Specified by:

getCells in interface Partition

Parameters:

rect - The rectangle to get the cells for.

Returns:

The cells in which the given rectangle lies.

getBounds

public YRectangle getBounds()

Returns the bounds of the decomposition area.

Specified by:

getBounds in interface Partition

Returns:

The bounds of the decomposition area.