INTERFACE SMGeo;
(* 
   This interface defines the geometry of the elements of a spherical map 
   and is based on the article:
    
       M. V. A. Andrade and J. Stolfi, Exact Algorithms for Circles on
         the Sphere, XII SoCG, 1998.

   A vertex will be represented as a "\Cpoint", that is, the geometry 
   of a vertex "v" will be represented by the 6-tuple Plucker coordinates of a 
   line "r" such that "\Exit(r)=v".
   
   An edge can be either an entire \Scircle (an oval) or an \Sarc (an
   arc of an \Scircle). The \Sarc denoted by "sarc(p,q,c)" corresponds
   to the non empty arc of the \Scircle "c" that starts at the point
   "p" and ends at point "q" in the positive sense of travelling along
   "c".
   
   An oval will be represented by the coeffcients of the \Scircle
   corresponding to it. The \Sarc "s=sarc(p,q,c)" will be represented
   by a triple "a,b,c", where "c" corresponds to the coefficients of
   the supporting circle of the arc, shortly "scircle(s)", and "a" and
   "b" are planes such that
          
                  "p=\Exit(\splane(c) \meet a)"
                  "q=\Exit(\splane(c) \meet b)"

   In other words, instead of storing the Plucker coefficients of the
   stabbing lines for each vertices "p" and "q", we will store the
   coefficients of the planes whose intersection with "\splane(c)" are
   those stabbing lines.  
   
   Note that two points "u" and "v" on an oriented circle "c" allows
   us to define 4 different arcs: 
      (u,v,c) -> origin "u", destination "v" in the direction of "c"
      (u,v,\neg c) -> origin "u", destination "v" in the opposite direction of "c"
      (v,u,c) -> origin "v", destination "u" in the direction of "c"
      (v,u,\neg c) -> origin "v", destination "u" in the opposite direction of "c"
      
   Created in Feb. 18, 1997 by Marcus Vinicius A. Andrade.
   Last edited in Jun. 28, 2000 by Marcus Vinicius A. Andrade.
*)   

IMPORT HI3, SMPoint, SMCircle, Rd, Wr;

EXCEPTION ValidationError(TEXT);

TYPE  
  Point  = REF SMPoint.CT;
  Plane  = REF HI3.Plane; 
  Circle = REF SMCircle.T; 
  Arc    <: REFANY; 
  Sign   = HI3.Sign;

VAR NorthPole : Point;        (* will be initialized with "<0,0,1,0,0,0>" *)

PROCEDURE CheckArc(READONLY s : Arc) RAISES {ValidationError};
  (* 
     Checks the arc s to verify if the origin and destination 
     are on the supporting circle *)

PROCEDURE AreSamePoints(p,q: Point) : BOOLEAN;
  (* 
    Returns TRUE if  "p=q" *)
    
PROCEDURE AreSameCircles(c1,c2 : Circle) : Sign;
  (* 
     Returns +1 if "c1=c2"; -1 if "c1=Inv(c2)" and 0 otherwise *)

PROCEDURE InvStabbingLine(p: Point) : Point;
  (* 
    Let "r" be the stabbing line for "p", then this rotine returns
    the line "\neg r". That is, given the point "\Exit(r)", this 
    rotine returns the point "\Ent(r)".  *)

PROCEDURE InvCircle(c: Circle) : Circle;
  (* 
    Returns a circle with the opposite orientation to "c". *)

PROCEDURE SidePointCircle(p: Point; c: Circle) : Sign;
  (* 
    Returns +1,0,-1 depending if the C-point "p" is respectively on
    the left side, belongs to or on the right side of the \Scircle "c".  *)

PROCEDURE MakeArc(u,v : Point; c: Circle) : Arc RAISES ANY;  
  (* 
    Allocates space for a new arc, sets its fiels and returns it *)

PROCEDURE GetOrgOfArc(s: Arc) : Point;
  (* 
    Returns the initial point of the arc "s".  *)

PROCEDURE GetDstOfArc(s: Arc) : Point;
  (* 
    Returns the final point of the arc "s".  *) 

PROCEDURE ScircleOfArc(s: Arc) : Circle;
  (* 
    Returns the supporting circle of the arc "s" *)

PROCEDURE InvArc(s: Arc) : Arc RAISES ANY;
  (* 
    Inverts the orientation of the arc, that is, inverts the
    orientation of the supporting circle of the arc and exchanges 
    "origin" and "destination".  *)

PROCEDURE PlaneDefPointOnCircle(p: Point; c: Circle) : Plane RAISES ANY;
  (*
    Returns a plane "a" such that the intersection between the circle
    "c" and "a" is the stabbing line of "p", that is, "c \meet a = p" *)

PROCEDURE GeneratePointOnCircle(c: Circle) : Point;
  (*
    Generates a point on the circle "c". *)
    
PROCEDURE CirclePassingThroughPoint(p: Point) : Circle RAISES ANY;
  (*
    Returns a circle passing through the point "p". *)

PROCEDURE CircleByTwoPoints(p,q: Point; VAR sc : Circle) : BOOLEAN RAISES ANY;
  (*
    Tries to create a rational circle passing through the two points "p"
    and "q"; requires that the stabbing line of "p" and "q" are
    coplanar or that either "p" or "q" is an "A-point". If it occurs, 
    creates the circle, stores its coefficients in "sc" and returns TRUE; 
    on the other hand, returns FALSE and sets "sc=NIL" *)

PROCEDURE CircOrd3PointsOnCircle(p,q,r: Point; c: Circle) : Sign RAISES ANY;
  (*
    Given three points "p", "q", and "r" on the \Scircle "c", returns
    +1 if the three points occur in that order along the oriented
    \Scircle "c" in positive sense of travelling; -1 if the points
    occur in opposite order and 0 if any two points are equal.  *)
    
PROCEDURE IsPointInArc(p: Point; sarc: Arc; VAR sp: Sign) : BOOLEAN RAISES ANY; 
  (* 
    Returns TRUE if the point "p" belongs to the arc "sarc". Besides,
    returns in "sp" the information whether the point "p" is one of
    the extremities of "sarc" or it is an internal point. More precisely,
    if "p" is the origin of "sarc" then sets "sp=+1"; if "p" is
    internal to "sarc" then sets "sp=0" and if "p" is the destination of
    "sarc" then sets "sp=-1". If "sarc" is a loop (i.e., has "origin =
    destination") and "p = origin = destination" then sets "sp=+1". *)

PROCEDURE IntersectionOfTwoArcs(A,B: Arc; perturb: Sign; VAR tangent: BOOLEAN; 
                                          VAR p: Point) : BOOLEAN RAISES ANY;
  (*
    Returns TRUE if the two arcs "A" and "B" interserct and the point of 
    intersection is kept in "p". By definition, the intersection of two 
    circles consists of zero or one point and this point is determined by 
    the direction of the two circles: 
    
         "line(p) = scircle(A) \meet scircle(B)"
    *)
    
PROCEDURE CircOrdOf3ArcsAroundVertex(A,B,C : Arc; v: Point) : Sign RAISES ANY;
  (* 
    Given three \Sarcs "A,B,C" with a common origin "v", checks the
    circular order of the three \Sarcs around the point "v", that is,
    starting at "A" and turning around "v" in counterclockwise
    direction, checks whether the next \Sarc is "B" or not. Returns +1
    if the next \Sarc is "B", -1 if not (i.e. if the next is "C") and
    0 if any \Sarc is contained in another one.  *)

PROCEDURE ReadPoint(rd: Rd.T) : Point RAISES ANY;
PROCEDURE ReadCircle(rd: Rd.T) : Circle RAISES ANY;
PROCEDURE ReadArc(rd: Rd.T; eps: LONGREAL:=1.0d-6) : Arc RAISES ANY;
  (* 
    Reads a point, a circle and an arc on the given reader "rd" *)

PROCEDURE PrintArc(wr: Wr.T; s: Arc) RAISES ANY;
  (* 
    Prints an arc on the given writer "wr" *)

END SMGeo.