Motivation for Tripod (Data Structure for Embedded Triangulations)

Edge-based Data Structure

Each edge stores

• pointers to its vertices: 2
• pointers to the next edges cw and ccw around both vertices: 4
• pointers to faces on either side of edge: 2

Therefore, edge-based structures store 8 pointers per edge.

Face-based Data Structure

Each face (or triangle) stores

• pointers to adjacent triangles: 3
• pointers to it vertices: 3

Therefore, face-based structures store 6 pointers per face.

Euler's Relation

We know from Euler's Relation that

• e = 3v - 6 and
• v - e + f = 2

e = 3v - 6

Therefore, edge-based structures store 3 x 8 or 24 pointers per vertex.

Additionally, if we count the number of faces in a triangulation and multiply by 3, then every edge will be counted twice. (Every face is bounded by exactly 3 edges, and each edge has a different face on either side of it.) Therefore,

• 3f = 2e

Substitute 2e = 3f into v - e + f = 2
2v - f = 4

f = 2v - 4

Therefore, face-based structures store 2 x 6 or 12 pointers per vertex.

Advantages of Tripod

• Tripod stores only 6 pointers per vertex.
• Tripod is vertex based, and vertices are the least ephemeral (compared to edges and faces) and keep location.

Features of Tripod

• There is a bounding triangle (outer face).
• Outer face is a cycle to the left.

• Every face is a triangle.

Intricate Features of Tripod

• Every vertex (not on the outer face) has exactly 3 outgoing edges labeled 0, 1 and 2 (blue, green, red on the Demo) ccw. Edge labels are called Schnyder labels.
• Incoming edges between i and i + 1 are labeled (i + 2)mod 3. This causes three spanning trees: each including one vertex of the outer face and all vertices inside. (See the Demo: each color (red, blue and green) represents a different spanning tree.)

• For an outgoing edge e, e.inc points to the next outgoing edge ccw of e (label is incremented, modulo 3) and e.dec points to the next outgoing edge cw of e (label is decremented, modulo 3).
• Each outgoing edge has two pointers : cw, ccw

CW and CCW Pointers

To find out the edge pointed by cw/ccw pointers

• Go cw/ccw around the vertex from the edge
• If the first edge is incoming to the vertex, you've got your edge! STOP!
• If the first edge is outgoing from the vertex, find its second vertex. Your edge is the outgoing edge from this vertex with the same label as the original edge.

A2.cw --> C0
B0.cw --> C0
B2.ccw --> A2
C0.ccw --> B2
C0.cw --> D1
D1.cw --> A2

Incoming and Outgoing Edges on a Vertex

Let e be an outgoing edge from a vertex v, and let f be the next edge ccw from e.

When f is incoming to vertex v, e.ccw --> f. Here, f always contributes an edge to a triangle with e.

When f is outgoing from vertex v, either e.ccw or f.cw will contribute an edge to a triangle with edge e.

Here, e.ccw contributes an edge.

Here, f.cw contributes an edge.

Types of Triangles and Tests for them

There are four different types of triangles to the left of an edge e. We can distinguish between these four types with the following tests:

Cycle

Here, edges form a ccw cycle.

Test: e.ccw³ == e

Mouth

Here, non-e edges are outgoing from the same vertex.

Test: e.ccw.inc.cw == e
Above, edges e and f have the same Schnyder label since they are both incoming to the same vertex with no outgoing edges from that vertex between them.

Wedgepar

Here, two edges are outgoing from the same vertex, and the third is directed toward e.

Test: e.ccw.cw.dec == e
Above, edges e and f have the same Schnyder label.

Wedgerev

Here, two edges are outgoing from the same vertex, and the third is directed away from e.

Test: e.inc.cw.ccw == e
Above, edges f and g have the same Schnyder label.

It is important to argue that the tests above return true on their triangle type, and return false on any other triangle type. See TriangleTests for details.

Note that tests for triangles right of e can be obtained by swapping .ccw with .cw and .inc with .dec

Operations

Identifying Edges

A directed edge can be identified by specifying its vertex, Schnyder label and direction (incoming or outgoing).

Accessing Edges

Once you know what type of triangle you have, you can access the next edge around a triangle given a first edge. See the tests for types of triangles.

Swapping Edges

When swapping edges (one incoming to a vertex; the other outgoing), Schnyder labels are preserved. Pointers will have to be reassigned, however.

Above, edges e and f are swapped. Pointers A1.ccw, A2.cw, B1.ccw, B2.cw, D0.ccw, D1.cw and D2.ccw all have to be reassigned.

Swapping becomes tricky when triangles right and left of a "diagonal edge" are of wedge type.

Above, triangles left and right of edge e are of wedge type, so edges e, f and g are all outgoing from vertex v.

There is always a directed cycle of edges through v that does not include edge e. See DirectedCycle for more on finding this directed cycle of edges. By reversing this cycle and relabeling edges, we can make either f or g incoming to vertex v.

Now, we can perform a swap between e and f. Schnyder labels are not preserved in this case.

-- SisillaSookdeo - 25 Jul 2005
to top