This is the page about the tripod data structure, implemented in Java.

The following cryptic definition is really important:

• CCW[e] points at an edge whose org is destination of the next edge ccw

around org(e) and that may be the third edge of the triangle...

Basic data structure

Initializer for Tripod class

Tripod makes a list of points, and cw and ccw pointers, three of each for each point. It makes a bounding triangle, and sets the initial points and pointers for this triangle.

public Tripod(int n, int width, int height) {

        P = new Point[n];
        CW = new int[3*n];
        CCW = new int[3*n];

        bt = new BTriangle(width, height);
        P[0] = bt.p1;
        P[1] = bt.p2;
        P[2] = bt.p3;
        set(0, 1,6,0, 2,0,6);
        set(3, 4,5,1, 1,3,4);
        set(6, 5,8,6, 8,5,7);
        freept = 3;
    }

We classify triangles into four types

(I should add pictures...)

    //  four types of triangles.
    //   cycle:     arrows form cycle
    //   mouth:     one arrow into org(e); two into dest(e).
    //   wedge_par: arrows out from org(e); opposite edge points to dest(e)
    //   wedge_rev: arrows out from org(e); opposite edge points away from dest(e)
    //              (wedge:    arrows out from org(e) )

Tests for which type we have. Two functions, classify_ccw and classify_cw will classify the triangle ccw or cw of an edge e using these more basic tests.

public boolean cycle_ccw(int e) { return CCW[CCW[CCW[e]]] == e; }
public boolean wedge_ccw_par(int e) { return CW[CCW[e]] == Inc(e); }
public boolean wedge_ccw_rev(int e) { return CCW[CW[Inc(e)]] == e; }
public boolean mouth_ccw(int e) { return CW[Inc(CCW[e])] == e; }
public boolean wedge_ccw(int e) {return wedge_ccw_par(e)||wedge_ccw_rev(e);}
public boolean parallel_ccw(int e) { return (mouth_ccw(e) || wedge_ccw_par(e));}

public boolean cycle_cw(int e) { return CW[CW[CW[e]]] == e; }
public boolean wedge_cw_par(int e) { return CCW[CW[e]] == Dec(e); }
public boolean wedge_cw_rev(int e) { return CW[CCW[Dec(e)]] == e; }
public boolean mouth_cw(int e) { return CCW[Dec(CW[e])] == e; }
public boolean wedge_cw(int e) {return wedge_cw_par(e) || wedge_cw_rev(e);}
public boolean parallel_cw(int e) { return (mouth_cw(e) || wedge_cw_par(e));}

public boolean isWedge(int type) { return (type & 1) != 0; }
public boolean isParallel(int type) { return (type & 2) != 0; }

Accessing edges by number (index in CW and CCW tables.)

Given the number of an edge e for a point, we can obtain the number of the edges ccw with Inc(e) and cw with Dec(e)

// edges are stored counter-clock-wise

static final private int inctable[] = {+1, +1, -2};
static final private int dectable[] = {+2, -1, -1};

public int Inc(int e) { return e+inctable[e%3]; }
public int Dec(int e) { return e+dectable[e%3]; }

Some access functions depend on what type of triangle we have:

   // Next edge ccw/cw around org(e)
 public int next_ccw(int e) { return (wedge_ccw(e) ? Inc(e) : CCW[e]); }
 public int next_cw(int e) { return (wedge_cw(e) ? Dec(e) : CW[e]); }

In words, next_ccw will decide if the triangle ccw of e uses two edges from e or just one. If it uses two, then they are e and Inc(e), otherwise they are e and CCW[e].

    // Opposite edge from org(e)
    public int op_ccw(int e) {
        if (wedge_ccw_par(e)) return(CCW[e]);
        if (wedge_ccw_rev(e)) return(CW[Inc(e)]);
        if (cycle_ccw(e)) return(CCW[CCW[e]]);
        return(Inc(CCW[e]));   /* mouth */
    }

    public int op_cw(int e) {
        if (wedge_cw_par(e)) return(CW[e]);
        if (wedge_cw_rev(e)) return(CCW[Dec(e)]);
        if (cycle_cw(e)) return(CW[CW[e]]);
        return(Dec(CW[e]));   /* mouth */
    }

    public int follow(int e) { // move to edge out of dest of same color
        int f;
        if (wedge_ccw(e)) f = Dec(CW[Inc(e)]);
        else { f = CCW[e];
            if (wedge_ccw(f)) f = Inc(CCW[f]);
            else f = Dec(CCW[f]);
        }
        return f;
    }

ModifyingEdgeDirections

(complicated stuff; let's ignore details for now.)

Updating the triangulation

Locate the old triangle containing a new point

// locate a point in the triangulation, return an edge of the enclosing triangle

    private int locate(Point q, int hint) { //throws duplicatePointExeption
        int e, left, right, i = 3*freept;
        Point a, b, c;

        //    System.out.println("loc from " + hint);
        audit();

        e = hint;

        do{
            if(Point.left(Org(e), Dest(e), q)) {
                a = Org(e);
                b = Dest(e);
                if(wedge_ccw(e)) c = Dest(Inc(e));
                else c = Org(CCW[e]);
                left = next_ccw(e);
                right = op_ccw(e);
            }
            else {
                a = Dest(e);
                b = Org(e);
                if(wedge_cw(e)) c = Dest(Dec(e));
                else c = Org(CW[e]);
                left = op_cw(e);
                right = next_cw(e);
            }

            // if(q.equals(a) || q.equals(b) || q.equals(c))
            // throw new duplicatePointException(e);

            if(Point.right(a, c, q)) {
                if(Point.right(c, b, q)) return(e);
                else e = right;
            }
            else e = left;

        } while(i-- > 0);
        return (-1); // we should never get here
    }

Split a triangle containing the new point into three triangles

Swap edges to form the Delaunay triangulation

-- JackSnoeyink - 14 Jul 2005
to top