|
void | runMayanPyramid (int dim) |
| Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold MinkowskiSum of given point sets Qi[].
|
|
mprfloat | vDistance (Coord_t *acoords, int dim) |
| Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords[].
|
|
void | mn_mx_MinkowskiSum (int dim, Coord_t *minR, Coord_t *maxR) |
| LP for finding min/max coord in MinkowskiSum, given previous coors.
|
|
bool | storeMinkowskiSumPoint () |
| Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored, else flase.
|
|
Definition at line 277 of file mpr_base.cc.
◆ mayanPyramidAlg()
mayanPyramidAlg::mayanPyramidAlg |
( |
simplex * | _pLP | ) |
|
|
inline |
Definition at line 280 of file mpr_base.cc.
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
◆ ~mayanPyramidAlg()
mayanPyramidAlg::~mayanPyramidAlg |
( |
| ) |
|
|
inline |
◆ getInnerPoints()
Drive Mayan Pyramid Algorithm.
The Alg computes conv(Qi[]+shift[]).
Definition at line 891 of file mpr_base.cc.
892{
894
897
898 E=
new pointSet(
Qi[0]->
dim );
899
901
903
905
907}
void runMayanPyramid(int dim)
Recursive Mayan Pyramid algorithm for directly computing MinkowskiSum lattice points for (n+1)-fold M...
Coord_t acoords[MAXVARS+2]
#define mprSTICKYPROT(msg)
◆ 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.
997{
998 int i,
j,
k, cols, cons;
999 int la_cons_row;
1000
1002
1003
1004
1005
1006
1007 pLP->LiPM[1][1] = 0.0;
1008 for(
i=2;
i<=
n+2;
i++)
1009 {
1010 pLP->LiPM[
i][1] = 1.0;
1011 pLP->LiPM[
i][2] = 0.0;
1012 }
1013
1014 la_cons_row = 1;
1015 cols = 2;
1016 for(
i=0;
i<=
n;
i++)
1017 {
1018 la_cons_row++;
1019 for(
j=1;
j<=
Qi[
i]->num;
j++)
1020 {
1021 cols++;
1022 pLP->LiPM[1][cols] = 0.0;
1023 for(
k=2;
k<=
n+2;
k++)
1024 {
1025 if(
k != la_cons_row)
pLP->LiPM[
k][cols] = 0.0;
1026 else pLP->LiPM[
k][cols] = -1.0;
1027 }
1028 for(
k=1;
k<=
n;
k++)
1030 }
1031 }
1032
1033 for(
i= 0;
i <
dim;
i++ )
1034 {
1036 pLP->LiPM[
i+
n+3][2] = 0.0;
1037 }
1039
1040
1041 pLP->LiPM[1][2] = -1.0;
1043
1044#ifdef mprDEBUG_ALL
1045 Print(
"\nThats the matrix for minR, dim= %d, acoords= ",
dim);
1046 for(
i= 0;
i <
dim;
i++ )
1049 print_mat(
pLP->LiPM, cons+1, cols);
1050#endif
1051
1052
1056
1058
1059 if (
pLP->icase != 0 )
1060 {
1062 WerrorS(
" mn_mx_MinkowskiSum: LinearProgram: minR: infeasible");
1063 else if(
pLP->icase > 0)
1064 WerrorS(
" mn_mx_MinkowskiSum: LinearProgram: minR: unbounded");
1065 }
1066
1068
1069
1070
1071
1072
1073 pLP->LiPM[1][1] = 0.0;
1074 for(
i=2;
i<=
n+2;
i++)
1075 {
1076 pLP->LiPM[
i][1] = 1.0;
1077 pLP->LiPM[
i][2] = 0.0;
1078 }
1079 la_cons_row = 1;
1080 cols = 2;
1081 for(
i=0;
i<=
n;
i++)
1082 {
1083 la_cons_row++;
1084 for(
j=1;
j<=
Qi[
i]->num;
j++)
1085 {
1086 cols++;
1087 pLP->LiPM[1][cols] = 0.0;
1088 for(
k=2;
k<=
n+2;
k++)
1089 {
1090 if(
k != la_cons_row)
pLP->LiPM[
k][cols] = 0.0;
1091 else pLP->LiPM[
k][cols] = -1.0;
1092 }
1093 for(
k=1;
k<=
n;
k++)
1095 }
1096 }
1097
1098 for(
i= 0;
i <
dim;
i++ )
1099 {
1101 pLP->LiPM[
i+
n+3][2] = 0.0;
1102 }
1104
1105 pLP->LiPM[1][2] = 1.0;
1107
1108#ifdef mprDEBUG_ALL
1109 Print(
"\nThats the matrix for maxR, dim= %d\n",
dim);
1110 print_mat(
pLP->LiPM, cons+1, cols);
1111#endif
1112
1116
1117
1119
1120 if (
pLP->icase != 0 )
1121 {
1123 WerrorS(
" mn_mx_MinkowskiSum: LinearProgram: maxR: infeasible");
1124 else if(
pLP->icase > 0)
1125 WerrorS(
" mn_mx_MinkowskiSum: LinearProgram: maxR: unbounded");
1126 }
1127
1129
1130#ifdef mprDEBUG_ALL
1131 Print(
" Range for dim=%d: [%d,%d]\n",
dim, *minR, *maxR);
1132#endif
1133}
void WerrorS(const char *s)
◆ 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.
1163{
1166
1167
1169
1170#ifdef mprDEBUG_ALL
1173 Print(
":: [%d,%d]\n", minR, maxR);
1174#endif
1175
1176
1178 {
1179 int lastKilled = 0;
1180
1183 {
1185 lastKilled++;
1187 }
1189 return;
1190 }
1191
1192
1195 {
1197 {
1200 }
1201 else
1202 {
1203
1205
1207 {
1210 }
1211 }
1213 }
1214}
bool storeMinkowskiSumPoint()
Stores point in E->points[pt], iff v-distance != 0 Returns true iff point was stored,...
mprfloat vDistance(Coord_t *acoords, int dim)
Compute v-distance via Linear Programming Linear Program finds the v-distance of the point in accords...
void mn_mx_MinkowskiSum(int dim, Coord_t *minR, Coord_t *maxR)
LP for finding min/max coord in MinkowskiSum, given previous coors.
◆ 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.
1139{
1141
1142
1144
1145
1147 {
1149 return false;
1150 }
1151
1154
1155 return true;
1156}
◆ vDistance()
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.
910{
911 int i, ii,
j,
k, col, r;
912 int numverts, cols;
913
914 numverts = 0;
916 {
917 numverts +=
Qi[
i]->num;
918 }
919 cols = numverts + 2;
920
921
922
923
924 pLP->LiPM[1][1] = 0.0;
925 pLP->LiPM[1][2] = 1.0;
926 for(
j=3;
j<=cols;
j++)
pLP->LiPM[1][
j] = 0.0;
927
928 for(
i=0;
i <=
n;
i++ )
929 {
930 pLP->LiPM[
i+2][1] = 1.0;
931 pLP->LiPM[
i+2][2] = 0.0;
932 }
934 {
937 }
938
939 ii = -1;
940 col = 2;
941 for (
i= 0;
i <=
n;
i++ )
942 {
943 ii++;
944 for(
k= 1;
k <=
Qi[ii]->num;
k++ )
945 {
946 col++;
947 for ( r= 0; r <=
n; r++ )
948 {
949 if ( r ==
i )
pLP->LiPM[r+2][col] = -1.0;
950 else pLP->LiPM[r+2][col] = 0.0;
951 }
952 for( r= 1; r <=
dim; r++ )
954 }
955 }
956
957 if( col != cols)
958 Werror(
"mayanPyramidAlg::vDistance:"
959 "setting up matrix for udist: col %d != cols %d",col,cols);
960
964
965#ifdef mprDEBUG_ALL
966 Print(
"vDistance LP, known koords dim=%d, constr %d, cols %d, acoords= ",
969 Print(
" %d",acoords_a[
i]);
971 print_mat(
pLP->LiPM,
pLP->m+1, cols);
972#endif
973
975
976#ifdef mprDEBUG_ALL
977 PrintS(
"LP returns matrix\n");
978 print_bmat(
pLP->LiPM,
pLP->m+1, cols+1-
pLP->m, cols,
pLP->iposv);
979#endif
980
981 if(
pLP->icase != 0 )
982 {
983 WerrorS(
"mayanPyramidAlg::vDistance:");
984 if(
pLP->icase == 1 )
985 WerrorS(
" Unbounded v-distance: probably 1st v-coor=0");
986 else if(
pLP->icase == -1 )
987 WerrorS(
" Infeasible v-distance");
988 else
990 return -1.0;
991 }
992
993 return pLP->LiPM[1][1];
994}
void PrintS(const char *s)
void Werror(const char *fmt,...)
◆ acoords
◆ idelem
int mayanPyramidAlg::idelem |
|
private |
◆ pLP
◆ Qi
◆ shift
The documentation for this class was generated from the following file: