dev.roanh.convexmerger.util

Class VerticalDecomposition

java.lang.Object

dev.roanh.convexmerger.animation.RenderableObject

dev.roanh.convexmerger.util.VerticalDecomposition

All Implemented Interfaces:

GameStateListener

public class VerticalDecomposition
extends RenderableObject
implements GameStateListener

Vertical decomposition of a plane containing non-overlapping convex objects. The decomposition supports efficient modifications and querying of the convex objects.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	VerticalDecomposition.DecompositionPoint A structure to represent a point in the vertical decomposition.
protected static class	VerticalDecomposition.DecompVertex Represents a vertex in the search structure of the decomposition.
static class	VerticalDecomposition.DecompVertexType Enum to denote the type of a decomposition vertex.
static class	VerticalDecomposition.Line A line instance with equality based on its end points, extended with information about decomposition trapezoids.
class	VerticalDecomposition.Trapezoid Defines the trapezoid structure that is used in the Vertical decomposition.

Field Summary

Fields

Modifier and Type	Field and Description
private boolean	animate True if the vertical decomposition is animated and showing individual segment updates.
private java.util.List<VerticalDecomposition.Line>	lines All line segments ever added into the vertical decomposition.
private java.util.List<VerticalDecomposition.Line>	orientedSegments The list of segments that have been added to the decomposition.
private java.util.List<VerticalDecomposition.DecompositionPoint>	points The list of points added to the decomposition.
private VerticalDecomposition.DecompVertex	searchStructure The search structure of the decomposition.
private java.util.Map<VerticalDecomposition.Line,ConvexObject>	segToObj Map of segments to the object above them or to null if that object is the playing field.
private java.util.List<VerticalDecomposition.Trapezoid>	trapezoids The trapezoids of the decomposition.
private java.util.List<VerticalDecomposition.Line>	verticalSegments The list of vertical segments.

Constructor Summary

Constructors

Constructor and Description
VerticalDecomposition() Constructs a new blank vertical decomposition with a corresponding search structure vertex.
VerticalDecomposition(java.util.List<ConvexObject> objects) Constructs a new vertical decomposition with the given objects.

Method Summary

Modifier and Type	Method and Description
void	abort() Called when the game is aborted (forcefully terminated).
private void	addedBorderVerticalSegment(VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid trap) Handles the case where the added vertical segment is on the inside of a single trapezoid.
private void	addedCompletelyInsideSingleTrapezoid(VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid trap) Updates the structures for case when the added segment fits entirely inside one trapezoid inside the decomposition.
private void	addedInternalVerticalSegment(VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid trap) Handles the case where the added vertical segment is on the inside of a single trapezoid.
private void	addedIntersectsMultipleTrapezoids(VerticalDecomposition.Line orientedSegment, ConvexObject obj) Updates the structures for case when the added segment crosses more than one trapezoid inside the decomposition.
private void	addedIntersectsSingleTrapezoid(VerticalDecomposition.Line segment) Adds a segment that only crosses one trapezoid inside the decomposition.
private void	addedOnRightBorder(VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid trap) Updates the structures for case when the added segment fits inside one trapezoid of the decomposition, except for its right ending point.
private void	addedVerticalSegment(VerticalDecomposition.Line segment) Updates the search structure for the case of an added vertical segment.
void	addObject(ConvexObject obj) Adds a new convex object to this vertical decomposition.
private void	addPoint(VerticalDecomposition.DecompositionPoint point) Adds a decomposition point to the list of decomposition points.
private void	addSegment(java.awt.geom.Line2D seg, ConvexObject obj) Adds a line segment belonging to an object to the vertical decomposition and updates the structures.
private void	addSegmentEndpointsAsTrapezoidBoundingPoints(VerticalDecomposition.Trapezoid start, VerticalDecomposition.Trapezoid end, VerticalDecomposition.Line segment) If the endpoints of the inserted segment are not bounding points of trapezoids whose boundaries they lie on, they are added to their bounding points.
private void	addTrapezoid(VerticalDecomposition.Trapezoid trap) Adds a trapezoid to the list of trapezoids.
void	claim(Player player, ConvexObject obj) Called when a player claims a new object.
private void	distributeRightPoints(VerticalDecomposition.Trapezoid trap, VerticalDecomposition.Trapezoid top, VerticalDecomposition.Trapezoid bot, VerticalDecomposition.Line segment) Distributes the right bounding points of a given trapezoid between the two trapezoids that it is being split into.
void	end() Called when the game ends.
private java.util.Queue<VerticalDecomposition.Trapezoid>	findIntersectedTrapezoids(java.awt.geom.Line2D seg, ConvexObject obj) Computes a list of trapezoids intersected by a line segment, excluding the leftmost and rightmost intersected trapezoids.
private void	finishBotTrapezoid(VerticalDecomposition.Trapezoid trap, VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid bot) Finishes a trapezoid that has just received one of the given parent trapezoid's right points below the given segment, and assigns neighbourhoods between itself and the current trapezoid's neighbours.
private void	finishTopTrapezoid(VerticalDecomposition.Trapezoid trap, VerticalDecomposition.Line segment, VerticalDecomposition.Trapezoid top) Finishes a trapezoid that has just received one of the given parent trapezoid's right points above the given segment, and assigns neighbourhoods between itself and the current trapezoid's neighbours.
java.util.List<java.awt.geom.Line2D>	getDecompLines() Gets a list of lines that represent the vertical decomposition lines.
private VerticalDecomposition.Trapezoid	getFirstIntersectedTrapezoid(java.awt.geom.Line2D seg) Gets the first trapezoid to the right that is run through by a given segment.
int	getHeight() Computes the height of the vertical decomposition as the length of the longest path to any trapezoid in the search structure.
java.awt.geom.Line2D	getLastLine() Gets the last line segment added into the vertical decomposition.
java.util.List<? extends java.awt.geom.Line2D>	getLines() Gets all lines that were ever added to the vertical decomposition.
ConvexObject	getObjectOfSegment(VerticalDecomposition.Line segment) Gets the object that the segment points to.
private VerticalDecomposition.DecompositionPoint	getOrCreatePoint(java.awt.geom.Point2D point) Gets the decomposition point at the given point or adds a new point if it doesn't exist and returns it.
private VerticalDecomposition.DecompositionPoint	getPoint(java.awt.geom.Point2D point) Gets a decomposition point for a given query point.
java.util.List<VerticalDecomposition.Trapezoid>	getTrapezoids() Gets all the trapezoids that make up the vertical decomposition.
private VerticalDecomposition.Trapezoid	handleFirstTrapezoid(VerticalDecomposition.Trapezoid trap, java.awt.geom.Point2D leftp) Handles the special case of the current trapezoid being the first of the many intersected by the inserted segment.
private VerticalDecomposition.Trapezoid	handleLastTrapezoid(VerticalDecomposition.Trapezoid trap, java.awt.geom.Point2D rightp) Handles the special case of the current trapezoid being the last of the many intersected by the inserted segment.
boolean	isAnimated() Checks if the vertical decomposition is animated, meaning it is showing individual segment updates.
void	merge(Player player, ConvexObject source, ConvexObject target, ConvexObject result, java.util.List<ConvexObject> absorbed) Called when a player performs a merge.
private VerticalDecomposition.Trapezoid	newBot(VerticalDecomposition.Trapezoid trap, VerticalDecomposition.Line segment) Creates a new trapezoid from the part of a given trapezoid that lies below a given segment.
private VerticalDecomposition.Trapezoid	newTop(VerticalDecomposition.Trapezoid trap, VerticalDecomposition.Line segment) Creates a new trapezoid from the part of a given trapezoid that lies above a given segment.
ConvexObject	queryObject(double x, double y) Queries the convex object that is at the given position.
VerticalDecomposition.Trapezoid	queryTrapezoid(double x, double y) Queries the trapezoid that is at the given position.
VerticalDecomposition.Trapezoid	queryTrapezoid(java.awt.geom.Point2D point) Queries the trapezoid that is at the given position.
private void	removePoint(VerticalDecomposition.DecompositionPoint point) Removes a decomposition point from the list of decomposition points.
private void	removeTrapezoid(VerticalDecomposition.Trapezoid trap) Removes a trapezoid from the structure, freeing its neighbours and disassociating it from its decomposition vertex.
void	render(java.awt.Graphics2D g) Renders this object.
private void	replaceOverlappedSegment(VerticalDecomposition.Line shortLine, VerticalDecomposition.Line line) Replaces a given line segment and line segments between its end points and points collinear with the line, with a segment that overlaps the union of the shorter line segments.
void	setAnimated(boolean animated) Sets whether the vertical decomposition is animated and showing individual segment updates.

Methods inherited from class dev.roanh.convexmerger.animation.RenderableObject

getAnimation, hasAnimation, renderOrAnimate, runAnimation, setAnimation

Methods inherited from class java.lang.Object

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

Field Detail

trapezoids

private final java.util.List<VerticalDecomposition.Trapezoid> trapezoids

The trapezoids of the decomposition.

searchStructure

private final VerticalDecomposition.DecompVertex searchStructure

The search structure of the decomposition. It is a DAG with 3 types of vertices (leaf, point, and segment).

orientedSegments

private java.util.List<VerticalDecomposition.Line> orientedSegments

The list of segments that have been added to the decomposition.

verticalSegments

private java.util.List<VerticalDecomposition.Line> verticalSegments

The list of vertical segments.

segToObj

private java.util.Map<VerticalDecomposition.Line,ConvexObject> segToObj

Map of segments to the object above them or to null if that object is the playing field.

points

private java.util.List<VerticalDecomposition.DecompositionPoint> points

The list of points added to the decomposition.

lines

private java.util.List<VerticalDecomposition.Line> lines

All line segments ever added into the vertical decomposition.

animate

private boolean animate

True if the vertical decomposition is animated and showing individual segment updates.

Constructor Detail

VerticalDecomposition

public VerticalDecomposition()

Constructs a new blank vertical decomposition with a corresponding search structure vertex. The size of the vertical decomposition is defined by Constants.PLAYFIELD_WIDTH and Constants.PLAYFIELD_HEIGHT.

VerticalDecomposition

public VerticalDecomposition(java.util.List<ConvexObject> objects)
                      throws java.lang.InterruptedException

Constructs a new vertical decomposition with the given objects. The decomposition is initialised and all objects get decomposed, i.e. their segments are added to the decomposition. The size of the vertical decomposition is defined by Constants.PLAYFIELD_WIDTH and Constants.PLAYFIELD_HEIGHT.

Parameters:

objects - The objects that the vertical decomposition will contain at the beginning.

Throws:

java.lang.InterruptedException - When the game is aborted.

Method Detail

getLines

public java.util.List<? extends java.awt.geom.Line2D> getLines()

Gets all lines that were ever added to the vertical decomposition.

Returns:

All line segments ever added.

getLastLine

public java.awt.geom.Line2D getLastLine()

Gets the last line segment added into the vertical decomposition.

Returns:

The last line segment added to the vertical decomposition.

getObjectOfSegment

public ConvexObject getObjectOfSegment(VerticalDecomposition.Line segment)

Gets the object that the segment points to. If the segment is part of an object and during addition it is oriented from left-to-right (in case of a tie, bottom to top), the segment will point to an object, otherwise to null.

Parameters:

segment - The segment for which to fetch its object.

Returns:

The object for this segment, null in case the segment is oriented from right to left during addition (on the top of the object).

setAnimated

public void setAnimated(boolean animated)

Sets whether the vertical decomposition is animated and showing individual segment updates.

Parameters:

animated - True to animate segment updates.

getTrapezoids

public java.util.List<VerticalDecomposition.Trapezoid> getTrapezoids()

Gets all the trapezoids that make up the vertical decomposition.

Returns:

All decomposition trapezoids.

addTrapezoid

private void addTrapezoid(VerticalDecomposition.Trapezoid trap)

Adds a trapezoid to the list of trapezoids.

Parameters:

trap - The trapezoid to be added to the list.

removeTrapezoid

private void removeTrapezoid(VerticalDecomposition.Trapezoid trap)

Removes a trapezoid from the structure, freeing its neighbours and disassociating it from its decomposition vertex.

Parameters:

trap - The trapezoid to be removed.

addObject

public void addObject(ConvexObject obj)
               throws java.lang.InterruptedException

Adds a new convex object to this vertical decomposition.

Parameters:

obj - The convex object to add.

Throws:

java.lang.InterruptedException - When the game is aborted.

isAnimated

public boolean isAnimated()

Checks if the vertical decomposition is animated, meaning it is showing individual segment updates.

Returns:

True if the vertical decomposition is animated.

queryObject

public ConvexObject queryObject(double x,
                                double y)

Queries the convex object that is at the given position. If no such object exists null is returned.

Parameters:

x - The x-coordinate of the query point.

y - The y-coordinate of the query point.

Returns:

The convex object at the given position or null if there is no convex object at the given position.

queryTrapezoid

public VerticalDecomposition.Trapezoid queryTrapezoid(double x,
                                                      double y)

Queries the trapezoid that is at the given position. If no such trapezoid exists null is returned.

Parameters:

x - The x-coordinate of the query point.

y - The y-coordinate of the query point.

Returns:

The convex object at the given position or null is there is no convex object at the given position.

queryTrapezoid

public VerticalDecomposition.Trapezoid queryTrapezoid(java.awt.geom.Point2D point)

Queries the trapezoid that is at the given position. If no such trapezoid exists null is returned.

Parameters:

point - The query point.

Returns:

The convex object at the given position or null is there is no convex object at the given position.

getHeight

public int getHeight()

Computes the height of the vertical decomposition as the length of the longest path to any trapezoid in the search structure. Note that the implementation for this method is not very efficient, so a call to this method may take relatively long to complete.

Returns:

The height of the vertical decomposition.

See Also:

VerticalDecomposition.Trapezoid.getDepth()

getDecompLines

public java.util.List<java.awt.geom.Line2D> getDecompLines()

Gets a list of lines that represent the vertical decomposition lines. Lines to represent the bounding box will be included as well.

Returns:

The vertical decomposition lines.

getOrCreatePoint

private VerticalDecomposition.DecompositionPoint getOrCreatePoint(java.awt.geom.Point2D point)

Gets the decomposition point at the given point or adds a new point if it doesn't exist and returns it.

Parameters:

point - The point at which to add a new decomposition point.

Returns:

The added decomposition point or the existing decomposition point at this point.

addPoint

private void addPoint(VerticalDecomposition.DecompositionPoint point)

Adds a decomposition point to the list of decomposition points.

Parameters:

point - The decomposition point to add to the list.

removePoint

private void removePoint(VerticalDecomposition.DecompositionPoint point)

Removes a decomposition point from the list of decomposition points.

Parameters:

point - The decomposition point to remove from the list.

getPoint

private VerticalDecomposition.DecompositionPoint getPoint(java.awt.geom.Point2D point)

Gets a decomposition point for a given query point.

Parameters:

point - The query point to look for in the list.

Returns:

The query point if it is in the list, or null otherwise.

getFirstIntersectedTrapezoid

private VerticalDecomposition.Trapezoid getFirstIntersectedTrapezoid(java.awt.geom.Line2D seg)

Gets the first trapezoid to the right that is run through by a given segment.

Parameters:

seg - The query segment. The first point is assumed to lie to the left, or below the second point.

Returns:

The first trapezoid to the right run through by the segment.

replaceOverlappedSegment

private void replaceOverlappedSegment(VerticalDecomposition.Line shortLine,
                                      VerticalDecomposition.Line line)

Replaces a given line segment and line segments between its end points and points collinear with the line, with a segment that overlaps the union of the shorter line segments.

Parameters:

shortLine - The central line segment (short merge line).

line - The overlapping union segment.

addSegment

private void addSegment(java.awt.geom.Line2D seg,
                        ConvexObject obj)
                 throws java.lang.InterruptedException

Adds a line segment belonging to an object to the vertical decomposition and updates the structures.

Parameters:

seg - The line segment to add to the decomposition.

obj - The object that the segment belongs to.

Throws:

java.lang.InterruptedException - When the game is aborted.

addedVerticalSegment

private void addedVerticalSegment(VerticalDecomposition.Line segment)

Updates the search structure for the case of an added vertical segment.

Parameters:

segment - The added segment. Its first point is always the lower leftmost point.

addedInternalVerticalSegment

private void addedInternalVerticalSegment(VerticalDecomposition.Line segment,
                                          VerticalDecomposition.Trapezoid trap)

Handles the case where the added vertical segment is on the inside of a single trapezoid.

Parameters:

segment - The added vertical segment.

trap - The trapezoid that contains the segment.

addedBorderVerticalSegment

private void addedBorderVerticalSegment(VerticalDecomposition.Line segment,
                                        VerticalDecomposition.Trapezoid trap)

Handles the case where the added vertical segment is on the inside of a single trapezoid.

Parameters:

segment - The added vertical segment.

trap - The trapezoid whose border the segment lies on.

addedIntersectsSingleTrapezoid

private void addedIntersectsSingleTrapezoid(VerticalDecomposition.Line segment)

Adds a segment that only crosses one trapezoid inside the decomposition.

Parameters:

segment - The segment to add to the decomposition.

addedCompletelyInsideSingleTrapezoid

private void addedCompletelyInsideSingleTrapezoid(VerticalDecomposition.Line segment,
                                                  VerticalDecomposition.Trapezoid trap)

Updates the structures for case when the added segment fits entirely inside one trapezoid inside the decomposition.

Parameters:

segment - The segment that was added.

trap - The trapezoid that the segment is contained inside.

addedOnRightBorder

private void addedOnRightBorder(VerticalDecomposition.Line segment,
                                VerticalDecomposition.Trapezoid trap)

Updates the structures for case when the added segment fits inside one trapezoid of the decomposition, except for its right ending point.

Parameters:

segment - The segment that was added.

trap - The trapezoid that the segment is contained inside.

addedIntersectsMultipleTrapezoids

private void addedIntersectsMultipleTrapezoids(VerticalDecomposition.Line orientedSegment,
                                               ConvexObject obj)

Updates the structures for case when the added segment crosses more than one trapezoid inside the decomposition.

Parameters:

orientedSegment - The segment that was added to the decomposition.

obj - The object that orientedSegment should point towards.

addSegmentEndpointsAsTrapezoidBoundingPoints

private void addSegmentEndpointsAsTrapezoidBoundingPoints(VerticalDecomposition.Trapezoid start,
                                                          VerticalDecomposition.Trapezoid end,
                                                          VerticalDecomposition.Line segment)

If the endpoints of the inserted segment are not bounding points of trapezoids whose boundaries they lie on, they are added to their bounding points. This only has effect if the segment's endpoints were not part of the decomposition until now.

Parameters:

start - The starting Trapezoid that was intersected by the segment.

end - The ending Trapezoid that was intersected by the segment.

segment - THe newly added segment.

handleFirstTrapezoid

private VerticalDecomposition.Trapezoid handleFirstTrapezoid(VerticalDecomposition.Trapezoid trap,
                                                             java.awt.geom.Point2D leftp)

Handles the special case of the current trapezoid being the first of the many intersected by the inserted segment. Splits it into left and right. The right trapezoid can be handled as one that is entirely split by the segment.

Parameters:

trap - The trapezoid intersected by the inserted segment.

leftp - The left point of the inserted segment.

Returns:

The left trapezoid, to be split into top and bottom part.

handleLastTrapezoid

private VerticalDecomposition.Trapezoid handleLastTrapezoid(VerticalDecomposition.Trapezoid trap,
                                                            java.awt.geom.Point2D rightp)

Handles the special case of the current trapezoid being the last of the many intersected by the inserted segment. Splits it into left and right. The left trapezoid can be handled as as one that is entirely split by the segment.

Parameters:

trap - The trapezoid intersected by the inserted segment.

rightp - The right point of the inserted segment.

Returns:

The left trapezoid, to be split into top and bottom part.

newTop

private VerticalDecomposition.Trapezoid newTop(VerticalDecomposition.Trapezoid trap,
                                               VerticalDecomposition.Line segment)

Creates a new trapezoid from the part of a given trapezoid that lies above a given segment.

Parameters:

trap - The trapezoid that is split.

segment - The newly inserted segment that splits the trapezoid.

Returns:

A new trapezoid that spans the part of the trapezoid above the segment.

newBot

private VerticalDecomposition.Trapezoid newBot(VerticalDecomposition.Trapezoid trap,
                                               VerticalDecomposition.Line segment)

Creates a new trapezoid from the part of a given trapezoid that lies below a given segment.

Parameters:

trap - The trapezoid that is split.

segment - The newly inserted segment that splits the trapezoid.

Returns:

A new trapezoid that spans the part of the trapezoid below the segment.

distributeRightPoints

private void distributeRightPoints(VerticalDecomposition.Trapezoid trap,
                                   VerticalDecomposition.Trapezoid top,
                                   VerticalDecomposition.Trapezoid bot,
                                   VerticalDecomposition.Line segment)

Distributes the right bounding points of a given trapezoid between the two trapezoids that it is being split into. The right bounding points get split according their position w.r.t. the given segment.

Parameters:

trap - The initial trapezoid that is being split.

top - The top trapezoid resulting from the split.

bot - The bottom trapezoid resulting from the split.

segment - The inserted line segment that splits the trapezoid into top and bot.

finishTopTrapezoid

private void finishTopTrapezoid(VerticalDecomposition.Trapezoid trap,
                                VerticalDecomposition.Line segment,
                                VerticalDecomposition.Trapezoid top)

Finishes a trapezoid that has just received one of the given parent trapezoid's right points above the given segment, and assigns neighbourhoods between itself and the current trapezoid's neighbours.

Parameters:

trap - The parent trapezoid.

segment - The splitting segment, which is the bottom bounding segment of top.

top - The top trapezoid created by splitting trap with segment.

finishBotTrapezoid

private void finishBotTrapezoid(VerticalDecomposition.Trapezoid trap,
                                VerticalDecomposition.Line segment,
                                VerticalDecomposition.Trapezoid bot)

Finishes a trapezoid that has just received one of the given parent trapezoid's right points below the given segment, and assigns neighbourhoods between itself and the current trapezoid's neighbours.

Parameters:

trap - The parent trapezoid.

segment - The splitting segment, which is the top bounding segment of bot.

bot - The bottom trapezoid created by splitting trap with segment.

findIntersectedTrapezoids

private java.util.Queue<VerticalDecomposition.Trapezoid> findIntersectedTrapezoids(java.awt.geom.Line2D seg,
                                                                                   ConvexObject obj)

Computes a list of trapezoids intersected by a line segment, excluding the leftmost and rightmost intersected trapezoids.

Parameters:

seg - The line segment.

obj - The object that the segment is added for.

Returns:

A list of trapezoids intersected by a line segment, excluding the leftmost and rightmost intersected trapezoids.

claim

public void claim(Player player,
                  ConvexObject obj)

Description copied from interface: GameStateListener

Called when a player claims a new object.

Specified by:

claim in interface GameStateListener

Parameters:

player - The player that made the claim.

obj - The object that was claimed.

merge

public void merge(Player player,
                  ConvexObject source,
                  ConvexObject target,
                  ConvexObject result,
                  java.util.List<ConvexObject> absorbed)
           throws java.lang.InterruptedException

Description copied from interface: GameStateListener

Called when a player performs a merge.

Specified by:

merge in interface GameStateListener

Parameters:

player - The player that performed the merge.

source - The object the merge was started from.

target - The target object of the merge.

result - The object resulting from the merge.

absorbed - The objects absorbed in the merge.

Throws:

java.lang.InterruptedException - When the player was interrupted while making its move. Signalling that the game was aborted.

end

public void end()

Description copied from interface: GameStateListener

Called when the game ends.

Specified by:

end in interface GameStateListener

abort

public void abort()

Description copied from interface: GameStateListener

Called when the game is aborted (forcefully terminated).

Specified by:

abort in interface GameStateListener

render

public void render(java.awt.Graphics2D g)

Description copied from class: RenderableObject

Renders this object.

Specified by:

render in class RenderableObject

Parameters:

g - The graphics context to use.