with Standard_Integer_Vectors; use Standard_Integer_Vectors;
with Standard_Integer_VecVecs; use Standard_Integer_VecVecs;
package Simplices is
-- DESCRIPTION :
-- The simplices are facets on the lower hull of a lifted polytope
-- spanned by standard integer vectors.
-- DATA STRUCTURE :
type Simplex is private;
Null_Simplex : constant Simplex; -- empty simplex
-- CREATORS :
function Create ( x : VecVec ) return Simplex;
-- DESCRIPTION :
-- Given the vertices, the simplex will be created.
procedure Update ( s : in out Simplex; x : in Link_to_Vector;
k : in natural );
-- DESCRIPTION :
-- Creates a neighboring simplex by pivoting the kth point in the
-- simplex by the given point x.
procedure Update ( s : in out Simplex; x : in Link_to_Vector;
pos : in Vector );
-- DESCRIPTION :
-- Creates neighboring simplices by pivoting the points in the
-- simplex by the given point x.
-- ON ENTRY :
-- s simplex, volume(s) > 0;
-- x a certain point to be considered for update;
-- pos the position vector of x.
-- ON RETURN :
-- s updated, so that the neighbors of s contain the new
-- simplices.
procedure Update_One ( s : in out Simplex; x : in Link_to_Vector;
pos : in Vector );
procedure Update_One ( s : in out Simplex; x : in Link_to_Vector;
pos : in Vector; news : out Simplex );
-- DESCRIPTION :
-- Creates at most one new simplex that contains x.
-- It will be assumed that there are no internal points, so no more
-- than one new simplex will be constructed. When x already belongs
-- to s or to one of its neighbor, then nothing will be done.
-- The specifications of s,x and pos are the same as the other
-- Update operation, except for the new parameter news wich returns
-- the new simplex that contains x.
generic
with procedure Process ( news : in Simplex; cont : out boolean );
procedure Update_All ( s : in out Simplex; x : in Link_to_Vector;
pos : in Vector; ancestor : in Simplex );
-- DESCRIPTION :
-- Computes all new simplices that can be derived from the initial
-- simplex s and the new point x.
-- The ancestor simplex prevents the walk from turning back.
procedure Connect ( s1,s2 : in out Simplex );
-- DESCRIPTION :
-- Computes the intersection of the two simplices.
-- If they are neighbors to each other, then the appropriate
-- connections will be made.
procedure Flatten ( s : in out Simplex );
-- DESCRIPTION :
-- All lifting values will become zero and the inner normal changes
-- into (0,0,..,0,1).
-- SELECTORS :
function Dimension ( s : Simplex ) return natural;
-- DESCRIPTION :
-- Returns the number of points in the simplex.
function Normal ( s : Simplex ) return Vector;
-- DESCRIPTION :
-- Returns the normal to the given simplex.
function Is_Flat ( s : Simplex ) return boolean;
-- DESCRIPTION :
-- Returns true if all components of the normal equal zero,
-- except the last one, which must be equal to one.
-- Returns false otherwise.
function Vertices ( s : Simplex ) return VecVec;
-- DESCRIPTION :
-- Returns the vertices that span the simplex.
function Vertex ( s : Simplex; k : natural ) return Vector;
-- DESCRIPTION :
-- Returns the kth vector that spans the simplex.
function Is_Vertex ( s : Simplex; x : Vector ) return boolean;
-- DESCRIPTION :
-- Returns true if x is one of the vertices that spans the simplex.
function Equal ( s1,s2 : Simplex ) return boolean;
-- DESCRIPTION :
-- returns true if the representations of both simplices are the same.
function Index ( s : Simplex; x : Vector ) return natural;
-- DESCRIPTION :
-- k := Index(s,x);
-- if k = 0 then Is_Vertex(s,x) = false,
-- else Neighbor(s,k) is the neighboring simplex of s by pivoting x.
function Neighbor ( s : Simplex; k : natural ) return Simplex;
function Neighbor ( s : Simplex; k : natural; pos : Vector ) return Simplex;
-- DESCRIPTION :
-- Returns the neighbor of the kth point of the given simplex.
-- If the position vector is supplied, then it will only return
-- a non-empty simplex if that is allowed by the position.
function Position ( s : Simplex; x : Vector ) return Vector;
-- DESCRIPTION :
-- Computes the position of the given vector w.r.t. that simplex,
-- i.e., if l = Position(pt,s), then sum of l(i)*s(i) + l(l'last)*pt = 0,
-- where s(i) = ith point that spans the simplex, and the sum
-- of all entries in l equals 1.
function Is_In ( s : Simplex; x : Vector ) return boolean;
function Is_In ( s : Simplex; x,pos : Vector ) return boolean;
function Is_In_All ( s : Simplex; x : Vector ) return boolean;
function Is_In_All ( s : Simplex; x : Vector ) return Simplex;
function Is_In_All ( s : Simplex; x,pos : Vector ) return boolean;
function Is_In_All ( s : Simplex; x,pos : Vector ) return Simplex;
-- DESCRIPTION :
-- Returns true if the point x is contained in the convex hull of s.
-- The function runs more efficiently if the position vector is
-- already available, otherwise it will be computed.
-- With Is_In_All, also all neighbors of the given simplex are checked.
-- Is_In_All(s,x) returns true if x is contained in s or in one of its
-- neigbors, or in one of the neighbors of the neigbors...
-- Either the simplex which contains x or the empty simplex is returned.
generic
with procedure Process_Neighbor
( nei : in out Simplex; k : in natural;
continue : out boolean );
procedure Neighbors ( s : in out Simplex; x : in Vector );
-- DESCRIPTION :
-- Computes all neighbors (and neighbors of ...) of the simplex s,
-- that lie closest to x, i.e. with no other simplices in between.
-- This procedure implements a walk from the simplex s to
-- a given point x.
-- As the parameters are of type 'in out', simplices are
-- allowed to be updated.
-- To the user defined procedure Process_Neighbor the following
-- information is passed:
-- ON ENTRY :
-- nei a neighboring simplex close to x;
-- k index for point in nei that can be replaced by s.
-- ON RETURN :
-- nei updated simplex;
-- continue if true then more neighboring simplices may be delivered;
-- if false then the iteration will stop.
function Volume ( s : Simplex ) return natural;
-- DESCRIPTION :
-- Returns n! times the volume of the simplex.
-- DESTRUCTORS :
procedure Destroy_Neighbor ( s : in out Simplex; k : in natural );
procedure Destroy_Neighbors ( s : in out Simplex );
-- DESCRIPTION :
-- Sets the kth neighbor of the simplex to the empty simplex.
-- If k is not specified, then all neighbors will be set to empty.
procedure Clear_Neighbor ( s : in out Simplex; k : in natural );
procedure Clear_Neighbors ( s : in out Simplex );
-- DESCRIPTION :
-- Clears the kth neighbor of the simplex s.
-- If k is not specified, then all neighbors will be cleared.
procedure Clear ( s : in out Simplex );
-- DESCRIPTION :
-- Makes the allocated memory space available.
private
type Simplex_Rep ( n : natural );
type Simplex is access Simplex_Rep;
Null_Simplex : constant Simplex := null;
end Simplices;