dev.roanh.convexmerger.util

Class VerticalDecomposition.Trapezoid

java.lang.Object

dev.roanh.convexmerger.util.VerticalDecomposition.Trapezoid

Enclosing class:

VerticalDecomposition

public class VerticalDecomposition.Trapezoid
extends java.lang.Object

Defines the trapezoid structure that is used in the Vertical decomposition.

Field Summary

Fields

Modifier and Type	Field and Description
private VerticalDecomposition.Line	botSegment The segment that bound the trapezoid from the bottom.
private java.util.List<java.awt.geom.Line2D>	decompLines The decomposition lines of the trapezoid.
private java.util.List<java.awt.geom.Point2D>	leftPoints The points that bound the trapezoid from the left.
private java.util.List<VerticalDecomposition.Trapezoid>	neighbours The neighbouring trapezoids of the trapezoid.
private java.util.List<java.awt.geom.Point2D>	rightPoints The points that bound the trapezoid from the right.
private VerticalDecomposition.Line	topSegment The segment that bound the trapezoid from the top.
private VerticalDecomposition.DecompVertex	vertex The vertex that this trapezoid is linked to.

Constructor Summary

Constructors

Constructor and Description
Trapezoid(java.util.List<java.awt.geom.Point2D> left, java.util.List<java.awt.geom.Point2D> right, VerticalDecomposition.Line botSegment, VerticalDecomposition.Line topSegment) Constructs a trapezoid given lists of left and right bounding points, and the top and bottom bounding segments.
Trapezoid(java.util.List<java.awt.geom.Point2D> left, java.awt.geom.Point2D right, VerticalDecomposition.Line botSegment, VerticalDecomposition.Line topSegment) Constructs a trapezoid given a list of left bounding points and a right bounding point, and the top and bottom bounding segments.
Trapezoid(java.awt.geom.Point2D left, java.util.List<java.awt.geom.Point2D> right, VerticalDecomposition.Line botSegment, VerticalDecomposition.Line topSegment) Constructs a trapezoid given a left bounding point and a list of right bounding points, and the top and bottom bounding segments.
Trapezoid(java.awt.geom.Point2D left, java.awt.geom.Point2D right, VerticalDecomposition.Line botSegment, VerticalDecomposition.Line topSegment) Constructs a trapezoid given a left and a right bounding point, and the top and bottom bounding segments.

Method Summary

Modifier and Type	Method and Description
private void	addLeftPoint(java.awt.geom.Point2D point) Adds a left bounding point to the trapezoid.
private void	addNeighbour(VerticalDecomposition.Trapezoid neighbour) Adds a neighbour to the list of neighbours.
private void	addRightPoint(java.awt.geom.Point2D point) Adds a right bounding point to the trapezoid.
void	computeDecompLines() Computes and sets the decomposition lines related to this trapezoid.
private int	computeDepth(VerticalDecomposition.DecompVertex root) Computes the longest path from the given search structure vertex to the vertex associated with this trapezoid.
void	freeNeighbours() Removes this trapezoid from the neighbour lists of all neighbours and clears the neighbour list of this trapezoid.
java.awt.geom.Point2D	getCentroid() Returns the centroid of the trapezoid.
java.util.List<java.awt.geom.Line2D>	getDecompLines() Gets the vertical lines of this trapezoid.
VerticalDecomposition.DecompVertex	getDecompVertex() Gets the decomposition vertex that this trapezoid is linked to.
int	getDepth() Computes the maximum depth of this trapezoid in the search structure.
java.util.List<java.awt.geom.Point2D>	getEndPoints() Returns the points of the trapezoid in counterclockwise order.
java.awt.geom.Line2D	getLeftDecompLine() Gets the left vertical line of this trapezoid.
java.util.List<VerticalDecomposition.Trapezoid>	getNeighbours() Getter for the neighbours of the trapezoid.
ConvexObject	getObject() Returns the convex object that contains this trapezoid.
java.awt.geom.Line2D	getRightDecompLine() Gets the right vertical line of this trapezoid.
double	getXLeft() Getter for the X coordinate of the left wall of the trapezoid.
double	getXRight() Getter for the X coordinate of the right wall of the trapezoid.
boolean	intersectsSegment(java.awt.geom.Line2D segment) Checks whether a given line segment intersects with this trapezoid.
boolean	pointInside(double x, double y) Checks whether a point given by its coordinates is strictly inside a trapezoid.
boolean	pointInside(java.awt.geom.Point2D p) Checks whether a given point is strictly inside a trapezoid.
void	removeNeighbour(VerticalDecomposition.Trapezoid neighbour) Removes a neighbour from the list of neighbours.
void	sanitizeNeighbours() Removes undesired neighbourhoods of trapezoids.
void	setDecompVertex(VerticalDecomposition.DecompVertex vertex) Links the trapezoid to a Decomposition vertex.
java.awt.Shape	toShape() Computes the shape for this trapezoid.

Methods inherited from class java.lang.Object

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

Field Detail

topSegment

private VerticalDecomposition.Line topSegment

The segment that bound the trapezoid from the top.

botSegment

private VerticalDecomposition.Line botSegment

The segment that bound the trapezoid from the bottom.

leftPoints

private java.util.List<java.awt.geom.Point2D> leftPoints

The points that bound the trapezoid from the left.

rightPoints

private java.util.List<java.awt.geom.Point2D> rightPoints

The points that bound the trapezoid from the right.

neighbours

private java.util.List<VerticalDecomposition.Trapezoid> neighbours

The neighbouring trapezoids of the trapezoid.

vertex

private VerticalDecomposition.DecompVertex vertex

The vertex that this trapezoid is linked to.

decompLines

private java.util.List<java.awt.geom.Line2D> decompLines

The decomposition lines of the trapezoid.

Constructor Detail

Trapezoid

public Trapezoid(java.awt.geom.Point2D left,
                 java.awt.geom.Point2D right,
                 VerticalDecomposition.Line botSegment,
                 VerticalDecomposition.Line topSegment)

Constructs a trapezoid given a left and a right bounding point, and the top and bottom bounding segments. Also computes the vertical decomposition lines if at least one left and right point are passed.

Parameters:

left - The left bounding point of the trapezoid.

right - The right bounding point of the trapezoid.

botSegment - The bottom bounding segment of the trapezoid.

topSegment - The top bounding segment of the trapezoid.

Trapezoid

public Trapezoid(java.util.List<java.awt.geom.Point2D> left,
                 java.awt.geom.Point2D right,
                 VerticalDecomposition.Line botSegment,
                 VerticalDecomposition.Line topSegment)

Constructs a trapezoid given a list of left bounding points and a right bounding point, and the top and bottom bounding segments. Also computes the vertical decomposition lines if at least one left and right point are passed.

Parameters:

left - The left bounding point of the trapezoid.

right - The right bounding point of the trapezoid.

botSegment - The bottom bounding segment of the trapezoid.

topSegment - The top bounding segment of the trapezoid.

Trapezoid

public Trapezoid(java.awt.geom.Point2D left,
                 java.util.List<java.awt.geom.Point2D> right,
                 VerticalDecomposition.Line botSegment,
                 VerticalDecomposition.Line topSegment)

Constructs a trapezoid given a left bounding point and a list of right bounding points, and the top and bottom bounding segments. Also computes the vertical decomposition lines if at least one left and right point are passed.

Parameters:

left - The left bounding point of the trapezoid.

right - The right bounding point of the trapezoid.

botSegment - The bottom bounding segment of the trapezoid.

topSegment - The top bounding segment of the trapezoid.

Trapezoid

public Trapezoid(java.util.List<java.awt.geom.Point2D> left,
                 java.util.List<java.awt.geom.Point2D> right,
                 VerticalDecomposition.Line botSegment,
                 VerticalDecomposition.Line topSegment)

Constructs a trapezoid given lists of left and right bounding points, and the top and bottom bounding segments. Also computes the vertical decomposition lines if at least one left and right point are passed.

Parameters:

left - The left bounding point of the trapezoid.

right - The right bounding point of the trapezoid.

botSegment - The bottom bounding segment of the trapezoid.

topSegment - The top bounding segment of the trapezoid.

Method Detail

getDepth

public int getDepth()

Computes the maximum depth of this trapezoid in the search structure. Note that this will return the length of the longest path through the search structure DAG if more than one path leads to this trapezoid. Furthermore, note that this computation is relatively expensive.

Returns:

The maximum depth of this trapezoid.

computeDepth

private int computeDepth(VerticalDecomposition.DecompVertex root)

Computes the longest path from the given search structure vertex to the vertex associated with this trapezoid.

Parameters:

root - The vertex to treat as the search structure root.

Returns:

The maximum depth of this trapezoid in the search structure rooted at the given vertex.

getXLeft

public double getXLeft()

Getter for the X coordinate of the left wall of the trapezoid.

Returns:

The X coordinate of the left wall of the trapezoid.

getXRight

public double getXRight()

Getter for the X coordinate of the right wall of the trapezoid.

Returns:

The X coordinate of the right wall of the trapezoid.

getNeighbours

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

Getter for the neighbours of the trapezoid.

Returns:

The neighbours of the trapezoid.

addNeighbour

private void addNeighbour(VerticalDecomposition.Trapezoid neighbour)

Adds a neighbour to the list of neighbours.

Parameters:

neighbour - The neighbour to be added to the list.

removeNeighbour

public void removeNeighbour(VerticalDecomposition.Trapezoid neighbour)

Removes a neighbour from the list of neighbours.

Parameters:

neighbour - The neighbour to be removed.

freeNeighbours

public void freeNeighbours()

Removes this trapezoid from the neighbour lists of all neighbours and clears the neighbour list of this trapezoid.

sanitizeNeighbours

public void sanitizeNeighbours()

Removes undesired neighbourhoods of trapezoids. Assumes that the trapezoid has area.

This includes:

• Neighbours on the left (right) in case the top and bottom segment meet at the corresponding left or right bounding point of this trapezoid.
• Neighbours on the left (right) in case the top and bottom segment share the same X coordinate and there is a segment between the left (right) endpoints of the top and bottom segments.
• Neighbours who are somehow connected through the top (bottom) bounding segment.

getDecompLines

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

Gets the vertical lines of this trapezoid.

Returns:

The vertical lines of this trapezoid.

getLeftDecompLine

public java.awt.geom.Line2D getLeftDecompLine()

Gets the left vertical line of this trapezoid.

Returns:

The left vertical line of this trapezoid.

getRightDecompLine

public java.awt.geom.Line2D getRightDecompLine()

Gets the right vertical line of this trapezoid.

Returns:

The right vertical line of this trapezoid.

computeDecompLines

public void computeDecompLines()

Computes and sets the decomposition lines related to this trapezoid. The decomposition lines have x coordinates equal to the left and right bounding points, and they end at the bottomsegment and topsegment of the trapezoid. The endpoints of the decomposition lines can be used as points for the construction of a convex object that covers the trapezoid.

getDecompVertex

public VerticalDecomposition.DecompVertex getDecompVertex()

Gets the decomposition vertex that this trapezoid is linked to.

Returns:

The decomposition vertex that this trapezoid is linked to.

setDecompVertex

public void setDecompVertex(VerticalDecomposition.DecompVertex vertex)

Links the trapezoid to a Decomposition vertex.

Parameters:

vertex - The Decomposition vertex to link to.

intersectsSegment

public boolean intersectsSegment(java.awt.geom.Line2D segment)

Checks whether a given line segment intersects with this trapezoid.

Parameters:

segment - The line segment to check intersection with.

Returns:

True if the line segment is intersected, false otherwise.

pointInside

public boolean pointInside(double x,
                           double y)

Checks whether a point given by its coordinates is strictly inside a trapezoid.

Parameters:

x - The x coordinate of the point to check.

y - The y coordinate of the point to check.

Returns:

True if the point is contained in the trapezoid and not on the boundary, false otherwise.

pointInside

public boolean pointInside(java.awt.geom.Point2D p)

Checks whether a given point is strictly inside a trapezoid.

Parameters:

p - The point to check.

Returns:

True if the point is contained in the trapezoid and not on the boundary, false otherwise.

addLeftPoint

private void addLeftPoint(java.awt.geom.Point2D point)

Adds a left bounding point to the trapezoid. Also computes the vertical decomposition lines if this is the first left bounding point and at least 1 right bounding point exists.

Parameters:

point - The new left bounding point.

addRightPoint

private void addRightPoint(java.awt.geom.Point2D point)

Adds a right bounding point to the trapezoid. Also computes the vertical decomposition lines if this is the first right bounding point and at least 1 left bounding point exists.

Parameters:

point - The new right bounding point.

getCentroid

public java.awt.geom.Point2D getCentroid()

Returns the centroid of the trapezoid.

Returns:

the centroid of the trapezoid.

getEndPoints

public java.util.List<java.awt.geom.Point2D> getEndPoints()

Returns the points of the trapezoid in counterclockwise order.

Returns:

points of the trapezoid in counterclockwise order as a list.

getObject

public ConvexObject getObject()

Returns the convex object that contains this trapezoid. Returns null if no convex object contains it.

Returns:

The convex object that contains this trapezoid, or null if it is not part of any convex object.

toShape

public java.awt.Shape toShape()

Computes the shape for this trapezoid.

Returns:

The shape for this trapezoid.