INTERFACE TrapSub;

(* Sweep directions: *)

TYPE
  WEDir = {W, E};
  SNDir = {S, N};
  
(* The input data: *)

TYPE
  VertexId = CARDINAL;  (* Identifies one of the input points. *)
  EdgeId = CARDINAL;    (* Identifies one of the input edges. *)
  TrapId = CARDINAL;    (* Identifies one of the output trapezoids. *)
  
CONST
  NoVertex = FIRST(VertexId) - 1;
  NoEdge = FIRST(EdgeId) - 1;

TYPE
  VertexIdOrNil = [NoVertex..LAST(VertexId)];
  EdgeIdOrNil = [NoEdge..LAST(EdgeId)];
    
  EdgeSpan = ARRAY WEDir OF VertexId;
  VertexSpan = ARRAY SNDir OF EdgeIdOrNil;
  
(* The result structure: *)
  
TYPE
  TrapId = CARDINAL;   (* Identifies one of the output trapezoids. *)
  
  Trap = RECORD
      snBound: ARRAY SNDir OF EdgeIdOrNil;
      weBound: ARRAY WEDir OF VertexId;
    END;
    
  EdgeCorners = ARRAY WEDir OF ARRAY SNDir OF TrapId;
  
  VertexCorners = ARRAY SNDir OF ARRAY WEDir OF TrapId;
    
PROCEDURE Trapezoidalize(
    nVertices,
    
    READONLY eSpan: ARRAY (* EdgeId *) OF EdgeSpan;
    
    isWestVV:  PROCEDURE (u, v: VertexId): BOOLEAN;
    isSouthVE: PROCEDURE (v: VertexId; e: EdgeId): BOOLEAN;
    isSouthEE: PROCEDURE (a: EdgeId; b: EdgeId): BOOLEAN;

    VAR (*OUT*) vSpan: ARRAY (* VertexId *) OF VertexSpan;
    VAR (*OUT*) eCorner: ARRAY (* EdgeId *) OF EdgeCorners;
    VAR (*OUT*) vCorner: ARRAY (* VertexId *) OF VertexCorners;
  ): REF ARRAY OF Trap;
  (*
    Computes a trapezoidal subdivision for a given set of 
    non-intersecting edges 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 edge can be described by a continuous
    function "e", that to each meridian "m" assigns a point "e(m)" on
    "m".  The domain of "e" is assumed to be some open interval of
    meridians, and edges are pairwise disjoint.
    
    The limit of "e(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 edge; and analogously for the `eastern vertex'.  A vertex
    may be shared by several edges, but it may not lie *in* any edge.
    
    We also assume that "N" and "S" are distinct from all input
    vertices.  Thus, we for each vertex "v" there is a unique meridian
    "m(v)" that contains "v".  We further assume that no two input
    vertices have the same meridian.
    
    Thus, the positive (counterclockwise) cyclic ordering of the
    meridians around the north pole induces a strict cyclic ordering
    of the input vertices, which we call `west to east'.
    
    We assume that this circular ordering has been turned into a strict
    linear order, by the arbitrary choice of a `reference meridian'
    that does not go through any vertex.  The procedure "isWestVV"
    is assumed to compare vertices according to this linear order.

    Note that the `western tip' of an edge "e" will come *after* the
    `eastern tip' in the linear vertex order, if the reference
    meridian lies in the domain of "e".
    
    We also say that a point "p" is `south' of point "q" iff "p" lies
    on the segment "S q"; and is `north' of "q" iff it lies on the
    segment "q N".
    
    In particular, if "e" is any edge, and "v" is any vertex such that
    "m(v)" is in the domain of "e", then we say that 'v" is either
    `north' of "e" if it is `north' of "e(m(v))"; and similarly for
    `south'.  The procedure "isSouthVE" is assumed to test this condition.
    
    Moreover, given two edges "a" and "b" with overlapping domains, 
    either "a(m)" is north of "b(m)" for all common meridians "m",
    or "a(m)" is south of "b(m)" for all those "m".  The procedure 
    "isSouthEE" is assumed to test for this condition.
    
    The output of the procedure is a partition of the sphere, minus
    the input edges and the "N" and "S" poles, into a collection of
    `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 edge point.  The `north tip' of "v" is the edge
    that defines the north endpoint of "c(v)"; or "NoEdge" if that
    endpoint is the "N" pole.  The `south tip' of "v" is defined in
    the same way.
    
    If we remove from the sphere all the edges 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'.  
    
    The `north boundary' of a trapezoid "t", stored in
    "t.ns[SNDir.N]", is either a single edge, or the north pole "N"
    (represented by "NoEdge"); and analogously for the `south
    boundary'.  
    
    The `west boundary' of "t", stored in "t.ew[WEDir.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 edges have a common vertex.
  *)      

END TrapSub.