INTERFACE TrapSub; IMPORT Wr; (* Sweep directions: *) TYPE WEDir = {W, E}; (* Longitudinal directions: `west' and `east'. *) SNDir = {S, N}; (* Latitudinal directions: `south' and `north'. *) (* The input data: *) TYPE VertexId = CARDINAL; (* Identifies one of the input points. *) CurveId = CARDINAL; (* Identifies one of the input curves. *) TrapId = CARDINAL; (* Identifies one of the output trapezoids. *) (* The output structure: *) TYPE Vertex = REF RECORD id: VertexId; (* Numeric ID of vertex, as input. *) tip: CurvePair; (* North and south visible curves; or NIL if none. *) stitch: VStitches; (* Trapezoids adjacent to the cut's ends. *) END; Curve = REF RECORD id: CurveId; (* Numeric ID of curve, as input. *) tip: VertexPair; (* West and east endpoints of the curve. *) stitch: CStitches; (* Trapezoids adjacent to the curve's ends. *) END; Trap = REF RECORD id: TrapId; (* Numeric ID of trapezoid, serial from 0. *) curve: CurvePair; (* North and south bounding curves; or NIL if none. *) vertex: VertexPair; (* West and east bounding cuts. *) END; VertexPair = ARRAY WEDir OF Vertex; CurvePair = ARRAY SNDir OF Curve; VStitches = ARRAY SNDir OF ARRAY WEDir OF Trap; CStitches = ARRAY WEDir OF ARRAY SNDir OF Trap; PROCEDURE Build( nV: CARDINAL; (* Number of vertices *) nC: CARDINAL; (* Number of curves *) READONLY tipW: ARRAY (* CurveId *) OF VertexId; READONLY tipE: ARRAY (* CurveId *) OF VertexId; isWest: PROCEDURE (u, v: VertexId): BOOLEAN; isSouth: PROCEDURE (v: VertexId; c: CurveId): BOOLEAN; isSouthAtRef: PROCEDURE (a: CurveId; b: CurveId): BOOLEAN; isSouthAtTip: PROCEDURE (which: WEDir; a: CurveId; b: CurveId): BOOLEAN; VAR (*OUT*) rV: ARRAY (* VertexId *) OF Vertex; VAR (*OUT*) rC: ARRAY (* CurveId *) OF Curve; VAR (*OUT*) rT: ARRAY (* TrapId *) OF Trap; ): REF ARRAY OF Trap; (* Computes a trapezoidal subdivision for a given set of isolated points and non-intersecting curves on the sphere (or on the two-sided plane). The trapezoidalization is relative to a distinguished point "N" on the sphere, the `north pole'. The antipode "-N" of "N" is the `south pole'. A `meridian' is an open half-line with endpoints "N" and "S". The `west-to-east' order of the meridians is their cyclic positive (counterclockwise) order around the "N" pole. We assume that every input curve can be described by a continuous function "c" that assigns to each meridian "m" a point "c(m)" on "m". The domain of "c" must be some open interval of meridians, and no point of the sphere can lie on more than one curve. The limit of "c(m)" when "m" tends to the western end of the domain must be defined, and is called the `western vertex', or `western tip' of the curve; and analogously for the `eastern vertex'. In addition to the curves and their tips, the input data may include isolated vertices, which are not the tip of any curve. The vertices must be pairwise distinct points of the sphere. A vertex may be shared by several curves, but it may not lie *in* any curve. All together, the procedure assumes there are "nV" vertices and "nC" curves. The vertices are identified by consecutive serial numbers, starting from 0, in arbitrary order; and same for the curves. The array "tipW", indexed by curve ID, gives the ID of the west vertex of each curve; and "tipE" gives the east vertex. If the west and east tips of a curve "c" are the same vertex "v", the curve is assumed to make one full turn around the poles; that is, the domain of "c" is the set of all meridians, minus "m(v)". The procedure assumes that the poles "N" and "S" are distinct from all input vertices. Thus, for each vertex "v" there is a unique meridian "m(v)" that contains "v". It also assumes that no two input vertices have the same meridian. Therefore, the `west-to-east' cyclic ordering of the meridians around the north pole induces a strict cyclic `west-to-east' ordering of the input vertices. This circular ordering of the vertices must be turned by the client into a strict *linear* order, by cutting it at an arbitrary `reference meridian' "m_0" that does not go through any vertex. The procedure "isWest(u,v)" is assumed to return TRUE iff vertex "u" precedes "v" in this this linear order. Note that the `western tip' of a curve "c" will come *after* the `eastern tip', in the west-to-east vertex order, if the reference meridian lies in the domain of "c". We also say that a point "p" is `south' of a point "q" iff "p" lies on the segment "S q"; and "p" is `north' of "q" iff it lies on the segment "q N". If "c" is any curve, and "v" is any vertex such that "m(v)" is in the domain of "c", then "isSouth(v, c)" must tell whether "v" lies south of "c(m(v))". For any two distinct curves "a" and "b" that cross the reference meridian "m_0", the procedure "isSouthAtRef" is assumed to test whether "a(m_0)" is south of "b(m_0)". If the curves "a" and "b" have a common western tip "v", the call "isSouthAtTip(W, a, b)" is assumed to tell whether "a(m)" ultimately lies south of "b(m)" as the meridian "m" tends to "m(v)" from the east; and symmetrically for "isSouthAtTip(E, a, b)". The output of the procedure is a partition of the sphere, minus the "N" and "S" poles, into a collection of `elements' of three types: input curves, `vertex cuts', and `trapezoids'. For each input vertex "v", there is one `vertex cut' "c(v)", which is the maximal open segment of "m(v)" that contains "v" but does not contain any curve point. The `north tip' of "v" is the curve that defines the north endpoint of "c(v)"; or "NIL" if that endpoint is the "N" pole. The `south tip' of "v" is defined in the same way. These edges are stored in the "Vertex" record corresponding to "v", in the fields "v.tip[S]" and "v.tip[N]". For each input curve "c", the procedure returns an associated "Curve" record, containing (among other things) the pointer "c.tip[W]" and "c.tip[E]" to the vertex records representing the west and east tips of the curve. If we remove from the sphere all the curves and vertex cuts, and the "N" and "S" poles, the remainder falls apart into a finite set of conncted open regions; these are the `trapezoids'. Each is represented by a "Trap" record. They are numbered consecitively, starting from 0. The `north boundary' of a trapezoid "t", stored in "t.curve[N]", is either a single curve, or the north pole "N" (represented by "NIL"); and analogously for the `south boundary'. The `west boundary' of "t", stored in "t.vertex[W]", is always a vertex cut; and ditto for the `east boundary'. Note however that either of these boundaries may reduce to a single point, if the north and south boundary curves have a common vertex. Each curve record "c" also includes four `corner stitch' fields, "c.stitch[W..E][S..N]", which point to the trapezoids adjacent to the curve's western and eastern ends, on the south and north sides of the curve, respectively. Similarly, each vertex cut "v" has four `corner stitch' fields, "v.stitch[S..N][W..E]", which point to the trapezoids adjacent to the cut's south and north ends, on the west and east sides of the cut, respectively. These fields are defined even if the cut extends all the way to the poles. The procedure stores into the arrays "rV", "rC", and "rT" pointes to the vertex, curve and trapezoid records, indexed by the respective ID's. These arrays must have the right number of elements; in particular, "rT" must have exactly "nV + nC" elements. The procedure also returns as the result of the call a new array of pointers to all trapezoids that cross the reference meridian, in south-to-north order. *) PROCEDURE Print( wr: Wr.T; READONLY rV: ARRAY (* VertexId *) OF Vertex; READONLY rC: ARRAY (* CurveId *) OF Curve; READONLY rT: ARRAY (* TrapId *) OF Trap; READONLY rA: ARRAY OF Trap; ); (* Prints on "wr" the elements and links of a trapezoidals subdivision, given its vertices ("rV"), curves ("rC"), trapezoids ("rT"), and starting trapezoids ("rA"), as returned by "Build". *) END TrapSub.