Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Stalift/inner_normal_cones.ads, Revision 1.1
1.1 ! maekawa 1: with Standard_Integer_Vectors; use Standard_Integer_Vectors;
! 2: with Standard_Integer_Matrices; use Standard_Integer_Matrices;
! 3: with Lists_of_Integer_Vectors; use Lists_of_Integer_Vectors;
! 4: with Integer_Faces_of_Polytope; use Integer_Faces_of_Polytope;
! 5:
! 6: package Inner_Normal_Cones is
! 7:
! 8: -- DESCRIPTION :
! 9: -- This package contains facilities for dealing with inner normal cones,
! 10: -- that are cones normal to some faces of a given polytope, with apex
! 11: -- at the origin. Especially the normal cones to vertices are of great
! 12: -- interest to determine which points contribute to the mixed volume.
! 13: -- The primal representation of a normal cone consists in the generators
! 14: -- of the cone. A matrix of inequalities defines the dual representation.
! 15:
! 16: -- CONSTRUCTORS FOR PRIMAL REPRESENTATION :
! 17:
! 18: function Generators ( l : List; facets : Faces; x : Vector ) return List;
! 19:
! 20: -- DESCRIPTION :
! 21: -- Returns the generators of the polyhedral cone, which lies in the
! 22: -- dual space of the polytope spanned by l and is enclosed by the facets,
! 23: -- which all contain the vector x.
! 24: -- The list on return contains all inner normals to the facets.
! 25:
! 26: function Generators ( l : List; x : Vector ) return List;
! 27:
! 28: -- DESCRIPTION :
! 29: -- Returns the generators of the polyhedral cone to conv(l),
! 30: -- normal at the vector x.
! 31:
! 32: -- CONSTRUCTOR FOR DUAL REPRESENTATION :
! 33:
! 34: function Inner_Normal_Cone ( l : List; x : Vector ) return Matrix;
! 35:
! 36: -- DESCRIPTION :
! 37: -- Returns the inequalities that define the normal cone to the vector x,
! 38: -- normal to the polytope spanned by the points in l.
! 39: -- The range of the matrix on return is (x'range,1..Length_Of(l)-1),
! 40: -- which implies that the inequalities are stored columnwise.
! 41: -- The type of the inequalities is >= 0.
! 42:
! 43: function Included_Normal_Cone ( gx : List; x : Vector ) return Matrix;
! 44:
! 45: -- DESCRIPTION :
! 46: -- Returns the inequalities that define the inner normal cone to the
! 47: -- vector x, such that these normals are pointing in the interior of
! 48: -- the polytope spanned by l, when their basis is the point x.
! 49: -- The walls of this cone are the facets, the list gx should
! 50: -- contain all inner normal to the facets at the vertex x.
! 51:
! 52: -- RANGE FORMATS :
! 53: -- The matrix on return has ranges (x'first-1..x'last,1..Length_Of(gx)).
! 54: -- The first row of the matrix contains <gx,x>,
! 55: -- to be used in the right-hand side of the inequalities.
! 56:
! 57: -- PRIMITIVE SELECTORS :
! 58:
! 59: function Evaluate ( m : Matrix; i : integer; v : Vector ) return integer;
! 60:
! 61: -- DESCRIPTION :
! 62: -- Evaluates the vector in the ith hyperplane of the inequality matrix.
! 63:
! 64: function Satisfies ( m : Matrix; i : integer; v : Vector ) return boolean;
! 65: function Strictly_Satisfies ( m : Matrix; i : integer; v : Vector )
! 66: return boolean;
! 67:
! 68: -- DESCRIPTION :
! 69: -- Returns true if the vector v satisfies the ith inequality of the matrix.
! 70: -- With Strictly_ true is only returned if the evaluation yields a
! 71: -- positive result.
! 72:
! 73: function Satisfies ( m : Matrix; v : Vector ) return boolean;
! 74: function Strictly_Satisfies ( m : Matrix; v : Vector ) return boolean;
! 75:
! 76: -- DESCRIPTION :
! 77: -- Returns true if the vector v satisfies all inequalities defined by m.
! 78:
! 79: function Satisfies ( m : Matrix; v : List ) return boolean;
! 80: function Strictly_Satisfies ( m : Matrix; v : List ) return boolean;
! 81:
! 82: -- DESCRIPTION :
! 83: -- Returns true if all vectors in v satisfy all inequalities defined by m.
! 84:
! 85: -- SECONDARY SELECTORS :
! 86:
! 87: function Satisfy ( m : Matrix; l : List ) return List;
! 88: function Strictly_Satisfy ( m : Matrix; l : List ) return List;
! 89:
! 90: -- DESCRIPTION :
! 91: -- Returns a list of points from l that (strictly) satisfy the
! 92: -- inequalities in the matrix.
! 93:
! 94: function Contained_in_Cone ( l : List; x : Vector; v : List ) return boolean;
! 95: function Strictly_Contained_in_Cone ( l : List; x : Vector; v : List )
! 96: return boolean;
! 97:
! 98: -- DESCRIPTION :
! 99: -- Returns true when all vectors in v are contained in the normal cone
! 100: -- to the points in l, at the vector x.
! 101:
! 102: function Contained_in_Cone ( l,v : List ) return boolean;
! 103: function Strictly_Contained_in_Cone ( l,v : List ) return boolean;
! 104:
! 105: -- DESCRIPTION :
! 106: -- Returns true when there exists a normal cone to the points in l
! 107: -- that entirely contains the points in v.
! 108:
! 109: -- CONCERNING THE UNION OF CONES :
! 110:
! 111: function In_Union ( v1,v2 : Vector; k1,k2 : Matrix ) return boolean;
! 112:
! 113: -- DESCRIPTION :
! 114: -- Returns true if the convex combination of v1 and v2 is contained
! 115: -- in the union of the convex cones k1 and k2, given by their
! 116: -- inequality matrix.
! 117:
! 118: -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
! 119:
! 120: function In_Union ( v1,v2 : List; k1,k2 : Matrix ) return boolean;
! 121:
! 122: -- DESCRIPTION :
! 123: -- Returns true if every convex combination of a vector from v1
! 124: -- and a vector from v2 is contained in the union of the convex
! 125: -- cones k1 and k2, given by their inequality matrix.
! 126:
! 127: -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
! 128:
! 129: end Inner_Normal_Cones;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>