com.yworks.yfiles.layout.router.polyline

Class DynamicObstacleDecomposition

java.lang.Object

com.yworks.yfiles.layout.router.polyline.DynamicObstacleDecomposition

All Implemented Interfaces:

IDynamicDecomposition, IObstaclePartition, IPartition

public class DynamicObstacleDecomposition
extends Object
implements IObstaclePartition, IDynamicDecomposition

This class describes an IObstaclePartition 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.

Constructor Summary

Constructors

Constructor and Description
DynamicObstacleDecomposition() Constructs a new instance of DynamicObstacleDecomposition.

Method Summary

Modifier and Type	Method and Description
void	addDynamicDecompositionListener(IDecompositionListener 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, List<Object> subCells) Notifies all registered dynamic decomposition listeners of a subdivision of a given partition cell.
YRectangle	getBounds() Gets the bounds of the original rectangular area that is being partitioned.
List<Object>	getCells(Obstacle obstacle) Returns all partition cells that are completely covered by the given Obstacle.
List<Object>	getCells(YRectangle rect) Returns a list of all PartitionCells that intersect or cover the given rectangle.
double	getCutObstacleCost() Gets 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<Object>	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.
List<Object>	getObstacles(PartitionCell cell) Returns all Obstacles that cover the given partition cell.
double	getUnbalancedObstaclesCost() Gets the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.
double	getUnbalancedRatioCost() Gets the costs incurred if the subdivision produces unbalanced rectangles.
void	init(List<Object> obstacles, YRectangle partitionBounds) Initializes this DynamicObstacleDecomposition instance with the given obstacles and partition bounds.
void	removeDynamicDecompositionListener(IDecompositionListener listener) Removes the given dynamic decomposition listener such that it no longer receives PartitionCell subdivision and creation events from this decomposition.
void	setCutObstacleCost(double value) Sets the costs incurred for every Obstacle that must be cut in a subdivision.
void	setUnbalancedObstaclesCost(double value) Sets the costs incurred if the distribution after a subdivision of obstacles is unbalanced in sub-cells.
void	setUnbalancedRatioCost(double value) 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 new instance of DynamicObstacleDecomposition.

Method Detail

addDynamicDecompositionListener

public void addDynamicDecompositionListener(IDecompositionListener 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 IDynamicDecomposition

Parameters:

listener - the dynamic decomposition listener to add

See Also:

IDecompositionListener

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 IObstaclePartition

See Also:

init(List, YRectangle)

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:

IDecompositionListener

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:

IDecompositionListener

fireSubdividedEvent

protected void fireSubdividedEvent(PartitionCell cell,
                                   List<Object> 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:

IDecompositionListener

getBounds

public YRectangle getBounds()

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

Specified by:

getBounds in interface IPartition

Returns:

the bounds of the original rectangular area

getCells

public List<Object> getCells(Obstacle obstacle)

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

Specified by:

getCells in interface IObstaclePartition

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 List<Object> getCells(YRectangle rect)

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

Specified by:

getCells in interface IPartition

Parameters:

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

Returns:

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

getCutObstacleCost

public double getCutObstacleCost()

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

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 8.

Returns:

a non-negative cut cost

See Also:

setCutObstacleCost(double)

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 List<Object> getNeighbors(PartitionCell cell)

Returns the neighbor partition cells of the given cell.

Specified by:

getNeighbors in interface IPartition

Parameters:

cell - the cell whose neighbors will be returned

Returns:

the neighbor cells of the given cell

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

getObstacles

public List<Object> getObstacles(PartitionCell cell)

Returns all Obstacles that cover the given partition cell.

Specified by:

getObstacles in interface IObstaclePartition

Parameters:

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

Returns:

an unmodifiable list of Obstacle instances that cover the given cell

getUnbalancedObstaclesCost

public double getUnbalancedObstaclesCost()

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

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 2.

Returns:

a non-negative cost value

See Also:

setUnbalancedObstaclesCost(double)

getUnbalancedRatioCost

public double getUnbalancedRatioCost()

Gets the costs incurred if the subdivision produces unbalanced rectangles.

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 2.

Returns:

a non-negative cost value

See Also:

setUnbalancedRatioCost(double)

init

public void init(List<Object> 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 IObstaclePartition

Parameters:

obstacles - a list of Obstacle objects

partitionBounds - the bounds of the partition

See Also:

IObstaclePartition.clear()

removeDynamicDecompositionListener

public void removeDynamicDecompositionListener(IDecompositionListener 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 IDynamicDecomposition

Parameters:

listener - the dynamic decomposition listener to remove

See Also:

IDecompositionListener

setCutObstacleCost

public void setCutObstacleCost(double value)

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

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 8.

Parameters:

value - a non-negative cut cost

See Also:

getCutObstacleCost()

setUnbalancedObstaclesCost

public void setUnbalancedObstaclesCost(double value)

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

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 2.

Parameters:

value - a non-negative cost value

See Also:

getUnbalancedObstaclesCost()

setUnbalancedRatioCost

public void setUnbalancedRatioCost(double value)

Sets the costs incurred if the subdivision produces unbalanced rectangles.

Values need to be non-negative.

Throws:

IllegalArgumentException - if the cost is negative

Default Value:

The default value is 2.

Parameters:

value - a non-negative cost value

See Also:

getUnbalancedRatioCost()