Jcg.schnyderwoods

Class PlanarTriSchnyderWood

java.lang.Object

Jcg.schnyderwoods.EdgeOrientation

Jcg.schnyderwoods.PlanarTriSchnyderWood

public class PlanarTriSchnyderWood
extends EdgeOrientation

Author:

Luca Castelli Aleardi This class allows to compute a (minimal) Schnyder wood of a planar triangulation. It implements a "cut border": a simple cycle of edges defining a topological disk, and provides basic operations such as vertex removal (the vertex to be removed must belong to the cut border) It works for planar triangle meshes without boundaries. Faces are assumed to be ccw oriented (only for combinatorics)

Field Summary

Fields

Modifier and Type	Field and Description
Halfedge<Point_>	rootEdge half-edge (v_0, v_1) oriented toward v_1, assuming the ccw orientation of faces
Vertex<Point_>	v0
Vertex<Point_>	v1
Vertex<Point_>	v2

Fields inherited from class Jcg.schnyderwoods.EdgeOrientation

edgeColor, isWellOriented, polyhedron

Constructor Summary

Constructors

Constructor and Description
PlanarTriSchnyderWood(Polyhedron_3<Point_> polyhedron, Halfedge<Point_> rootEdge) Construct the cut-border starting from the root edge (v0, v1) At the beginning the cut-border contains edges (v2, v0) and (v1, v2) Edges are ccw oriented around faces

Method Summary

Modifier and Type	Method and Description
void	addToCutBorder(Halfedge<Point_> e, DListNode<Halfedge<Point_>> node) Add a half-edge to the cut-border, at a given position (in the cut-border) Update all concerned information (colors, existent chords, boundary vertices, ...)
java.lang.String[]	encodeSchnyderWood() Return the parenthesis encoding of the Schnyder wood, consisting of two words balanced parenthesis words.
Halfedge<Point_>	getFirstIncomingRedEdge(Vertex<Point_> v) Return the first (half)edge oriented toward vertex v and having color 0 (red) Edges (v0, v1) and (v2, v0) are assumed to be red colored Return null, if such an edge does not exist
Halfedge<Point_>	getNextIncomingRedEdge(Halfedge<Point_> e) Return the next edge of color 0, after edge e (turning in ccw direction), oriented toward its target vertex (denoted by v).
int[]	getOriginalVertexOrdering() Return an array of indices representing the original vertex ordering
java.lang.String[]	originalVertexOrderingToString()
void	performTraversal() Perform all steps of the vertex conquest, computing the Schnyder wood
java.lang.String	SchnyderWoodToString() Return a string representing the Schnyder wood
void	setToCutBorder(Halfedge<Point_> e) Add a half-edge to the cut-border, at a given position (in the cut-border) Update all concerned information (colors, existent chords, boundary vertices, ...)
java.lang.String	toString()
DListNode<Halfedge<Point_>>	vertexRemoval(DListNode<Halfedge<Point_>> node) It removes a vertex from the cut-border (vertex conquest) It updates the cut-border, assigning color and orientation to edges

Methods inherited from class Jcg.schnyderwoods.EdgeOrientation

getEdgeColoration, getEdgeColors, getEdgeOrientation, orientationToString

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

rootEdge

public Halfedge<Point_> rootEdge

half-edge (v_0, v_1) oriented toward v_1, assuming the ccw orientation of faces

v0

public Vertex<Point_> v0

v1

public Vertex<Point_> v1

v2

public Vertex<Point_> v2

Constructor Detail

PlanarTriSchnyderWood

public PlanarTriSchnyderWood(Polyhedron_3<Point_> polyhedron,
                             Halfedge<Point_> rootEdge)

Construct the cut-border starting from the root edge (v0, v1) At the beginning the cut-border contains edges (v2, v0) and (v1, v2) Edges are ccw oriented around faces

Method Detail

vertexRemoval

public DListNode<Halfedge<Point_>> vertexRemoval(DListNode<Halfedge<Point_>> node)

It removes a vertex from the cut-border (vertex conquest) It updates the cut-border, assigning color and orientation to edges

Parameters:

node - The node in the list storing the given half-edge (whose vertex will be removed)

Returns:

result return the list node containing the preceding halfedge (on the boundary cycle)

addToCutBorder

public void addToCutBorder(Halfedge<Point_> e,
                           DListNode<Halfedge<Point_>> node)

Add a half-edge to the cut-border, at a given position (in the cut-border) Update all concerned information (colors, existent chords, boundary vertices, ...)

setToCutBorder

public void setToCutBorder(Halfedge<Point_> e)

Add a half-edge to the cut-border, at a given position (in the cut-border) Update all concerned information (colors, existent chords, boundary vertices, ...)

performTraversal

public void performTraversal()

Perform all steps of the vertex conquest, computing the Schnyder wood

getOriginalVertexOrdering

public int[] getOriginalVertexOrdering()

Return an array of indices representing the original vertex ordering

getFirstIncomingRedEdge

public Halfedge<Point_> getFirstIncomingRedEdge(Vertex<Point_> v)

Return the first (half)edge oriented toward vertex v and having color 0 (red) Edges (v0, v1) and (v2, v0) are assumed to be red colored Return null, if such an edge does not exist

getNextIncomingRedEdge

public Halfedge<Point_> getNextIncomingRedEdge(Halfedge<Point_> e)

Return the next edge of color 0, after edge e (turning in ccw direction), oriented toward its target vertex (denoted by v). Half-edge e is assumed to have v as target vertex Edges (v0, v1) and (v2, v0) are assumed to be red colored (and oriented toward v0) Return null, if such an edge does not exist

encodeSchnyderWood

public java.lang.String[] encodeSchnyderWood()

Return the parenthesis encoding of the Schnyder wood, consisting of two words balanced parenthesis words. It performs the traversal of the contour of the tree, in ccw order. The traversal starts from the half-edge (u, v0) and ends at (v0, v2). (u, v0) is the half-edge oriented toward v0 corresponding to the first incoming edge incident to v0 (thus of color 0)

originalVertexOrderingToString

public java.lang.String[] originalVertexOrderingToString()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

SchnyderWoodToString

public java.lang.String SchnyderWoodToString()

Return a string representing the Schnyder wood