movingregion
Class ConvexHullTreeNode

java.lang.Object
  |
  +--movingregion.ConvexHullTreeNode

public class ConvexHullTreeNode
extends java.lang.Object

This class represents a node in the convex hull tree. The node contains a polygon representation of an object or concavity, and links to child nodes representing concavities in the object. The polygon represented in a convex hull tree node is convex.


Field Summary
static int X_DISP
           
static int Y_DISP
           
 
Constructor Summary
ConvexHullTreeNode()
          Creates an empty convex hull tree node
ConvexHullTreeNode(LineWA[] linelist, double min, double minmatch)
          Creates a convex hull tree from the given polygon.
ConvexHullTreeNode(LineWA[] linelist, int level, double min, double minmatch)
          Creates a convex hull tree from the given polygon.
 
Method Summary
 ConvexHullTreeNode createChild(int lineindex)
          This function creates an empty convex hull tree node and associates it with a given line in this object.
 int[] drawThis(java.awt.Graphics g, int xdisp, int ydisp)
          This function draws this convex hull three node in a "flattened" way.
 void drawTree(java.awt.Graphics g, int xdisp, int ydisp)
          Draws the convex hull tree with this node as its root.
 ConvexHullTreeNode[] getChildren()
          Returns all children of this node.
 LineWA getLine(int index)
          This function returns the line at a given position in the line list.
 LineWA[] getLineForChild(ConvexHullTreeNode child)
          This function finds the line a given child of this node is associated with.
 LineWA[] getLines()
          Gets the polygon stored in the convex hull tree that has this node as its root.
 LineWA[] getOrderedOutLine()
          Gets the polygon stored in the node with the point with the smallest y-coordinate first.
 LineWA[] getOutLine()
          Gets the polygon stored in the node in the order in which it is stored internally.
 OverlapGraphEdge[] getOverlapEdges()
          Returns all overlap graph edges going from this node.
 ConvexHullTreeNode[] getOverlappingNodes()
          Returns all convex hull tree nodes that overlaps with this node.
 int getSmallestPoint()
          Gets the smallest point.
 void insertChild(int lineindex, ConvexHullTreeNode child)
          This function links a particular line in this object to a given convex hull tree node, thereby making it a child of this node.
 int insertLine(LineWA line)
          This function inserts a new line at the end of the list of lines defining the polygon represented by this object.
 void insertOverlap(double amount, ConvexHullTreeNode node)
          This function inserts an overlap graph edge between this node and another node.
 boolean isMatched()
          Finds whether this object has already been matched to another convex hull tree node or not.
 LineWA[] joinChildren(ConvexHullTreeNode[] tojoin)
          This function takes the given nodes, which must be children of this node, and creates a single convex hull tree node out of them.
 int numberOfLines()
          Finds the number of lines that makes op the polygon stored in this node.
 void removeAllOverlaps()
          Removes all overlap edges going out from this node.
 void removeLine(int index)
          This function removes a line from the polygon.
 void removeOverlap(ConvexHullTreeNode node)
          This function removes an overlap graph edge between this node and another node.
 void setMatched(boolean val)
          Sets the variable indicating whether this object has been matched to another or not.
 void sortOverlapEdges()
          This function sorts the overlap graph edges of this node by the amount of overlap.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

Y_DISP

public static final int Y_DISP

X_DISP

public static final int X_DISP
Constructor Detail

ConvexHullTreeNode

public ConvexHullTreeNode()
Creates an empty convex hull tree node

ConvexHullTreeNode

public ConvexHullTreeNode(LineWA[] linelist,
                          double min,
                          double minmatch)
Creates a convex hull tree from the given polygon. If the region defined by the polygon is not convex, this constructor will also create the necessary subnodes. This constructor assumes that this node will be the root of the convex hull tree.
Parameters:
linelist - The polygon represented as a list of LineWA objects.
min - The minimum overlap required for an edge to be added to the overlap graph
minmatch - The minimum overlap required for two convex hull tree nodes to match.

ConvexHullTreeNode

public ConvexHullTreeNode(LineWA[] linelist,
                          int level,
                          double min,
                          double minmatch)
Creates a convex hull tree from the given polygon. If the region defined by the polygon is not convex, this constructor will also create the necessary subnodes.
Parameters:
linelist - The polygon represented as a list of LineWA objects.
level - Which level of the convex hull tree this node is on
min - The minimum overlap required for an edge to be added to the overlap graph
minmatch - The minimum overlap required for two convex hull tree nodes to match.
Method Detail

insertLine

public int insertLine(LineWA line)
This function inserts a new line at the end of the list of lines defining the polygon represented by this object.
Parameters:
line - The line represented by a LineWA object.
Returns:
The index of the new line in the list of lines.

removeLine

public void removeLine(int index)
This function removes a line from the polygon.
Parameters:
index - The line represented by its index in the list of lines.

getLine

public LineWA getLine(int index)
This function returns the line at a given position in the line list.
Parameters:
index - The line represented by its index in the list of lines.
Returns:
The line represented by a LineWA object. Modifications to this LineWA object are also reflected in the line stored in this object!

createChild

public ConvexHullTreeNode createChild(int lineindex)
This function creates an empty convex hull tree node and associates it with a given line in this object.
Parameters:
lineindex - The line represented by its index in the list of lines.
Returns:
The newly created convex hull tree node.

insertChild

public void insertChild(int lineindex,
                        ConvexHullTreeNode child)
This function links a particular line in this object to a given convex hull tree node, thereby making it a child of this node.
Parameters:
lineindex - The line represented by its index in the list of lines.
child - The convex hull tree node which should be linked to the line.

insertOverlap

public void insertOverlap(double amount,
                          ConvexHullTreeNode node)
This function inserts an overlap graph edge between this node and another node.
Parameters:
amount - How much the two nodes overlap, given as the percentage of this object that is overlapped by the other object.
node - The convex hull tree node that overlaps this node.

removeOverlap

public void removeOverlap(ConvexHullTreeNode node)
This function removes an overlap graph edge between this node and another node.
Parameters:
node - The other node.

removeAllOverlaps

public void removeAllOverlaps()
Removes all overlap edges going out from this node.

numberOfLines

public int numberOfLines()
Finds the number of lines that makes op the polygon stored in this node.
Returns:
The number of lines.

getChildren

public ConvexHullTreeNode[] getChildren()
Returns all children of this node.
Returns:
The children of this node given as a ConvexHullTreeNode array.

getOverlapEdges

public OverlapGraphEdge[] getOverlapEdges()
Returns all overlap graph edges going from this node.
Returns:
The overlap graph edges given as an OverlapGraphEdge array.

getOverlappingNodes

public ConvexHullTreeNode[] getOverlappingNodes()
Returns all convex hull tree nodes that overlaps with this node.
Returns:
The overlapping nodes given as a ConvexHullTreeNode array.

sortOverlapEdges

public void sortOverlapEdges()
This function sorts the overlap graph edges of this node by the amount of overlap.

getLineForChild

public LineWA[] getLineForChild(ConvexHullTreeNode child)
This function finds the line a given child of this node is associated with.
Parameters:
child - The child node.
Returns:
A list of two LineWA objects, the one associated with the child node and the next one. If the convex hull tree node given as parameter to this function is not a child of this node, this function returns NULL.

getSmallestPoint

public int getSmallestPoint()
Gets the smallest point.
Returns:
The smallest point, which is the point with the smallest y-coordinate.

drawThis

public int[] drawThis(java.awt.Graphics g,
                      int xdisp,
                      int ydisp)
This function draws this convex hull three node in a "flattened" way. It was used for debugging purposes, and is not necessary for the algorithm itself to work.
Parameters:
g - The graphic into which the function should draw.
xdisp - Displacement in the x direction
ydisp - Displacement in the y direction.
Returns:
The centre of the drawn object given as an [x,y] coordinate pair.

drawTree

public void drawTree(java.awt.Graphics g,
                     int xdisp,
                     int ydisp)
Draws the convex hull tree with this node as its root. This function was made for debugging purposes and is not needed for the algorithm itself.
Parameters:
g - The graphic into which the function should draw.
xdisp - Displacement in the x direction
ydisp - Displacement in the y direction.

getOutLine

public LineWA[] getOutLine()
Gets the polygon stored in the node in the order in which it is stored internally.
Returns:
The polygon stored in this node represented as a LineWA array.

getOrderedOutLine

public LineWA[] getOrderedOutLine()
Gets the polygon stored in the node with the point with the smallest y-coordinate first.
Returns:
The polygon stored in this node represented as a LineWA array.

getLines

public LineWA[] getLines()
Gets the polygon stored in the convex hull tree that has this node as its root.
Returns:
The polygon stored in this node represented as a LineWA array.

setMatched

public void setMatched(boolean val)
Sets the variable indicating whether this object has been matched to another or not.
Parameters:
val - TRUE if this object has been matched, FALSE otherwise.

isMatched

public boolean isMatched()
Finds whether this object has already been matched to another convex hull tree node or not.
Returns:
TRUE if it has been matched, FALSE otherwise.

joinChildren

public LineWA[] joinChildren(ConvexHullTreeNode[] tojoin)
This function takes the given nodes, which must be children of this node, and creates a single convex hull tree node out of them. This includes rearranging the subtree which was under these nodes. This function is called when the matching algorithm discovers that one concavity in one object should be matched to more than one in the other object.
Parameters:
tojoin - The convex hull tree nodes which should be joinen.
Returns:
The coordinates of the points which have been deleted from this node represented as LineWA objects. This function will return null if there is an error.