y.layout.router.polyline
Class DynamicObstacleDecomposition

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

All Implemented Interfaces:

DynamicDecomposition, ObstaclePartition, Partition

public class DynamicObstacleDecomposition
extends java.lang.Object
implements ObstaclePartition, DynamicDecomposition

This class describes an ObstaclePartition that decomposes its area dynamically.

The partitioning strategy is based on binary space partitioning. It divides the partition space recursively in two cells until each cell is completely covered by 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 new instance of DynamicObstacleDecomposition.

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 such that the DynamicObstacleDecomposition can be reused and initialized with new Obstacles.
protected void	fireCreateCellEvent(PartitionCell createdCell) Notifies all registered dynamic decomposition listeners that the given partition cell has been created.
protected void	fireFinalizeCellEvent(PartitionCell finalizedCell) Notifies all registered dynamic decomposition listeners that the given partition cell has been finalized.
protected void	fireSubdividedEvent(PartitionCell cell, java.util.List subCells) Notifies all registered dynamic decomposition listeners of a subdivision of a given partition cell.
protected void	fireUnlockCellEvent(PartitionCell unlockedCell) Notifies all registered dynamic decomposition listeners that the given partition cell is unlocked again.
YRectangle	getBounds() Returns the bounds of the original rectangular area that is being partitioned.
java.util.List	getCells(Obstacle obstacle) Returns all partition cells that are completely covered by the given Obstacle.
java.util.List	getCells(YRectangle rect) Returns a list of all PartitionCells that intersect or cover the given rectangle.
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.
java.util.List	getNeighbors(PartitionCell cell) Returns the neighbor partition 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.
java.util.List	getObstacles(PartitionCell cell) Returns all Obstacles that cover the given partition 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(java.util.List obstacles, YRectangle partitionBounds) Initializes this DynamicObstacleDecomposition instance with the given obstacles and partition bounds.
void	removeDynamicDecompositionListener(DynamicDecomposition.Listener listener) Removes the given dynamic decomposition listener such that it no longer receives PartitionCell subdivision and creation events from this decomposition.
void	setCutObstacleCost(double cutObstacleCost) Specifies the costs incurred for every Obstacle that must be cut in a subdivision.
void	setUnbalancedObstaclesCost(double unbalancedObstaclesCost) Specifies the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.
void	setUnbalancedRatioCost(double unbalancedRatioCost) Specifies 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 new instance of DynamicObstacleDecomposition.

Method Detail

getCutObstacleCost

public double getCutObstacleCost()

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

Values need to be non-negative.

Returns:

a non-negative cut cost

See Also:

setCutObstacleCost(double)

setCutObstacleCost

public void setCutObstacleCost(double cutObstacleCost)

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

Values need to be non-negative.

Default Value:

The default value is 8.

Parameters:

cutObstacleCost - a non-negative cut cost

Throws:

java.lang.IllegalArgumentException - if the cost is negative

getUnbalancedObstaclesCost

public double getUnbalancedObstaclesCost()

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

Values need to be non-negative.

Returns:

a non-negative cost value

See Also:

setUnbalancedObstaclesCost(double)

setUnbalancedObstaclesCost

public void setUnbalancedObstaclesCost(double unbalancedObstaclesCost)

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

Values need to be non-negative.

Default Value:

The default value is 2.

Parameters:

unbalancedObstaclesCost - a non-negative cost value

Throws:

java.lang.IllegalArgumentException - if the cost is negative

getUnbalancedRatioCost

public double getUnbalancedRatioCost()

Returns the costs incurred if the subdivision produces unbalanced rectangles.

Values need to be non-negative.

Returns:

a non-negative cost value

See Also:

setUnbalancedRatioCost(double)

setUnbalancedRatioCost

public void setUnbalancedRatioCost(double unbalancedRatioCost)

Specifies the costs incurred if the subdivision produces unbalanced rectangles.

Values need to be non-negative.

Default Value:

The default value is 2.

Parameters:

unbalancedRatioCost - a non-negative cost value

Throws:

java.lang.IllegalArgumentException - if the cost is negative

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 when new cells are created.

Specified by:

addDynamicDecompositionListener in interface DynamicDecomposition

Parameters:

listener - the dynamic decomposition listener to add

See Also:

DynamicDecomposition.Listener

removeDynamicDecompositionListener

public void removeDynamicDecompositionListener(DynamicDecomposition.Listener listener)

Removes the given dynamic decomposition listener such 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 to remove

See Also:

DynamicDecomposition.Listener

fireSubdividedEvent

protected void fireSubdividedEvent(PartitionCell cell,
                                   java.util.List subCells)

Notifies all registered dynamic decomposition listeners of a subdivision of a given partition cell.

Parameters:

cell - the cell that has been subdivided

subCells - the new sub-cells resulting from the subdivision of the given cell

See Also:

DynamicDecomposition.Listener

fireFinalizeCellEvent

protected void fireFinalizeCellEvent(PartitionCell finalizedCell)

Notifies all registered dynamic decomposition listeners that the given partition cell has been finalized.

Parameters:

finalizedCell - the cell that has been finalized

See Also:

DynamicDecomposition.Listener

fireUnlockCellEvent

protected void fireUnlockCellEvent(PartitionCell unlockedCell)

Notifies all registered dynamic decomposition listeners that the given partition cell is unlocked again.

Parameters:

unlockedCell - the cell that has been unlocked

See Also:

DynamicDecomposition.Listener

fireCreateCellEvent

protected void fireCreateCellEvent(PartitionCell createdCell)

Notifies all registered dynamic decomposition listeners that the given partition cell has been created.

This method is also called in init(List, YRectangle).

Parameters:

createdCell - the newly created cell

See Also:

DynamicDecomposition.Listener

init

public void init(java.util.List obstacles,
                 YRectangle partitionBounds)

Initializes this DynamicObstacleDecomposition instance 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

See Also:

ObstaclePartition.clear()

clear

public void clear()

Clears the partition data such that the DynamicObstacleDecomposition can be reused and initialized with new Obstacles.

Specified by:

clear in interface ObstaclePartition

See Also:

init(List, YRectangle)

getObstacleCutCosts

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

Calculates the cost of a cut with respect to the subdivided obstacles.

The cost can take values between 0 and 1.

This method is called while a PartitionCell is divided into upper and lower or left and right child cells depending on the cut costs (during getCells(Obstacle), getCells(YRectangle) and getNeighbors(PartitionCell) methods).

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:

the cost 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 can take values between 0 and 1.

This method is called while a PartitionCell is divided into upper and lower or left and right child cells depending on the cut costs (during getCells(Obstacle), getCells(YRectangle) and getNeighbors(PartitionCell) methods).

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:

the cost of a cut with respect to the geometry of the sub-cells

getNeighbors

public java.util.List getNeighbors(PartitionCell cell)

Returns the neighbor partition cells of the given cell.

Specified by:

getNeighbors in interface Partition

Parameters:

cell - the cell whose neighbors will be returned

Returns:

the neighbor cells of the given cell

getObstacles

public java.util.List getObstacles(PartitionCell cell)

Returns all Obstacles that cover the given partition cell.

Specified by:

getObstacles in interface ObstaclePartition

Parameters:

cell - the partition cell for which the obstacles will be returned

Returns:

an unmodifiable list of Obstacle instances that cover the given cell

getCells

public java.util.List getCells(Obstacle obstacle)

Returns all partition cells that are completely covered by the given Obstacle.

Specified by:

getCells in interface ObstaclePartition

Parameters:

obstacle - the obstacle for which the covered cells will be returned

Returns:

an unmodifiable list of PartitionCell instances that are completely covered by the given obstacle

getCells

public java.util.List getCells(YRectangle rect)

Returns a list of all PartitionCells that intersect or cover the given rectangle.

Specified by:

getCells in interface Partition

Parameters:

rect - the rectangular area whose (partially) covered cells will be returned

Returns:

a list of PartitionCells that (partially) cover the given rectangular area

getBounds

public YRectangle getBounds()

Returns the bounds of the original rectangular area that is being partitioned.

Specified by:

getBounds in interface Partition

Returns:

the bounds of the original rectangular area