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

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;