INTERFACE GDGeometry;

(* Geometric procedures for integer points *)

(* BASIC TYPES *)

TYPE
  INT = INTEGER;   INTS = ARRAY OF INT;
  NAT = CARDINAL;  NATS = ARRAY OF NAT;
  BOOL = BOOLEAN;  BOOLS = ARRAY OF BOOL;
  LONG = LONGREAL; LONGS = ARRAY OF LONG;
  SIGN = [-1..+1]; SIGNS = ARRAY OF SIGN;

(* BASIC GEOMETRIC TYPES *)

TYPE
  Axis = [0..1];
  
  Point = ARRAY Axis OF INT;
  Points = ARRAY OF Point;

  Interval = RECORD lo, hi: INT END;
  Box = ARRAY Axis OF Interval;     (* [0] = X, [1] = Y *)
  
  Weight = NAT;              (* Weight for cost computation *)
  Weights = ARRAY OF Weight; 

(* PROCEDURES *)

PROCEDURE SGN(x: INT): SIGN;
  (*
    The sign of "x". *)

PROCEDURE InterpolateCoords(u, v: INT; r, s: INT): INT;
PROCEDURE InterpolatePoints(u, v: Point; r, s: INT): Point;
  (*
    Interpolates linearly between the integer coordinates/points
    "u" and "v", proportionally to the ratio "r/s". *)
  
PROCEDURE GetBounds(READONLY pt: Points): Box;
PROCEDURE GetRange(READONLY pt: Points; axis: Axis): Interval;
  (*
    The smallest enclosing box for the given points. *)

PROCEDURE Medians(READONLY pt: Points; axis: Axis): Interval;
PROCEDURE Median(READONLY pt: Points; axis: Axis): LONG;
  (* 
    "Medians" returns the narrowest interval "r" containing all median
    coordinates (integer OR real) of the given points along the given
    "axis". If "r.lo = r.hi" there is a single median equal to those
    two values. If "r.lo < r.hi" the medians are all real values in
    the OPEN interval "(r.lo .. r.hi)". Note that if "r.hi - r.lo = 1"
    there is no integer median; otherwise the integer medians are
    "[r.lo+1..r.hi-1]".
    
    "Median" returns the midpoint of the interval returned by "Medians". *)

PROCEDURE LexCompare(READONLY p, q: Point): SIGN;
  (*
    Compares points lexicographically, first "y" then "x". *)

PROCEDURE PickOutside(r: Interval; xBar: LONG; dir: SIGN): INT;
  (*
    Returns an integer value closest to "xBar" outside the
    range "r", breaking ties in the direction "dir". *)

END GDGeometry.
(* Last edited on 2000-01-10 06:30:38 by stolfi *)