|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.ObjectcellularSurface.CellularSurface
A class to represent (combinatorially) a broad class of cell decompositions of orientable and non-orientable surfaces.
Created: Wed Jan 23 11:49:51 2002
Status: Incomplete, only halfheartedly debugged. TODO: write TestCellularSurface
| Field Summary | |
static int |
NO_ELEMENT
Index used to signify "no such edge/face/vertex exists". |
static int |
NON_ORIENTED_INC
Use this increment in a loop, if you want to iterate over positively (or negatively) oriented faces, vertices, or directed edges. |
static int |
NON_ORIENTED_NON_DIRECTED_INC
Use this increment in a loop, if you want to iterate over positively oriented and positively directed edges. |
| Constructor Summary | |
CellularSurface()
Creates a CellularSurface object with no edges, faces, or
vertices. |
|
| Method Summary | |
int[] |
boundary(int face)
Returns the boundary edges of a given face in the right order. |
int |
boundaryLength(int face)
Returns the number of edges in the boundary of a given face. |
void |
buildFromFaceBoundaries(int[][] faceBoundaries)
Build the surface with given face boundaries. |
void |
buildPoincareDual(CellularSurface surface)
Let this be the Poincare dual of a give surface. |
void |
contractEdge(int edge)
Contract an edge. |
void |
copy(CellularSurface surface)
|
int |
edgeWithLeftFace(int face)
Returns an edge with a given left face. |
int |
edgeWithTerminalVertex(int vertex)
Returns an edge with a given terminal vertex. |
boolean |
equals(CellularSurface surface)
|
int |
firstEdgeWithLeftFace(int face)
Returns the first edge with given a left face. |
static int |
fullIndexFromNonOriented(int i)
TODO: Description, example of use. |
static int |
fullIndexFromNonOrientedNonDirected(int i)
TODO: Description, example of use. |
int[] |
getInitialVertex()
For debugging purposes: Hand out a copy of initialVertex(int). |
int[] |
getLeftFace()
For debugging purposes: Hand out a copy of leftFace(int). |
int[] |
getNextEdge()
For debugging purposes: Hand out a copy of #nextEdge. |
int |
getNumEdges()
Gets the number of non-oriented, non-directed edges. |
int |
getNumFaces()
Gets the number of non-oriented faces. |
int |
getNumVertices()
Gets the number of non-oriented vertices. |
int[] |
getPreviousEdge()
For debugging purposes: Hand out a copy of #previousEdge. |
static boolean |
hasPositiveDirection(int i)
Checks if an edge has positive direction. |
static boolean |
hasPositiveOrientation(int i)
Checks if an edge, face, or vertex has positive orientation. |
int |
initialVertex(int i)
Given the full index of an edge, returns the full index of the initial vertex; or NO_ELEMENT if no such vertex exists. |
boolean |
isBoundaryFace(int face)
Returns true if face is boundary face and
false otherwise. |
static boolean |
isNoElement(int i)
Compares with NO_ELEMENT. |
int |
lastEdgeWithLeftFace(int face)
Returns the last edge with a given left face. |
int |
leftEdgeOfInitialVertex(int i)
Given the full index of an edge, returns the full index of the next edge with the same initial vertex to the left (i.  e.  turning the edge in the counterclockwise direction); or NO_ELEMENT if
no such edge exists. |
int |
leftEdgeOfTerminalVertex(int i)
Given the full index of an edge, returns the full index of the next edge with the same terminal vertex to the left (i.  e.  turning the edge in the clockwise direction); or NO_ELEMENT
if no such edge exists. |
int |
leftFace(int i)
Given the full index of an edge, returns the full index of the face on its left side; or NO_ELEMENT if no such face exists. |
int |
leftmostEdgeWithTerminalVertex(int vertex)
Returns the leftmost edge with a given terminal vertex. |
void |
medialGraph()
Build the medial graph. |
int |
nextEdgeOfLeftFace(int i)
Given the full index of an edge, returns the full index of the next edge in the boundary of the face on the left; or NO_ELEMENT
if no such edge exists. |
int |
nextEdgeOfRightFace(int i)
Given the full index of an edge, returns the full index of the next edge in the boundary of the face on the right; or NO_ELEMENT
if no such edge exists. |
static int |
nonDirectedIndex(int i)
Given the full index of an edge, returns the index of the corresponding non-directed oriented edge. |
static int |
nonOrientedIndex(int i)
Given the full index of an edge, face, or vertex, returns the index of the corresponding non-oriented edge, face, or vertex. |
static int |
nonOrientedNonDirectedIndex(int i)
Given the full index of an edge, returns the index of the corresponding non-oriented, non-directed edge. |
int |
previousEdgeOfLeftFace(int i)
Given the full index of an edge, returns the full index of the previous edge in the boundary of the face on the left; or NO_ELEMENT if no such edge exists. |
int |
previousEdgeOfRightFace(int i)
Given the full index of an edge, returns the full index of the previous edge in the boundary of the face on the right; or NO_ELEMENT if no such edge exists. |
void |
printData()
Print, in a tabular form, the data describing this
surface. |
static int |
reverseDirection(int i)
Reverse the direction of an edge. |
static int |
reverseOrientation(int i)
Reverse the orientation of an edge, face, or vertex. |
static int |
reverseOrientationAndDirection(int i)
Reverse the orientation and direction of an edge. |
int |
rightEdgeOfInitialVertex(int i)
Given the full index of an edge, returns the full index of the next edge with the same initial vertex to the right (i.  e.  turning the edge in the clockwise direction); or NO_ELEMENT
if no such edge exists. |
int |
rightEdgeOfTerminalVertex(int i)
Given the full index of an edge, returns the full index of the next edge with the same terminal vertex to the right (i.  e.  turning the edge in the counterclockwise direction); or NO_ELEMENT if no such edge exists. |
int |
rightFace(int i)
Given the full index of an edge, returns the full index of the face on its right side; or NO_ELEMENT if no such face exists. |
void |
slideEdgeLeft(int edge)
Slide an edge to the left. |
void |
slideEdgeRight(int edge)
Slide an edge to the right. |
int |
splitEdgeAcross(int edge)
Split an edge transversally. |
int |
splitEdgeAlong(int edge)
Split an edge longitudinally. |
int |
terminalVertex(int i)
Given the full index of an edge, returns the full index of the terminal vertex; or NO_ELEMENT if no such vertex exists. |
void |
truncateVertex(int vertex)
Truncate a Vertex. |
void |
truncateVertices()
Truncate all vertices. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Field Detail |
public static final int NO_ELEMENT
-1.
public static final int NON_ORIENTED_INC
public static final int NON_ORIENTED_NON_DIRECTED_INC
| Constructor Detail |
public CellularSurface()
CellularSurface object with no edges, faces, or
vertices.
| Method Detail |
public int[] getNextEdge()
#nextEdge.
public int[] getPreviousEdge()
#previousEdge.
public int[] getLeftFace()
leftFace(int).
public int[] getInitialVertex()
initialVertex(int).
public boolean equals(CellularSurface surface)
public void copy(CellularSurface surface)
public void buildPoincareDual(CellularSurface surface)
this be the Poincare dual of a give surface.
surface - the surface to dualize.public static final boolean isNoElement(int i)
NO_ELEMENT. Does not check if argument is negative. Does not and cannot check if argument is out of bounds, because argument could be the index of an edge, face, or vertex.
i - the full index of an edge, face, or vertex, or NO_ELEMENT.
i == NO_ELEMENTpublic static final boolean hasPositiveOrientation(int i)
0 means positive orientation, a 1 means
negative orientation. Does not check if argument is negative. Does not and cannot check if argument is out of bounds, because argument could be the index of an edge, face, or vertex.
i - the full index of an edge, face, or vertex
(i & 1) == 0public static final boolean hasPositiveDirection(int i)
0
means positive direction, a 1 means negative
direction. Does not check if argument is negative or out of bounds.
i - the full index of an edge
(i & 2) == 0public static final int reverseOrientation(int i)
If argument is the return value is
also NO_ELEMENT. NO_ELEMENT
i - The full index of an edge, face or vertex, or NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : i ^ 1hasPositiveOrientation(int)public static final int reverseDirection(int i)
If argument is the return value is
also NO_ELEMENT. NO_ELEMENT
i - the full index of an edge, or NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : i ^ 2hasPositiveDirection(int)public static final int reverseOrientationAndDirection(int i)
If argument is the return value is
also NO_ELEMENT.NO_ELEMENT
i - the full index of an edge, or NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : i ^ 3hasPositiveDirection(int)public static final int nonOrientedIndex(int i)
If argument is the return value is
also NO_ELEMENT.NO_ELEMENT
i - the full index of an edge, face, or vertex, or NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : i >> 1public static final int nonDirectedIndex(int i)
If argument is the return value is
also NO_ELEMENT.NO_ELEMENT
i - the full index of an edge or NO_ELEMENT. Should be
>= 0 and < 4 * getNumEdges(), or equal to NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : ((i >> 1) &
0xFFFFFFFE) | (i & 1). If argument is in recommended
range, * return value is >= 0 and < 2 *
getNumEdges(), or equal to NO_ELEMENTpublic static final int nonOrientedNonDirectedIndex(int i)
If argument is NO_ELEMENT the return value is
also NO_ELEMENT.
i - the full index of an edge or NO_ELEMENT. Should be
>= 0 and < 4 * getNumEdges(), or equal to NO_ELEMENT
isNoElement(i) ? NO_ELEMENT : ((i >> 1) & (!1)) ||
(i & 1). If argument is in recommended range, return
value is >= 0 and < 2 * getNumEdges(), or equal to NO_ELEMENTpublic static final int fullIndexFromNonOriented(int i)
i - non-oriented index of a face, vertex, or directed edge
public static final int fullIndexFromNonOrientedNonDirected(int i)
i - non-oriented, non-directed index of an edge
public final int getNumEdges()
public final int getNumFaces()
public final int getNumVertices()
public final int nextEdgeOfLeftFace(int i)
NO_ELEMENT
if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTnextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int),
leftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int)public final int nextEdgeOfRightFace(int i)
NO_ELEMENT
if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTnextEdgeOfLeftFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int),
leftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int)public final int previousEdgeOfLeftFace(int i)
NO_ELEMENT if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTnextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfRightFace(int),
leftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int)public final int previousEdgeOfRightFace(int i)
NO_ELEMENT if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTnextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
leftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int)public final int leftEdgeOfInitialVertex(int i)
NO_ELEMENT if
no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTrightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int),
nextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int)public final int rightEdgeOfInitialVertex(int i)
NO_ELEMENT
if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTleftEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
rightEdgeOfTerminalVertex(int),
nextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int)public final int leftEdgeOfTerminalVertex(int i)
NO_ELEMENT
if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTleftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
rightEdgeOfTerminalVertex(int),
nextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int)public final int rightEdgeOfTerminalVertex(int i)
NO_ELEMENT if no such edge exists.
Returns NO_ELEMENT, if
i - the full index of an edge
NO_ELEMENTleftEdgeOfInitialVertex(int),
rightEdgeOfInitialVertex(int),
leftEdgeOfTerminalVertex(int),
nextEdgeOfLeftFace(int),
nextEdgeOfRightFace(int),
previousEdgeOfLeftFace(int),
previousEdgeOfRightFace(int)public final int leftFace(int i)
NO_ELEMENT if no such face exists.
i - full index of an edge
rightFace(int),
initialVertex(int),
terminalVertex(int)public final int rightFace(int i)
NO_ELEMENT if no such face exists.
i - full index of an edge
initialVertex(int),
terminalVertex(int)public final int initialVertex(int i)
NO_ELEMENT if no such vertex exists.
i - full index of an edge
terminalVertex(int),
rightFace(int)public final int terminalVertex(int i)
NO_ELEMENT if no such vertex exists.
i - full index of an edge
initialVertex(int),
leftFace(int),
rightFace(int)public final int edgeWithTerminalVertex(int vertex)
Returns an edge with a given terminal vertex.
vertex - the full index of a vertex
terminalVertex(edge)
== vertex .leftmostEdgeWithTerminalVertex(int vertex)public final int leftmostEdgeWithTerminalVertex(int vertex)
Returns the leftmost edge with a given terminal vertex.
vertex - the full index of a vertex
terminalVertex(edge)
== vertex and
leftEdgeOfTerminalVertex(int) ==
NO_ELEMENT, if vertex is a boundary
vertex. terminalVertex(edge)
== vertex , if vertex is an
interior vertex. edgeWithTerminalVertex(int vertex)public final int edgeWithLeftFace(int face)
Returns an edge with a given left face.
face - the full index of a face
leftFace(edge)
== face .firstEdgeWithLeftFace(int face),
lastEdgeWithLeftFace(int face)public final int firstEdgeWithLeftFace(int face)
Returns the first edge with given a left face.
face - the full index of a face
leftFace(edge)
== face and
previousEdgeOfLeftFace(int) ==
NO_ELEMENT, if face is a boundary
face. leftFace(edge)
== face , if face is an
interior face. edgeWithLeftFace(int face),
lastEdgeWithLeftFace(int face)public final int lastEdgeWithLeftFace(int face)
Returns the last edge with a given left face.
face - the full index of a face
leftFace(edge)
== face and
nextEdgeOfLeftFace(int) ==
NO_ELEMENT, if face is a boundary
face. leftFace(edge)
== face , if face is an
interior face. edgeWithLeftFace(int face),
firstEdgeWithLeftFace(int face)public final boolean isBoundaryFace(int face)
true if face is boundary face and
false otherwise.
Also returns false, if face == NO_ELEMENT.
face - the full intex of a face
true if face is boundary face and
false otherwisepublic final void buildFromFaceBoundaries(int[][] faceBoundaries)
The value may appear once in a
boundary. The corresponding face is then a boundary face with
non-closed boundary. NO_ELEMENT = -1
No checks are performed to test wether the resulting edge-links are
consistent. Hence, there is no guarantee that the resulting surface is
in a consistent state. What is even worse: Method #buildVertices() may run into an infinite loop. TODO: Remove this
problem by checking consistency of edge-links.
faceBoundaries - the face
boundaries. faceBoundaries[i][j] is
edge j in the boundary of the
face with non-oriented index i.public final int boundaryLength(int face)
Returns the number of edges in the boundary of a given face. If an edge appears twice in the boundary (with different orientation or direction), it is counted twice.
TODO: Implement the method coBoundaryLength(int
vertex).
face - the full index of a face. Should be in the range from
0 to 2 * getNumFaces().
public final int[] boundary(int face)
Returns the boundary edges of a given face in the right order.
The int array which is returned is newly created each
time the method is called.
face - an int: the full index of a face
int[] of length boundaryLength(face), holding the full indices of the edges in the
boundarypublic final int splitEdgeAcross(int edge)
Split an edge transversally. This increases by one the number of edges and the number of vertices.
Introduces a new edge in series with (and following)
edge and a new vertex between them. The new vertex is
the terminal vertex of edge and the initial vertex of the
new edge.
edge - the full index of the edge to be split.
4
getNumEdges() would have returned before the method was
invoked.splitEdgeAlong(int edge)public final int splitEdgeAlong(int edge)
Split an edge longitudinally. This increases by one the number of edges and the number of faces.
Introduces a new parallel edge to the right of edge
and a new face between them. The new face is the right face of
edge and the left face of the new edge.
edge - the full index of the edge to be split.
4 *
getNumEdges() .splitEdgeAcross(int edge)public final void slideEdgeLeft(int edge)
Slide an edge to the left. Performs the following transformation:
\ / \ /
\ / \ /
*-----* ===> *-----*
/ / \ / \ \
/ / \ / \ \
* *
The numbers of vertices, edges, and faces do not change.
TODO: Improve this doc-comment.
edge - the full index of an edge. The following restrictions
apply:
nextEdgeOfLeftFace(edge)
must not return NO_ELEMENT, edge,
reverseOrientation(edge),
reverseDirection(edge), or
reverseOrientationAndDirection(edge).
rightFace(edge)
must not return NO_ELEMENT.
slideEdgeRight(int edge)public final void slideEdgeRight(int edge)
Slide an edge to the right. Performs the following transformation:
\ / \ /
\ / \ /
*-----* ===> *-----*
/ \ \ / / \
/ \ \ / / \
* *
The numbers of vertices, edges, and faces do not change.
TODO: Improve this doc-comment.
edge - the full index of an edge. The following restrictions
apply:
nextEdgeOfRightFace(edge)
must not return NO_ELEMENT, edge,
reverseOrientation(edge),
reverseDirection(edge), or
reverseOrientationAndDirection(edge).
leftFace(edge)
must not return NO_ELEMENT.
slideEdgeLeft(int edge)public void contractEdge(int edge)
edge - a non-negative int less than 4 *
getNumEdges() : the edge to contractpublic void truncateVertex(int vertex)
Truncate a Vertex. This introduces one new face, d new
edges, and d - 1 new vertices, where d
is the degree of the vertex.
So far, vertex must not be a boundary vertex or have
degree one. Otherwise, an IllegalArgumentException
is thrown.
TODO: Come up with a good specification for what should be done in all possible cases and implement it.
vertex - a non-negative int less than 2 *
getNumVertices() : the vertex to truncate
java.lang.IllegalArgumentException - if vertex is a boundary
vertex or has degree 1.public void truncateVertices()
truncateVertex(int
vertex) for all original vertices.
public void medialGraph()
public final void printData()
this
surface.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||