mayanPyramidAlg Class Reference

Public Member Functions
	mayanPyramidAlg (simplex *_pLP)
	~mayanPyramidAlg ()
pointSet *	getInnerPoints (pointSet **_q_i, mprfloat _shift[])
	Drive Mayan Pyramid Algorithm. More...

Private Member Functions
void	runMayanPyramid (int dim)
	Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold MinkowskiSum of given point sets Qi[]. More...
mprfloat	vDistance (Coord_t *acoords, int dim)
	Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords[]. More...
void	mn_mx_MinkowskiSum (int dim, Coord_t *minR, Coord_t *maxR)
	LP for finding min/max coord in MinkowskiSum, given previous coors. More...
bool	storeMinkowskiSumPoint ()
	Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase. More...

Private Attributes
pointSet **	Qi
pointSet *	E
mprfloat *	shift
int	n
int	idelem
Coord_t	acoords [MAXVARS+2]
simplex *	pLP

Detailed Description

Definition at line 277 of file mpr_base.cc.

Constructor & Destructor Documentation

mayanPyramidAlg()

mayanPyramidAlg::mayanPyramidAlg ( simplex *  _pLP )

inline

Definition at line 280 of file mpr_base.cc.

: n((currRing->N)), pLP(_pLP) {}

~mayanPyramidAlg()

mayanPyramidAlg::~mayanPyramidAlg ( )

inline

Definition at line 281 of file mpr_base.cc.

{}

Member Function Documentation

getInnerPoints()

pointSet * mayanPyramidAlg::getInnerPoints	(	pointSet **	_q_i,
		mprfloat	_shift[]
	)

Drive Mayan Pyramid Algorithm.

The Alg computes conv(Qi[]+shift[]).

Definition at line 891 of file mpr_base.cc.

{
  int i;
 
  Qi= _q_i;
  shift= _shift;
 
  E= new pointSet( Qi[0]->dim ); // E has same dim as Qi[...]
 
  for ( i= 0; i < MAXVARS+2; i++ ) acoords[i]= 0;
 
  runMayanPyramid(0);
 
  mprSTICKYPROT("\n");
 
  return E;
}

mn_mx_MinkowskiSum()

void mayanPyramidAlg::mn_mx_MinkowskiSum ( int  dim, Coord_t *  minR, Coord_t *  maxR  )

private

LP for finding min/max coord in MinkowskiSum, given previous coors.

Assume MinkowskiSum in non-negative quadrants coor in [0,n); fixed coords in acoords[0..coor)

Definition at line 996 of file mpr_base.cc.

{
  int i, j, k, cols, cons;
  int la_cons_row;
 
  cons = n+dim+2;
 
  // first, compute minimum
  //
 
  // common part of the matrix
  pLP->LiPM[1][1] = 0.0;
  for( i=2; i<=n+2; i++)
  {
    pLP->LiPM[i][1] = 1.0;        // 1st col
    pLP->LiPM[i][2] = 0.0;        // 2nd col
  }
 
  la_cons_row = 1;
  cols = 2;
  for( i=0; i<=n; i++)
  {
    la_cons_row++;
    for( j=1; j<= Qi[i]->num; j++)
    {
      cols++;
      pLP->LiPM[1][cols] = 0.0;        // set 1st row 0
      for( k=2; k<=n+2; k++)
      {  // lambdas sum up to 1
        if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
        else pLP->LiPM[k][cols] = -1.0;
      }
      for( k=1; k<=n; k++)
        pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
    } // j
  } // i
 
  for( i= 0; i < dim; i++ )
  {                // fixed coords
    pLP->LiPM[i+n+3][1] = acoords[i];
    pLP->LiPM[i+n+3][2] = 0.0;
  }
  pLP->LiPM[dim+n+3][1] = 0.0;
 
 
  pLP->LiPM[1][2] = -1.0;                        // minimize
  pLP->LiPM[dim+n+3][2] = 1.0;
 
#ifdef mprDEBUG_ALL
  Print("\nThats the matrix for minR, dim= %d, acoords= ",dim);
  for( i= 0; i < dim; i++ )
    Print(" %d",acoords[i]);
  PrintLn();
  print_mat( pLP->LiPM, cons+1, cols);
#endif
 
  // simplx finds MIN for obj.fnc, puts it in [1,1]
  pLP->m= cons;
  pLP->n= cols-1;
  pLP->m3= cons;
 
  pLP->compute();
 
  if ( pLP->icase != 0 )
  { // check for errors
    if( pLP->icase < 0)
      WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: infeasible");
    else if( pLP->icase > 0)
      WerrorS(" mn_mx_MinkowskiSum: LinearProgram: minR: unbounded");
  }
 
  *minR = (Coord_t)( -pLP->LiPM[1][1] + 1.0 - SIMPLEX_EPS );
 
  // now compute maximum
  //
 
  // common part of the matrix again
  pLP->LiPM[1][1] = 0.0;
  for( i=2; i<=n+2; i++)
  {
    pLP->LiPM[i][1] = 1.0;
    pLP->LiPM[i][2] = 0.0;
  }
  la_cons_row = 1;
  cols = 2;
  for( i=0; i<=n; i++)
  {
    la_cons_row++;
    for( j=1; j<=Qi[i]->num; j++)
    {
      cols++;
      pLP->LiPM[1][cols] = 0.0;
      for( k=2; k<=n+2; k++)
      {
        if( k != la_cons_row) pLP->LiPM[k][cols] = 0.0;
        else pLP->LiPM[k][cols] = -1.0;
      }
      for( k=1; k<=n; k++)
        pLP->LiPM[k+n+2][cols] = -(mprfloat)((*Qi[i])[j]->point[k]);
    } // j
  }  // i
 
  for( i= 0; i < dim; i++ )
  {                // fixed coords
    pLP->LiPM[i+n+3][1] = acoords[i];
    pLP->LiPM[i+n+3][2] = 0.0;
  }
  pLP->LiPM[dim+n+3][1] = 0.0;
 
  pLP->LiPM[1][2] = 1.0;                      // maximize
  pLP->LiPM[dim+n+3][2] = 1.0;                // var = sum of pnt coords
 
#ifdef mprDEBUG_ALL
  Print("\nThats the matrix for maxR, dim= %d\n",dim);
  print_mat( pLP->LiPM, cons+1, cols);
#endif
 
  pLP->m= cons;
  pLP->n= cols-1;
  pLP->m3= cons;
 
  // simplx finds MAX for obj.fnc, puts it in [1,1]
  pLP->compute();
 
  if ( pLP->icase != 0 )
  {
    if( pLP->icase < 0)
      WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: infeasible");
    else if( pLP->icase > 0)
      WerrorS(" mn_mx_MinkowskiSum: LinearProgram: maxR: unbounded");
  }
 
  *maxR = (Coord_t)( pLP->LiPM[1][1] + SIMPLEX_EPS );
 
#ifdef mprDEBUG_ALL
  Print("  Range for dim=%d: [%d,%d]\n", dim, *minR, *maxR);
#endif
}

runMayanPyramid()

void mayanPyramidAlg::runMayanPyramid ( int  dim )

private

Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold MinkowskiSum of given point sets Qi[].

Recursively for range of dim: dim in [0..n); acoords[0..var) fixed. Stores only MinkowskiSum points of udist > 0: done by storeMinkowskiSumPoints.

Definition at line 1162 of file mpr_base.cc.

{
  Coord_t minR, maxR;
  mprfloat dist;
 
  // step 3
  mn_mx_MinkowskiSum( dim, &minR, &maxR );
 
#ifdef mprDEBUG_ALL
  int i;
  for( i=0; i <= dim; i++) Print("acoords[%d]=%d ",i,(int)acoords[i]);
  Print(":: [%d,%d]\n", minR, maxR);
#endif
 
  // step 5 -> terminate
  if( dim == n-1 )
  {
    int lastKilled = 0;
    // insert points
    acoords[dim] = minR;
    while( acoords[dim] <= maxR )
    {
      if( !storeMinkowskiSumPoint() )
        lastKilled++;
      acoords[dim]++;
    }
    mprSTICKYPROT(ST_SPARSE_MPEND);
    return;
  }
 
  // step 4 -> recurse at step 3
  acoords[dim] = minR;
  while ( acoords[dim] <= maxR )
  {
    if ( (acoords[dim] > minR) && (acoords[dim] <= maxR) )
    {     // acoords[dim] >= minR  ??
      mprSTICKYPROT(ST_SPARSE_MREC1);
      runMayanPyramid( dim + 1 );         // recurse with higher dimension
    }
    else
    {
      // get v-distance of pt
      dist= vDistance( &(acoords[0]), dim + 1 );// dim+1 == known coordinates
 
      if( dist >= SIMPLEX_EPS )
      {
        mprSTICKYPROT(ST_SPARSE_MREC2);
        runMayanPyramid( dim + 1 );       // recurse with higher dimension
      }
    }
    acoords[dim]++;
  } // while
}

storeMinkowskiSumPoint()

bool mayanPyramidAlg::storeMinkowskiSumPoint ( )

private

Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.

Definition at line 1138 of file mpr_base.cc.

{
  mprfloat dist;
 
  // determine v-distance of point pt
  dist= vDistance( &(acoords[0]), n );
 
  // store only points with v-distance > minVdist
  if( dist <= MINVDIST + SIMPLEX_EPS )
  {
    mprSTICKYPROT(ST_SPARSE_VREJ);
    return false;
  }
 
  E->addPoint( &(acoords[0]) );
  mprSTICKYPROT(ST_SPARSE_VADD);
 
  return true;
}

vDistance()

mprfloat mayanPyramidAlg::vDistance ( Coord_t *  acoords, int  dim  )

private

Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords[].

The v-distance is the distance along the direction v to boundary of Minkowski Sum of Qi (here vector v is represented by shift[]). Returns the v-distance or -1.0 if an error occurred.

Definition at line 909 of file mpr_base.cc.

{
  int i, ii, j, k, col, r;
  int numverts, cols;
 
  numverts = 0;
  for( i=0; i<=n; i++)
  {
    numverts += Qi[i]->num;
  }
  cols = numverts + 2;
 
  //if( dim < 1 || dim > n )
  //  WerrorS("mayanPyramidAlg::vDistance: Known coords dim off range");
 
  pLP->LiPM[1][1] = 0.0;
  pLP->LiPM[1][2] = 1.0;        // maximize
  for( j=3; j<=cols; j++) pLP->LiPM[1][j] = 0.0;
 
  for( i=0; i <= n; i++ )
  {
    pLP->LiPM[i+2][1] = 1.0;
    pLP->LiPM[i+2][2] = 0.0;
  }
  for( i=1; i<=dim; i++)
  {
    pLP->LiPM[n+2+i][1] = (mprfloat)(acoords_a[i-1]);
    pLP->LiPM[n+2+i][2] = -shift[i];
  }
 
  ii = -1;
  col = 2;
  for ( i= 0; i <= n; i++ )
  {
    ii++;
    for( k= 1; k <= Qi[ii]->num; k++ )
    {
      col++;
      for ( r= 0; r <= n; r++ )
      {
        if ( r == i ) pLP->LiPM[r+2][col] = -1.0;
        else pLP->LiPM[r+2][col] = 0.0;
      }
      for( r= 1; r <= dim; r++ )
        pLP->LiPM[r+n+2][col] = -(mprfloat)((*Qi[ii])[k]->point[r]);
    }
  }
 
  if( col != cols)
    Werror("mayanPyramidAlg::vDistance:"
           "setting up matrix for udist: col %d != cols %d",col,cols);
 
  pLP->m = n+dim+1;
  pLP->m3= pLP->m;
  pLP->n=cols-1;
 
#ifdef mprDEBUG_ALL
  Print("vDistance LP, known koords dim=%d, constr %d, cols %d, acoords= ",
        dim,pLP->m,cols);
  for( i= 0; i < dim; i++ )
    Print(" %d",acoords_a[i]);
  PrintLn();
  print_mat( pLP->LiPM, pLP->m+1, cols);
#endif
 
  pLP->compute();
 
#ifdef mprDEBUG_ALL
  PrintS("LP returns matrix\n");
  print_bmat( pLP->LiPM, pLP->m+1, cols+1-pLP->m, cols, pLP->iposv);
#endif
 
  if( pLP->icase != 0 )
  {  // check for errors
    WerrorS("mayanPyramidAlg::vDistance:");
    if( pLP->icase == 1 )
      WerrorS(" Unbounded v-distance: probably 1st v-coor=0");
    else if( pLP->icase == -1 )
      WerrorS(" Infeasible v-distance");
    else
      WerrorS(" Unknown error");
    return -1.0;
  }
 
  return pLP->LiPM[1][1];
}

Field Documentation

acoords

Coord_t mayanPyramidAlg::acoords[MAXVARS+2]

private

Definition at line 323 of file mpr_base.cc.

E

pointSet* mayanPyramidAlg::E

private

Definition at line 318 of file mpr_base.cc.

idelem

int mayanPyramidAlg::idelem

private

Definition at line 321 of file mpr_base.cc.

n

int mayanPyramidAlg::n

private

Definition at line 321 of file mpr_base.cc.

pLP

simplex* mayanPyramidAlg::pLP

private

Definition at line 325 of file mpr_base.cc.

Qi

pointSet** mayanPyramidAlg::Qi

private

Definition at line 317 of file mpr_base.cc.

shift

mprfloat* mayanPyramidAlg::shift

private

Definition at line 319 of file mpr_base.cc.

---

The documentation for this class was generated from the following file:

• kernel/numeric/mpr_base.cc