Test e.ccw3 == e
We have shown that test e.ccw
3 == e returns true for triangle type cycle left of an edge e. It is important, however, to show that this test returns false for the other three triangle types.
Mouth 1
Let edge
e have Schnyder label
i. As shown in the picture below, there are two cases for e.ccw
3 depending upon whether or not there is an incoming edge
f to vertex
v -:
- (a) e.ccw3 has label i + 1
- (b) e.ccw3 has label i + 2
Therefore, e.ccw
3 can never be
e which has label
i. The test always returns false for mouth triangle type.
Wedgepar 1
Let edge
e have Schnyder label
i. As shown in the picture below, there are four cases for e.ccw
3 depending upon whether or not there are incoming edges between certain outgoing edges including -:
- (a) e.ccw3 has label i + 1
- (b) e.ccw3 has label i + 2
- (c) e.ccw3 has label i + 2
There is a fourth case where e.ccw
3 could have label
i. In the picture below, edges
j and
k are outgoing from the same vertex
x. If there are no incoming edges between edges
k and
j and
k is e.ccw
2, e.ccw
3 will have label
i. This edge e.ccw
3 can be edge
e iff there exists a triangle T so that edge
j is incoming to vertex
w. This triangle cannot exist for the following reasons-:
- Vertex v must have an outgoing edge between edges g and h
- Incoming edges between edges f and g should have label i
Therefore, e.ccw
3 can never be
e. The test always returns false for wedgepar triangle type.
Wedgerev 1
Let edge
e have Schnyder label
i. As shown in the picture below, there are four cases for e.ccw
3 depending upon whether or not there are incoming edges between certain outgoing edges including -:
- (a) e.ccw3 has label i + 1
- (b) e.ccw3 has label i + 2
- (c) e.ccw3 has label i + 2
There is a fourth case where e.ccw
3 could have label
i. In the picture below, edges
j and
k are outgoing from the same vertex
x. If there are no incoming edges between edges
k and
j and
k is e.ccw
2, e.ccw
3 will have label
i. This edge e.ccw
3 can be edge
e iff there exists a triangle T so that edge
j is incoming to vertex
w. This triangle cannot exist for the following reasons-:
- Vertex v must have an outgoing edge between edges g and h
- Incoming edges between edges f and g should have label i
Therefore, e.ccw
3 can never be
e. The test always returns false for wedgepar triangle type.
Test e.ccw.inc.cw == e
We have shown that test e.ccw.inc.cw == e returns true for triangle type mouth left of an edge e. We show below that this test returns false for the other three triangle types.
Cycle 1
Let edge
e have Schnyder label
i. e.ccw.inc.cw has label
i + 1 and is an edge on the triangle as shown in the picture below. Therefore, edge e.ccw.inc.cw cannot be e. The test always returns false for cycle triangle type.
Wedgepar 2
Let edge
e have Schnyder label
i. As shown in the picture below, there are two cases for e.ccw.inc.cw depending upon whether or not there is an incoming edge
f to vertex
v including -:
- (a) e.ccw.inc.cw has label i + 2
- (b) e.ccw.inc.cw has label i + 1
Therefore, e.ccw.inc.cw can never be
e. The test always returns false for wedgepar triangle type.
Wedgerev 2
Let edge
e have Schnyder label
i. As shown in the picture below, there are two cases for e.ccw.inc.cw depending upon whether or not there is an incoming edge
f to vertex
v -:
- (a) e.ccw.inc.cw has label i + 2
- (b) e.ccw.inc.cw has label i + 1
Therefore, e.ccw.inc.cw can never be
e. The test always returns false for wedgerev triangle type.
Test e.ccw.cw.dec == e
We have shown that test e.ccw.cw.dec == e returns true for triangle type wedgepar left of an edge e. We show below that this test returns false for the other three triangle types.
Cycle 2
Let edge
e have Schnyder label
i. As shown in the picture below, there are two cases for e.ccw.inc.cw depending upon whether or not there is an incoming edge
f to vertex v -:
- (a) e.ccw.inc.cw has label i + 2
- (b) e.ccw.inc.cw has label i + 1
Therefore, e.ccw.cw.dec can never be
e. The test always returns false for cycle triangle type.
Mouth 2
Let edge
e have Schnyder label
i. e.ccw.inc.cw has label
i + 1 as shown in the picture below. Therefore, e.ccw.inc.cw can never be
e. The test always returns false for mouth triangle type.
Wedgerev 3
Let edge
e have Schnyder label
i and be outgoing from vertex
v and incoming to vertex
w. e.ccw.cw.dec also has label
i. e.ccw.cw.dec is outgoing from w while
e is outgoing from v. Therefore, e.ccw.cw.dec can never be
e. The test always returns false for wedgerev triangle type.
Test e.inc.cw.ccw == e
We have shown that test e.ccw.cw.dec == e returns true for triangle type wedgerev left of an edge e. We show below that this test returns false for the other three triangle types.
Cycle 3
Let edge
e have Schnyder label
i. As shown in the picture below, e.inc.cw.ccw has label
i + 1 and is an edge on the triangle. Therefore, e.inc.cw.ccw can never be
e. The test always returns false for cycle triangle type.
Mouth 3
Let edge
e have Schnyder label
i. As shown in the picture below, e.inc.cw.ccw has label
i + 2. Therefore, e.inc.cw.ccw can never be
e. The test always returns false for mouth triangle type.
Wedgepar 3
Let edge
e have Schnyder label
i. e.inc.cw.ccw has label
i but is an edge
f on the triangle. Since the edges on the triangle must be unique,
f or e.inc.cw.ccw can never be
e. The test always returns false for cycle triangle type.
--
SisillaSookdeo - 01 Aug 2005