Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.TripodImplementation
r1.1 - 14 Jul 2005 - 17:09 - Main.guest
topic end
Start of topic |
Skip to actions
%TOC% 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. <pre> 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; } </pre> ---+++ We classify triangles into four types (I should add pictures...) <pre> // 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) ) </pre> 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. <pre> 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; } </pre> ---+++ 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) <pre> // 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]; } </pre> Some access functions depend on what type of triangle we have: <pre> // 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]); } </pre> 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]. <pre> // 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; } </pre> ---+++ 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 <pre> 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 } </pre> ---+++ Split a triangle containing the new point into three triangles ---+++ Swap edges to form the Delaunay triangulation -- Main.JackSnoeyink - 14 Jul 2005
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
TripodImplementation
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback