Return to vertices.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Root_Counts / Implift

Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Implift/vertices.ads, Revision 1.1

1.1     ! maekawa     1: with Standard_Integer_Vectors;           use Standard_Integer_Vectors;
        !             2: with Standard_Floating_Vectors;
        !             3: with Lists_of_Integer_Vectors;           use Lists_of_Integer_Vectors;
        !             4:
        !             5: package Vertices is
        !             6:
        !             7: -- DESCRIPTION :
        !             8: --   This function offers some functions for computing the
        !             9: --   vertices that span the polytope, given its set of points.
        !            10: --   Based on the functions in this package it is possible to
        !            11: --   determine the dimension of conv(l), without the actual computation
        !            12: --   of the convex hull.
        !            13:
        !            14:   function Is_In_Hull ( point : Standard_Integer_Vectors.Vector;
        !            15:                         l : List ) return boolean;
        !            16:   function Is_In_Hull ( point : Standard_Floating_Vectors.Vector;
        !            17:                         l : List ) return boolean;
        !            18:
        !            19:   -- DESCRIPTION :
        !            20:   --   This function determines whether the point belongs to convex
        !            21:   --   hull of the points in the given list.
        !            22:
        !            23:   function Vertex_Points ( l : List ) return List;
        !            24:
        !            25:   -- DESCRIPTION :
        !            26:   --   The vertex points of conv(l) are returned.
        !            27:
        !            28:   function Extremal_Points ( l : List; v : Link_to_Vector ) return List;
        !            29:
        !            30:   -- DESCRIPTION :
        !            31:   --   Returns the vertex points of the list l w.r.t. the direction v and -v.
        !            32:
        !            33:   function Extremal_Points ( k,n : natural; exl,l : List ) return List;
        !            34:   function Max_Extremal_Points ( k,n : natural; exl,l : List ) return List;
        !            35:
        !            36:   -- DESCRIPTION :
        !            37:   --   There are already k linearly independent vertex points found,
        !            38:   --   given in exl.  This routine tries to take one more linearly
        !            39:   --   independent vertex point out of the list l.
        !            40:   --   The first function stops when a degeneracy is discovered,
        !            41:   --   while the second one still proceeds and returns one point
        !            42:   --   more, when possible.
        !            43:
        !            44:   function Extremal_Points ( n : natural; l : List ) return List;
        !            45:
        !            46:   -- DESCRIPTION :
        !            47:   --   Searches in the list l for linearly independent vertex points.
        !            48:   --   If dim(conv(l)) = n then n+1 points will be returned,
        !            49:   --   otherwise the number of points in the resulting list will be
        !            50:   --   less but not necessarily equal to dim(conv(l))+1.
        !            51:   --   The advantage of this routine lies in the fact that a degeneracy,
        !            52:   --   i.e., dim(conv(l)) < n, is detected as soon as possible.
        !            53:
        !            54:   function Max_Extremal_Points ( n : natural; l : list ) return List;
        !            55:
        !            56:   -- DESCRIPTION :
        !            57:   --   Does the same as the function above, except for the fact that
        !            58:   --   the number of points in the resulting lists equals dim(conv(l))+1.
        !            59:   --   The points in the resulting list can be regarded as a basis,
        !            60:   --   i.e., origin and as many linearly independent points as dim(conv(l)),
        !            61:   --   for the points in l.
        !            62:
        !            63: end Vertices;