dev.roanh.convexmerger.util

Class ConjugationTree<T>

java.lang.Object

dev.roanh.convexmerger.animation.RenderableObject

dev.roanh.convexmerger.util.PartitionTree<T,ConjugationTree<T>>

dev.roanh.convexmerger.util.ConjugationTree<T>

Type Parameters:

T - The metadata storage type.

public class ConjugationTree<T>
extends PartitionTree<T,ConjugationTree<T>>

Implementation of a conjugation tree inspired by the description in a paper by Herbert Edelsbrunner and Emo Welzl.

See Also:

Edelsbrunner, Herbert and Welzl, Emo, "Halfplanar range search in linear space and O(n^0.695) query time", in Information Processing Letters, vol. 23, 1986, pp. 289-293

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ConjugationTree.ConjugateData Class holding data about a single conjugate line.

Field Summary

Fields

Modifier and Type	Field and Description
private java.awt.geom.Line2D	bisector The bisector of this tree node (a conjugate of the parent bisector).
private java.util.List<java.awt.geom.Point2D>	hull The convex hull defining the bounds of this tree cell.
private ConjugationTree<T>	left The left child node of this node (containing CCW -1 points).
private java.util.List<java.awt.geom.Point2D>	on The points in this cell on the bisector line.
private ConjugationTree<T>	parent The parent node of this tree node.
private ConjugationTree<T>	right The right child node of this node (containing CCW 1 points).
private java.awt.geom.Path2D	shape The shape defining the bounds of this cell as constructed from the convex hull points in hull.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	ConjugationTree(ConjugationTree<T> parent, java.util.List<java.awt.geom.Point2D> points, java.awt.geom.Point2D on, java.awt.geom.Line2D bisector, java.util.List<java.awt.geom.Point2D> hull) Constructs a new child conjugation tree node with the given parent node, point set, conjugate bisector line and convex hull.
	ConjugationTree(java.util.List<java.awt.geom.Point2D> points) Constructs a new conjugation tree storing the given point set.

Method Summary

Modifier and Type	Method and Description
private static java.util.Comparator<java.awt.geom.Point2D>	angularComparator(java.awt.geom.Line2D vector) A comparator that compares points based on their angle to a fixed point, relative to the angle of a fixed "base" vector.
private static java.awt.geom.Line2D	clipLine(ConjugationTree<?> node, java.awt.geom.Line2D line, java.awt.geom.Point2D on) Clips the given line segment to be fully contained within the bounds of the given conjugation tree node.
private static ConjugationTree.ConjugateData	computeConjugate(java.util.List<java.awt.geom.Point2D> left, java.util.List<java.awt.geom.Point2D> right, ConjugationTree<?> parent) Computes a conjugate line for the given point sets and with the given parent conjugation tree node.
private void	constructShape() Constructs the shape object for the bounds of this object.
private static java.awt.geom.Line2D	extendLine(java.awt.geom.Line2D line) Extends the given closed line segment to the geometric bounds of this partition tree as defined by Constants.PLAYFIELD_HEIGHT and Constants.PLAYFIELD_WIDTH.
private static Segment	findUnusedSegment(java.util.List<java.awt.geom.Point2D> left, java.util.List<java.awt.geom.Point2D> right, java.util.Set<Segment> used, Segment fallback) Searches for lines that are not marked as used and similar to the segment between the median points of two sorted point lists.
java.awt.geom.Line2D	getBisector() Gets the bisector line for this tree node.
java.awt.geom.Point2D	getCentroid() Gets the centroid of this conjugation tree node.
java.util.List<ConjugationTree<T>>	getChildren() Gets the child nodes of this tree node.
ConjugationTree<T>	getLeftChild() Gets the left child node of this tree node (CCW -1).
ConjugationTree<T>	getParent() Gets the parent tree node of this node.
java.util.List<java.awt.geom.Point2D>	getPoints() Gets all the points located on the bisector for this tree cell.
ConjugationTree<T>	getRightChild() Gets the right child node of this tree node (CCW 1).
ConjugationTree<T>	getSelf() Gets 'this' partition tree.
java.awt.Shape	getShape() Gets the shape defining the boundary of this tree cell.
boolean	isLeafCell() Checks if this tree node is a leaf cell.
private static Segment	orientedLine(java.awt.geom.Point2D p1, java.awt.geom.Point2D p2) Create an oriented line segment given two points.
void	render(java.awt.Graphics2D g) Renders this object.
private static java.util.Comparator<java.awt.geom.Point2D>	segmentProjectionComparator(java.awt.geom.Line2D segment) Sorts the points on the order of their projections onto a segment, from the direction of its first point to the direction of its second point.

Methods inherited from class dev.roanh.convexmerger.util.PartitionTree

addData, getData, getDepth, getHeight, setMarked, streamCells, streamLeafCells

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

parent

private ConjugationTree<T> parent

The parent node of this tree node.

bisector

private java.awt.geom.Line2D bisector

The bisector of this tree node (a conjugate of the parent bisector). Cells without a bisector are leaf nodes.

on

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

The points in this cell on the bisector line. Only inner nodes have points, leaf nodes do not (since they have no bisector).

left

private ConjugationTree<T> left

The left child node of this node (containing CCW -1 points).

right

private ConjugationTree<T> right

The right child node of this node (containing CCW 1 points).

hull

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

The convex hull defining the bounds of this tree cell.

shape

private java.awt.geom.Path2D shape

The shape defining the bounds of this cell as constructed from the convex hull points in hull.

Constructor Detail

ConjugationTree

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

Constructs a new conjugation tree storing the given point set.

Parameters:

points - The point set to store.

ConjugationTree

private ConjugationTree(ConjugationTree<T> parent,
                        java.util.List<java.awt.geom.Point2D> points,
                        java.awt.geom.Point2D on,
                        java.awt.geom.Line2D bisector,
                        java.util.List<java.awt.geom.Point2D> hull)

Constructs a new child conjugation tree node with the given parent node, point set, conjugate bisector line and convex hull.

Parameters:

parent - The parent node for this conjugation tree node.

points - The points stored at or below this tree node.

on - The points on the bisector for this tree node.

bisector - The bisector for this tree node (conjugate of the parent bisector).

hull - The convex hull for this tree cell.

Method Detail

constructShape

private void constructShape()

Constructs the shape object for the bounds of this object.

getPoints

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

Gets all the points located on the bisector for this tree cell.

Returns:

The points on the bisector of this tree node.

getBisector

public java.awt.geom.Line2D getBisector()

Gets the bisector line for this tree node. This line splits this tree cell in two halves with both about the same number of points.

Returns:

The bisector for this tree cell.

getLeftChild

public ConjugationTree<T> getLeftChild()

Gets the left child node of this tree node (CCW -1).

Returns:

The left child node of null if this node is a leaf.

getRightChild

public ConjugationTree<T> getRightChild()

Gets the right child node of this tree node (CCW 1).

Returns:

The right child node of null if this node is a leaf.

getCentroid

public java.awt.geom.Point2D getCentroid()

Gets the centroid of this conjugation tree node.

Returns:

The centroid.

render

public void render(java.awt.Graphics2D g)

Description copied from class: RenderableObject

Renders this object.

Overrides:

render in class PartitionTree<T,ConjugationTree<T>>

Parameters:

g - The graphics context to use.

getShape

public java.awt.Shape getShape()

Description copied from class: PartitionTree

Gets the shape defining the boundary of this tree cell.

Specified by:

getShape in class PartitionTree<T,ConjugationTree<T>>

Returns:

The partition tree cell bounds.

getParent

public ConjugationTree<T> getParent()

Description copied from class: PartitionTree

Gets the parent tree node of this node.

Specified by:

getParent in class PartitionTree<T,ConjugationTree<T>>

Returns:

The parent node of this node or null if this is node is the root node of the tree.

isLeafCell

public boolean isLeafCell()

Description copied from class: PartitionTree

Checks if this tree node is a leaf cell.

Specified by:

isLeafCell in class PartitionTree<T,ConjugationTree<T>>

Returns:

True if this tree node is a leaf cell.

getChildren

public java.util.List<ConjugationTree<T>> getChildren()

Description copied from class: PartitionTree

Gets the child nodes of this tree node.

Specified by:

getChildren in class PartitionTree<T,ConjugationTree<T>>

Returns:

The direct child nodes of this node.

getSelf

public ConjugationTree<T> getSelf()

Description copied from class: PartitionTree

Gets 'this' partition tree.

Specified by:

getSelf in class PartitionTree<T,ConjugationTree<T>>

Returns:

This partition tree.

clipLine

private static final java.awt.geom.Line2D clipLine(ConjugationTree<?> node,
                                                   java.awt.geom.Line2D line,
                                                   java.awt.geom.Point2D on)

Clips the given line segment to be fully contained within the bounds of the given conjugation tree node. The given point is assumed to lie on the given line segment and within the given tree node.

Parameters:

node - The tree node to contain the line within.

line - The line to clip.

on - A point on the given line and within the tree node.

Returns:

The clipped line segment.

extendLine

private static final java.awt.geom.Line2D extendLine(java.awt.geom.Line2D line)

Extends the given closed line segment to the geometric bounds of this partition tree as defined by Constants.PLAYFIELD_HEIGHT and Constants.PLAYFIELD_WIDTH. The result being a new closed line segment ending on the bounds of the partition tree.

Parameters:

line - The line to extend.

Returns:

The line segment extended to the structure bounds.

computeConjugate

private static final ConjugationTree.ConjugateData computeConjugate(java.util.List<java.awt.geom.Point2D> left,
                                                                    java.util.List<java.awt.geom.Point2D> right,
                                                                    ConjugationTree<?> parent)

Computes a conjugate line for the given point sets and with the given parent conjugation tree node. All the points in the left set are left (CCW -1) of the bisector of the given parent tree node and all the points in the right set are right (CCW 1) of the bisector of the parent node. The left and right sets also have approximately the same size. The conjugate line computed by this subroutine will split the given left and right point sets in two subsets of approximately equal size and the conjugate line will also intersect the bisector of the given parent node. In addition, the conjugate line will pass through at least one point from the left point set and at least one point from the right point set. These points together with the computed conjugate line will be returned from this subroutine. If either of the given point sets is empty then the conjugate can be any line that splits the other point set and intersects the parent node bisector.

Parameters:

left - The left point set to split.

right - The right point set to split.

parent - The parent conjugation tree node.

Returns:

The computed conjugate line and its supporting points.

segmentProjectionComparator

private static final java.util.Comparator<java.awt.geom.Point2D> segmentProjectionComparator(java.awt.geom.Line2D segment)

Sorts the points on the order of their projections onto a segment, from the direction of its first point to the direction of its second point.

Parameters:

segment - The segment on which to project

Returns:

A comparator that orders points on their projection along a segment.

findUnusedSegment

private static final Segment findUnusedSegment(java.util.List<java.awt.geom.Point2D> left,
                                               java.util.List<java.awt.geom.Point2D> right,
                                               java.util.Set<Segment> used,
                                               Segment fallback)

Searches for lines that are not marked as used and similar to the segment between the median points of two sorted point lists.

Parameters:

left - The first sorted point list.

right - The second sorted point list.

used - The set of used lines.

fallback - The original segment to return in case no segment is found.

Returns:

The list-wise closest segment. The distance is minimized first on left list, then on the right list. If no unused line is found after reaching maxDistance, the segment between the median points of the two sorted point lists is returned.

angularComparator

private static final java.util.Comparator<java.awt.geom.Point2D> angularComparator(java.awt.geom.Line2D vector)

A comparator that compares points based on their angle to a fixed point, relative to the angle of a fixed "base" vector. The orientation of the points relative to the vector matters, as angles > PI rad are considered as negative.

Parameters:

vector - The fixed "base" vector, represented as a line.

Returns:

A comparator that sorts points based on their angle to the base vector.

orientedLine

private static final Segment orientedLine(java.awt.geom.Point2D p1,
                                          java.awt.geom.Point2D p2)

Create an oriented line segment given two points. The orientation is from left-bottom to right-top.

Parameters:

p1 - The first point.

p2 - The second point.

Returns:

An oriented line segment where the first point is the leftmost-lower point, and the second point is the rightmost-upper point.