INTERFACE TMC; (* This interface defines the representation of the topology of two dimensional maps, where - a Vertex is a point on a two dimensional surface and can be either incident to an edge or an isolated vertex (i.e., incident to NO edge). - an Edge can be either an oval (closed Jordan curve) or an open arc incident to two vertices: one at each end. In particular, the two vertices can be equal. - a Border is a (maximal) oriented connected alternated sequence of vertices and edges adjacent to a same face. In particular, an isolated vertex or an oval corresponds to a border consisting of only that one element. - a Face is a multidisc; that is, either the whole spherical surface or an open connected subset of the spherical surface whose boundary is a finite set of borders. As we know, the topology of a map can be described by the incidence relationship between the elements (vertices, edges and faces) of the map. In other words, the topology of a map corresponds to describe, for each element, the list of its neighbors, that is, the list of (other) elements incident on it. More specifically, the topology of a vertex is defined by the circular list of edges and faces incident on it. The topology of an edge is defined by its boundary vertices and by its adjacent faces. The topology of a face is defined by the list of its borders. To represent the topology of two dimensional maps -- i.e., the incidence relantionships between their elements -- we will use the concept of "Corner": a triple "(v,e,f)" where "v" describes the topology of a vertex, "e" defines the topology of an edge incident to "v"; in fact, "e" is a halfedge (considering the two possible travel on the edge) and "f" defines the topology of a face adjacent to "e" and incident to "v". The topology of the map will be given by the set of all corners defined over all elements fo the map. It's important to notice that the elements "v" and "e" in a corner can be left "blank" -- with value NIL. More specifically, . the corner "(NIL,e,f)" corresponds to an oval "e" whose left face is "f"; . the corner "(v,NIL,f)" corresponds to an isolated vertex "v" on the face "f". Created in Jan 21, 1997 by Marcus Vinicius A. Andrade. Lasted edited in May 6, 1998 by Marcus Vinicius A. Andrade. *) IMPORT SetOfBorders, TMCFeat, FileWr, FileRd; EXCEPTION ValidationError(TEXT); TYPE QueueOfCorners <: REFANY; QueueOfFaces <: REFANY; TCounter = RECORD NC, NB, NF : CARDINAL (* number of corners, borders and faces *) END; Vertex = TMCFeat.VFType; Edge = TMCFeat.EFType; HalfEdge = TMCFeat.HEFType; Corner <: Public; Public = TMCFeat.T OBJECT METHODS createIsolatedVertex(): Corner; createEdge(): Corner; createOval(): Corner; isIsolatedVertex(): BOOLEAN; isOval(): BOOLEAN; org(): Vertex; halfEdge() : HalfEdge; borderOf(): Border; left(): Face; oNext(): Corner; oPrev(): Corner; lNext(): Corner; lPrev(): Corner; sym(): Corner; splice(c: Corner); split(c: Corner); END; (* ==== a client-provided "element" visitation procedure ==== *) VisitProc = PROCEDURE (ic: Corner); Border <: PublicBorder; PublicBorder = TMCFeat.BFType OBJECT METHODS borderDesc(): Corner; (* the corner descriptor of a border *) faceOf() : Face; (* the left face of a border *) removeCorner(c: Corner); (* removes the corner "c" of the border *) walkOn(P: VisitProc; GetFaces: BOOLEAN:=TRUE; qftv: QueueOfFaces:=NIL); (* performes "P" in all corners of the border; if GetFaces = TRUE then stores the neighbor faces to make possible to complete face's visit *) END; Face <: PublicFace; PublicFace = TMCFeat.FFType OBJECT METHODS genus() : CARDINAL; (* the genus, i.e. the number of borders (holes) in a face *) bordersOf() : SetOfBorders.T;(* the set of borders in the face's boundary *) transferBorder(b: Border); (* removes the border "b" from its face and inserts it in the face "self" *) mergeFaces(f: Face); (* modifies the set of borders of "self" merging it with the set of borders of "f" *) walkOn(P: VisitProc; GetFaces: BOOLEAN:=TRUE; qftv: QueueOfFaces:=NIL); (* performes "P" in all borders of the face; if GetFaces = TRUE then stores the neighbor faces to make possible to complete map's visit *) END; Map <: PublicMap; PublicMap = OBJECT METHODS init() : Map; getTCounter() : TCounter; setTCounter(cnt: TCounter); refFace() : Face; setRefFace (f: Face); refCorner() : Corner; setRefCorner(c: Corner); walkOn (P: VisitProc); read(rd: FileRd.T; vStack: REF ARRAY OF Vertex; eStack: REF ARRAY OF Edge); write(wr: FileWr.T; vStack: REF ARRAY OF Vertex; eStack: REF ARRAY OF Edge); END; PROCEDURE DropOnEdge(c: Corner) : Corner; (* Creates a "new" vertex on the edge "e=c.edge()" in such a way that, if "e" is an oval, just transforms it into a loop creating a vertex on the two corners "c" and "c.sym()"; otherwise, the two corners on the edge "e" are replaced by four new corners. A corner on the new vertex is returned. Note that, this operation doesn't change the topology of the faces, that is, it just breaks the chain of corners in the borders "c.borderOf()" and "c.sym.borderOf()" inserting a new corner after "c" and another after "c.sym" (both on a same vertex). In fact, this operation could be implemented as a composition of splices. However, this composition could be very inefficient since it would require two unnecessary borders redistribuition. *) (* ----------------------------------------------------------------- Description of the methods of T ----------------------------------------------------------------- createIsolatedVertex() : Creates an isolated vertex; by definition, initializes a map with a face with one border consisting of that vertex; returns the corner corresponding to that vertex; createEdge() : Creates an edge; by definition, initializes a map with a face with one border consisting of that edge; returns one of the corners on that edge; createOval() : Creates an oval; by definition, initializes a map with two faces, each one with one border consisting of that oval; returns a corner on the oval. oNext() : returns the next counterclockwise corner orbiting the vertex; oPrev() : returns the previous counterclockwise (i.e. the next clockwise) corner orbiting the vertex; lNext() : returns the next corner on the border of the left face; lPrev() : returns the previous corner on the border of left face; borderOf(): returns the value of the field border; left() : returns the left face whose border contains that corner; sym() : returns the corner symetric to that object, that is, the corner on the other end of the edge defined by the object; splice(c): joins the vertices of the two corners "self" and "c", that is, the vertex orbit of "self" will inserted just after "c" and vice-versa. It is required that the two corners are adjacent to a same face. If the borders of "self" and "c" are equal then creates two new faces, each one with one border and each border described by "self" and "c". On the other hand, if the borders are different, creates only one face with one border described by "self". In both cases, the borders involved in the operation are removed from its original face(s); split(c) : splits the orbit of corners around the common vertex of "self" and "c"; the onext of "c" will be the onext corner of "self" and vice-versa. It is required that "self" and "c" are corners in a orbit of a same vertex. If "self" and "c" are adjacent to a same face then breaks the vertex orbit and separates the border creating a new face with two borders: one described by "self" and another one described by "c". On the other hand, if "c" and "self" are adjacent to different faces then just open the vertex joining the two faces in one new face with one border corresponding to the "union" of the original borders involved in the operation. In both cases, the borders involved in the operation are removed from its original face(s). ----------------------------------------------------------------- *) END TMC.