[Cyan]<PreISLCedar>Stolfi>COG>COGQuad.mesa!1

-- COGQuad.mesa: orientable 2-D subdivisions - data structure and primitives

-- last modified by Stolfi - April 8, 1983 5:33 pm

-- To do: add Use: PROC[e: Edge] RETURN [BOOL] parameter to Traverse and TopSort?

-- To do: Let the client worry about maintaining edge numbers?.

-- To do: review Traverse and TopSort

-- To do: add depthFirst: BOOL ← TRUE parameter to Traverse and TopSort?

-- To do: add faces option to Traverse?

-- To do: Check what happens to CloseFace for general edges ep, ef (not necessarily with same left face)

DIRECTORY;

COGQuad: CEDAR DEFINITIONS =
BEGIN

-- QUAD EDGE DATA STRUCTURE - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- This interface allows the creation and manipulation of orientable 2-D subdivisions (i.e. undirected graphs embedded in orientable 2-D manifolds).

-- A subdivision is a combinatorial beast consisting of a set of vertices, a set of faces, and a set of edges. See the paper "Primitives for the Manipulation of Planar Subdivisions and the Construction of Voronoi Diagrams" by Guibas and Stolfi (STOC 83) for definition and theory. The following are some properties of subdivisions:

1. every edge is incident to a pair of (eventually identical) vertices and to a pair of (eventually identical) faces;
2. every face is incident to at least one vertex, and every vertex to at least one face;
3. the edges incident to a given vertex v (or to a given face f) are cyclically ordered, in what will be called the "ccw order as seen from v (or from f)";
4. If the edges e1, e2 are incident to a common vertex v and are ccw consecutive as seen from v, then v, e1, and e2 are incident to a common face f, and e2, e1 (in that order) are ccw consecutive as seen from f; and the same is true if we exchange vertices with faces;

Note that if an edge is incident twice to the same vertex, it will appear twice in the ccw order around that vertex. A similar remark applies to faces.

If a vertex is incident to k edges, the faces incident to it can be arranged in a cyclical list (where each face appears one or more times) in such a way that the i-th edge is incident to the i-th and (i+1)th face in this list. The statement holds true also if we exchange vertices and faces.

-- A subdivision is said to be connected if it has at least one vertex (or, equivalently, at least one face) and every vertex (resp. face) can be reached from any other by a chain of adjacent edges. In general, a subdivision is the union of zero or more connected components.

-- Every edge in the subdivision has four distinct "directions of traversal": two from vertex to vertex and two from face to face. These four directions are all distinct, even if the edge is a loop (identical endpoints) or a bridge (same face on both sides). An edge plus a specific direction of traversal is called a directed edge (Edge).

-- To each directed edge e is associated an origin vertex, a destination vertex, a left face and a right face (Org[e], Dest[e], Left[e], Right[e]). These labels are assigned in such a way that e is crossed from origin to destination when going c.c.w. around its left face, and from the right face to the left face when going c.c.w. around its origin.

-- The functions Lnext[e] and Onext[e] give the directed edge that follows e in the c.c.w. ordering around Left[e] and Org[e], respectively; the functions Lprev[e] and Oprev[e] are their inverses. The function Sym[e] gives the same undirected edge as e, but taken in the opposite direction (so that Org[e] = Dest[Sym[e]], Left[e] = Right[Sym[e]], etc.).

-- The dual of a subdivision is obtained by exchanging vertices with faces, while preserving the c.c.w. orderings of both. To every directed edge e of the original subdivision there corresponds an edge e' = Rot[e] in the dual, such that Org[e'] = Right[e], Right[e'] = Dest[e], Dest[e'] = Left[e], Left[e'] = Org[e]. The representation of subdivisions is such that the dual is maintained in parallel with the original subdivision at no extra cost, so that Rot[] is a constant-time operation.

-- The Rot[] operation is not quite "dual", since Rot[Rot[e]] is Sym[e] rather than e. For this reason, the inverse operation Tor[e] = Rot^3[e] = Sym[Rot[e]] is also provided.

-- To refer to a connected subdivision, one gives an edge of it. Every component of a subdivision has at least one edge. An edge (or rather, a group of four directed edges related by Rot) is represented by an edge record. The vertices and faces are not represented explicitly in the structure; Dest[e] is represented implicitly by the ring of all edges obtained from e by one ofr more Onexts. However, every directed edge has a user-defined pointer field Odata[e] which may be used to store attributes of the edge e. Typically, this field points to a user-defined vertex record describing Org[e]. However, this module does not attempt to keep the Odata fields of all edges with same origin consistent with each other.

-- Every undirected edge (including dummy ones) is assigned a unique "serial number" No[e] when created, starting from zero. This number is used for debugging and traversing.

-- The edge representation is private to the implementation module, but vertices and faces are represented by client-defined data records.

Edge: TYPE = RECORD
[rec: REF EdgeRec,
ix: INTEGER[0..4)]; -- one edge (or rot edge) taken in a specific direction

EdgeData: TYPE = REF ANY; -- client-defined edge data

-- PRIMITIVES FOR TRAVERSING THE EDGE STRUCTURE - - - - - - - - - - - - - - - - - - - -

Onext: PROC [e: Edge] RETURNS [ne: Edge] = INLINE

-- Directed edge with same Org as e and following e ccw around Org[e].

{RETURN [ e.rec.next[e.ix] ]};

Rot: PROC [e: Edge] RETURNS [ne: Edge] = INLINE

-- Rot of the directed edge e, going from Right[e] to Left[e].

{RETURN [ [e.rec, (e.ix + 1) MOD 4] ]};

Sym: PROC [e: Edge] RETURNS [ne: Edge] = INLINE

-- Directed edge corresponding to e taken in opposite direction.

{RETURN [ [e.rec, (e.ix + 2) MOD 4] ]};

Tor: PROC [e: Edge] RETURNS [ne: Edge] = INLINE

-- Directed edge whose Rot is e.

{RETURN [ [e.rec, (e.ix + 3) MOD 4] ]};

Lnext: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge with same Left as e and following e c.c.w. around Left[e].

Rnext: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge with same Right as e and following e c.c.w. around Right[e].

Dnext: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge with same Dest as e and following e c.c.w. around Dest[e].

Oprev: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge whose Onext is e.

Lprev: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge whose Lnext is e.

Rprev: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge whose Rnext is e.

Dprev: PROC [e: Edge] RETURNS [ne: Edge];

-- Directed edge whose Dnext is e.

-- MISCELLANEOUS EDGE PRIMITIVES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

No: PROC [e: Edge] RETURNS [NAT] = INLINE

-- Serial creation number of the edge.

{RETURN [e.rec.no]};

-- PRIMITIVES FOR MAINTAINING USER DATA - - - - - - - - - - - - - - - - - - - - - - - - - -

Odata: PROC [e: Edge] RETURNS [d: EdgeData] = INLINE

-- Data field of e (presumably referring to the origin of e).

{RETURN [e.rec.data[e.ix]]};

Ddata: PROC [e: Edge] RETURNS [d: EdgeData] = INLINE

Data field for destination of e.

{RETURN [Odata[Sym[e]]]};

Ldata: PROC [e: Edge] RETURNS [d: EdgeData] = INLINE

Data field for left face of e.

{RETURN [Odata[Tor[e]]]};

Rdata: PROC [e: Edge] RETURNS [d: EdgeData] = INLINE

Data field for right face of e.

{RETURN [Odata[Rot[e]]]};

-- The procedures below can be used to replace the data fields of an edge e. The client should worry about maintaining the consistency of those links, so that, for example, all edges with common origin have indeed the same Odata[], and so forth. (The client should consider using SetAllOrg, SetAllLeft, etc., which guarantee this condition automatically)

-- Note that changing the Odata, Ddata, Ldata and/or Rdata fields does not afect in any way the structure of the subdivision, which is defined exclusively by Onext, Rot, and its derivatives.

SetOdata: PROC [e: Edge, d: EdgeData] = INLINE

{e.rec.ata[e.ix] ← d};

SetDdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetOdata [Sym[e], d]};

SetLdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetOdata [Tor[e], d]};

SetRdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetOdata [Rot[e], d]};

-- The procedures below replace the Odata (resp. Ddata, Ldata, Rdata) fields of an edge e, and also of all edges which can be reached from e by following the Onext (resp Dnext, Lnext, Rnext) links. They take time proportional to the number of such edges.

-- Note that changing the Odata, Ddata, Ldata and/or Rdata fields does not afect in any way the structure of the subdivision, which is defined exclusively by Onext, Rot, and its derivatives.

SetAllOdata: PROC [e: Edge, d: EdgeData];

SetAllLdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetAllOdata[Tor[e], d]};

SetAllDdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetAllOdata[Sym[e], d]};

SetAllRdata: PROC [e: Edge, d: EdgeData] = INLINE

{SetAllOdata[Rot[e], d]};

-- CONSTRUCTION AND MANIPULATION PRIMITIVES - - - - - - - - - - - - - - - - - - - - - -

-- The procedures in this section allow the client to build arbitrary subdivisions, without having to fiddle with the edge links.

MakeBridge: PROC [od, dd, ld, rd: EdgeData ← NIL] RETURNS [e: Edge];

-- Creates a subdivision with one face and two distinct vertices, connecterd by a single edge e. SetAlls the Odata, Ddata, Ldata and Rdata fields to the given values.

MakeLoop: PROC [od, dd, ld, rd: EdgeData ← NIL] RETURNS [e: Edge] = INLINE

-- Creates a subdivision with one vertex and two distinct faces, separated by a single edge e. SetAlls the Odata, Ddata, Ldata and Rdata fields to the given values

{RETURN [Rot[MakeBridge[ld, rd, dd, od]]]};

Splice: PROC [a, b: Edge];

-- Will merge Org[a] and Org[b] in a single vertex if they are distinct, or will split them if they are the same. In the first case the edges b, Onext[b], ... will be inserted just before a; in the second case, after the split we will have b, Onext[b], ..., Oprev[a] in one vertex, and a, Onext[a], ..., Oprev[b] in the other.

-- a and b must be real, distinct edges. Will not fix the Odata links.

-- Applying Splice[a, b] twice will reproduce the original subdivision.

-- DERIVED EULER OPERATIONS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- An arbitrary connected subdivision with ne edges can be built using ne calls to MakeBridge and ne calls to JoinVertices (below).

InvalidArguments: ERROR;

AttachEdge: PROC [e, a, b: Edge];

-- The first argument of AttachEdge is a bridge e that is the only edge in its component (as returned by MakeBridge). The edge e will be added to the subdivision(s) containing a and b, by inserting e in the vertex ring of Org[a] just after a, and Sym[e] in the ring of Org[b] just after b. Therefore, after the operation we will have Org[e]=Org[a], Dest[e]=Org[b], Right[e]=Left[a], Left[e]=Left[b], and Onext[a]=e, Onext[b]=Sym[e], .

-- The only restriction on the input parameters is that a#b. If a=e the origin of e will be left unattached, as a leaf vertex; similarly, if b=Sym[e] the destination of e will be left unattached. In particular, if a=e and b=Sym[e], the operation is a no-op.

-- If a#Sym[e], then after the operation we will have Onext[e]=old Onext[a]; similarly, if b#e, we will have Onext[Sym[e]]=old Onext[b] (these are the "normal" cases). If a=Sym[e], then we will get Onext[e]=old Onext[b], and e will be made into an empty loop oriented clockwise, incident at Org[b], lying just after b in the face Left[b]. Similarly, if b=e, we will have Onext[Sym[e]]=old Onext[a], and e will be made into an empty loop oriented counterclockwise, incident to Org[a] and lying just after a in the face Left[a]. However, if both a=Sym[e] and b=e, the operation will be a no-op.

-- The routine can be called with e other than an isolated bridge, but the meaning of such calls is a problem for the client to think about. All we can say is that this procedure is equivalent to the sequence {Splice[a, e]; Splice[b, Sym[e]]}.

-- The routine will not set any Data fields of e or any other edge; it is the client's resposibility to do that. Normally, the Data fields of e are set to their desired values when the edge is created by MakeBridge.

RemoveEdge: PROC [e: Edge] RETURNS [a, b: Edge];

-- Removes the directed edge e from the diagram and makes it into an isolated bridge. The old values of Oprev[e] and Oprev[Sym[e]] are returned in a and b, so that executing AddEdge[e, a, b]will restore the data structure to its original state.

-- This will merge Left[e] and Right[e] into a single face if they are distinct, and split them in two if they are the same.

-- In the second case, the split will occur at the two occurrences of e in the boundary of the face. As a consequence, the subdivision may be broken in two disconnected pieces, or may just lose one of its handles.

-- If AttachEdge [a, b] returns e, then applying DeleteEdge [e] to the resulting subdivision returns [a, b] and results in a subdivision isomorphic to the original one.

-- Only the edge links (Onext, Rot, and its derivatives) are updated; the Odata fields are not updated to reflect the splitting or merging of faces. Therefore, the client may have to call SetAllLdata[e, ...] or SetAllRdata[e, ...] explicitly after using this operator.

-- HANDY OPERATORS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

ConnectVertices: PROC [a, b: Edge] RETURNS [e: Edge];

-- This operator will create a new edge e and add it to the structure, inserting e in Org[a] immediately after a, and Sym[e] in Org[b] immediately after b. After the operation we will have Org[e]=Org[a], Dest[e]=Dest[a], Right[e]=Left[a], and Left[e]=Left[b].

-- The only precondition is that a#b. If a and b have the same left face, the latter will be split in two: Right[e] and Left[e] (=Left[b]). If a and b have different left faces fa and fb, the effect will be to replace those two faces with a single "tube", and run the new edge e lenghthwise across it. The tube will be split by e into a single disk-like face, so we will have Left[e]=Left[b]=Right[e]=Left[a]. In particular, if a and b are in two distinct diagrams, this operator will merge the two in a single connected component; otherwise, it will add an extra handle to the underlying manifold.

-- The only LData (Odata, Rdata, etc) fields that are set by this operation are those of e: it sets Odata[e]=Odata[a], Ddata[e]=Odata[b], Ldata[e]=Ldata[b], Rdata[e]=Ldata[a]. The values of Ldata[x], for all directed edges x c.c.w. around the original faces Left[a] and Left[b], are not updated to reflect the splitting or merging of those faces. Therefore, the client may have to call SetAllLeft[e, f] or SetAllRight[e, f], as appropriate, after using this operator.

DeleteEdge: PROC [e: Edge] = INLINE

-- Removes the edge e from the data structure (in the same way as RemoveEdge) and discards it.

{[]←RemoveEdge[e]};

-- MORE HANDY OPERATORS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- The two procedures below are useful in building subdivisions by adding faces one at a time. Suppose ff is the complement (exterior face) of the faces added so far, and let ef, ep be two edges (eventually the same) whith ff at their left. The sequence

-- FOR i IN [1..n] DO ep ← AddVertex [v[i], ep, left] ENDLOOP;

-- ep ← CloseFace [ep, ef, newf, left]

-- will cut out from ff a new face newf with new vertices v[1], v[2], ..., v[n], and sharing with the previous faces the path from ea up to (and including) eb.

EdgeSide: TYPE = {left, right};

AddLeaf: PROC [ep: Edge, side: EdgeSide, dd: EdgeData ← NIL] RETURNS [e: Edge];

-- If side = left, adds a new vertex v inside the face Left[ep], and connects Dest[ep] to it by means of a new edge e. Also sets Ldata[e]=Rdata[e]=Ldata[ep], Odata[e]=Ddata[ep], Ddata[e]=dd.

-- If side = right, does the same thing using Right[ep] instead of Left[ep], and Rdata[ep] instead of Ldata[ep].

CloseFace: PROC [ep, ef: Edge, side: EdgeSide, fd: EdgeData ← NIL] RETURNS [e: Edge];

-- If side = left, connects Dest[ep] to Org[ef] across the face Left[ef] (which should be the same as Left[ep]), by means of a new edge e. Also sets Odata[e]=Ddata[ep], Ddata[e]=Odata[ef], Rdata[e]=Ldata[ef], and sets all Ldatas of all edges on Left[e] to the given value fd.

-- If side = right, does the same thing using Right[ef] (which should be the same as Right[ep]) instead of Left[ef], and Rdata[ef] instead of Ldata[ef]. Also sets all Rdatas of all edges on Right[e] to the given value fd.

-- SUBDIVISION TRAVERSAL - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

VisitProc: TYPE = PROC [e: Edge, arg: REF ← NIL] RETURNS [res: REF ← NIL];

EdgeSet: TYPE = {all, oneWay, vertices};

Traverse: PROC [dg: Edge, Visit: VisitProc, arg: REF ← NIL, choice: EdgeSet ← all]
RETURNS [res: REF ← NIL];

-- Traverses a subdivision(given by one of its edges, dg) and performs arg ← Visit [e, arg] for every edge e in it. The final value of arg is returned as res.

-- If choice=all (default), Traverse will visit every directed edge of the primal subdivision exactly once (i.e., every undirected edge twice, once in each orientation). If choice=oneWay, it will visit only one member in each pair e, Sym[e]. Finally, if choice=vertices, Traverse will visit exactly one edge out of each vertex.

-- TOPOLOGICAL SORT OF VERTICES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

EdgePredicate: TYPE = PROC [e: Edge] RETURNS [BOOL];

TopSort: PROC
[dg: Edge, Visit: VisitProc, arg: REF ← NIL, Ordered: EdgePredicate, clockWise: BOOL ← FALSE]
RETURNS [res: REF ← NIL];

-- Enumerates the vertices of the subdivision in an order compatible with a partial order specified by a subset of the directed edges.

-- The predicate Ordered should be true for a directed edge e iff Org[e] is to precede Dest[e] in the output ordering. (It is O.K. if Ordered[e] and Ordered[Sym[e]] are both FALSE, but they should not be both TRUE, or an error will result).

-- The statement arg ← Visit[e, arg] is performed for exactly one edge e out of each vertex, in the final order. The final value of arg is returned in res. If dg has a single dummy edge, Visit will be called exactly once, with e=dg.

-- If the relative ordering of two vertices is not specified by the Ordered predicate or its transitive closure, normally the first of them to be visited will be the one whose "reference count" most recently became zero. If both vertices are "sources" (i.e., both had zero reference counts to begin with), they will be visited in arbitrary order.

-- When a vertex v is visited, it is either because it was a source in the first place, or because the reference count of v dropped to zero when TopSort visited some neighbor u of v. In this second case, after visiting v, the reference counts of its neighbors will be decremented in ccw order, starting at u. (the direction of scan can be reversed by setting clockWise to TRUE).

-- On the other hand, if v is a source, the starting point for the neighbor scan will be somewhat arbitrary. However, if dg is an edge out of v, then the scan will begin at that edge.

-- If Org[dg] and Dest[dg] are the only source and sink in the subdivision, and the genus of the latter is zero, it turns out that ties will be disambiguated by their counterclockwise order as seen from Dest[dg] (given the above conditions, this counterclockwise ordering can be unambiguously defined for all vertices, even if they are not neighbors of Dest[dg]).

-- For example, if the subdivision is embedded in the plane in such a way that all vertices are above the edge dg, and Ordered[e] is true iff e points strictly to the right, then in case of a tie the vertex with highest y coordinate (or lowest, of clockWise=TRUE) will be output first.

-- DEBUGGING - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

PutE: PROC [e: Edge];

-- Prints out (in the debugging viewer) the edge number as "n:x ", where n is the .no field of e.rec, and x is the index of the specific quarter edge.

PutORing: PROC [e: Edge];

-- Prints out all edges in the Onext ring of e. Prints a "#" between any two consecutive edges with different Org pointers.

PutLRing: PROC [e: Edge];

-- Prints out all edges in the Lnext ring of e. Prints a "#" between any two consecutive edges with different Left pointers.

PutDRing: PROC [e: Edge];

-- Prints out all edges in the Onext ring of e. Prints a "#" between any two consecutive edges with different Dest pointers.

PutRRing: PROC [e: Edge];

-- Prints out all edges in the Lnext ring of e. Prints a "#" between any two consecutive edges with different Right pointers.

PutDiagram: PROC [e: Edge];

-- Prints out (using PutORing) all vertex rings in the subdivision e.

-- EDGE REPRESENTATION - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- FOR DARING EYES ONLY --

-- An undirected edge e is represented by four "quarter edges", each corresponding to one sense of traversal of e. These quarter edges are stored in a single record, so a Edge is a pair [REF to edge record, index to a specific quarter]. We have therefore Rot[ [rec, ix] ] = [rec, (ix+1) mod 4], Sym[ [rec, ix] ] = [rec, (ix+2) mod 4], and so forth.

EdgeRec: TYPE = RECORD -- One half of an undirected edge
[data: ARRAY [0..4) OF EdgeData, -- Odata[e] is e.rec.data[e.ix]
next: ARRAY [0..4) OF Edge, -- directed edge following e in ccw order around Org[e]
no: EdgeNo -- edge serial number (for debugging & traversal)
];

EdgeNo: TYPE = NAT;

EdgeCount: READONLY EdgeNo; -- number of EdgeRecs allocated so far

END.

Edited on April 8, 1983 5:33 pm, by Stolfi

Changed everything to conform to STOC paper. Changed also names and meanings of almost all functions: beware!