(******************************************************************************
 ** HALFSPACE.sml
 ** sml
 **
 ** Franklin Chen and Guy Blelloch 
 ** The HALFSPACE signature used as part of the GEOMETRY signature
 ******************************************************************************)

(* A HALFSPACE is a region in a d dimensional space defined by being
  on one side of a d-1 dimensional hyperplane.   Points can be either
  In, On or Out of a Halfspace.   They are on if they are on the surface
  of the dividing hyperplane. *)

signature HALFSPACE =
    sig
	exception DegenerateInput

        structure Point : POINT 
        structure Vec : VEC = Point.Vec
        structure Number : NUMBER = Point.Number

	type halfSpace
	type t = halfSpace
	 
        (* Return the normal of a halfspace. *)
	val normal: halfSpace -> Vec.t

	(* Generates a halfspace in d dimensions from a sequence
	 of d points that are assumed to be on the d-1 dimensional
         dividing hyperplane.     The halfspace is oriented using the
         right-hand rule (thumb pointing in) based on the order of the
         input points.    Raises DegenerateInput if the points are 
	 not in general position (i.e. lie in a d-2 dimensional hyperplane.) *)
       	val fromPoints : Point.t Sequence.seq -> t

        (* Generates a halfspace from the vector normal to the dividing
	 hyperplane and a point on the hyperplane.  Raises DegenerateInput
         if the normal is the zero vector *)
	val fromNormal : Vec.t * Point.t -> t

	(* Inverts the sense of a halfspace *)
        val invert : t -> t

        val == : t * t -> bool
        val != : t * t -> bool
        val toString : t -> string

	(* Returns In, On, or Out *)
        val pointIn : t -> Point.t -> Side.t

        (* Returns the distance from a point to the dividing hyperplane.
	   This distance is negative if the point is out of the halfspace. *)
        val pointDist : t -> Point.t -> Number.t

    end