//*************************************************************************** //* Program: mcpic (POTM 'GLOSSY') Version 3.24 (24.09.2005) * //* Copyright (C) 2005 by Stefan Förster * //* stefan.foerster@mnet-online.de * //* * //* This program is free software; you can redistribute it and/or modify * //* it under the terms of the GNU General Public License as published by * //* the Free Software Foundation; either version 2 of the License, or * //* (at your option) any later version. * //* * //* This program is distributed in the hope that it will be useful, * //* but WITHOUT ANY WARRANTY; without even the implied warranty of * //* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * //* GNU General Public License for more details. * //* * //* You should have received a copy of the GNU General Public License * //* along with this program; if not, write to the * //* Free Software Foundation, Inc., * //* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * //*************************************************************************** #define DEBUG 0 #define __USE_ISOC99 1 #include #include #include #include #include #include #include #include #include #include #ifdef __linux__ #include #include #include #endif // constants and macros #define MAXTHR 4 // max. number of threads #define THRTHRESHOLD 10 // only multi-thread, if the number of pictures exceeds this value #define NUMTHRLIMIT 8 // limit of pictures per thread (except perhaps the last one) #define STACKSIZE 524288 // 512kB #define WEIGHT1 0.5 // weight for the picture splitting function #define WEIGHT2 (1.0 - WEIGHT1) // 1-WEIGHT1 #define MINPICS 2 // min. number of pictures #define MAXPICS 26 // max. number of pictures #define MAXPICS2 32 // power of 2 to optimize access to multidim. arrays #define ARLIMIT 0.02 // max. deviation of aspect ratio // !!! if you change ARLIMIT, you also have to change BDRY_AR, see below #define MAXARLIMIT 10.0 // max. aspect ratio #define PAGEAREA(hp,vp) ((hp)*(vp)) // area of paper (hp x vp) #define MINAREA(pagearea) ((pagearea)/100) // min. area of picture in relation to 'pagearea' #define MAXHSIZE 5000 // max. horiz. size of picture #define MAXVSIZE MAXHSIZE // max. vertical size of picture #define MINPAGEDIM 500 // min. page dimension #define MAXPAGEDIM 5000 // max. page dimension // For aspect ratios between 1 and BDRY_AR pic_limaratio[0] has to be calculated differently #define BDRY_AR 1.00019998 // = sqrt(1+ARLIMIT^2). #define MINLIMARATIO(a) (((a) >= BDRY_AR) ? ((a)-ARLIMIT) : (1.0/((a)+ARLIMIT))) #define RDEPS 1e-7 // epsilon for rounding purposes (ceil() and floor()) #define BRUTEFORCE 7 // if # of pics <= BRUTEFORCE, then we don't cut the search tree #define MAXITER 15 // max. number of iterations for binary search #define EPS 1e-7 // stop binary search, if upper-lower < EPS #define NUMSTEPS 20 // number of steps for SearchInitialSolution-loop #define WEMIN 0.50 // min. value of 'Weight1' #define WEMAX 1.00 // max. value of 'Weight1' #define WERANGE (WEMAX-WEMIN) #define ARMIN (-ARLIMIT) // min. value of 'ARDelta' #define ARMAX ARLIMIT // max. value of 'ARDelta' #define ARRANGE (ARMAX-ARMIN) #define ARWEQ 5.0 // number of ARDelta's : number of Weight1's #define NUMGRIDPTS 6 // # of grid points for the search in Searchsolutions() in brute force mode #define GRIDSHRINK 0.07 // shrink factor for grid if improved solution was found ( 0 < GRIDSHRINK < 0.5) #define MAXLINEITER 3 // max. number of iterations with unchanged tiebraker in OptimizeTiebraker #define MTPOSTPROTIME 0.10 // max. time allowed for post processing in the multi-threaded case #if DEBUG // max. time #define MAXTIME ( INT_MAX / CLOCKS_PER_SEC ) #else #define MAXTIME 59.5 #endif #define MTMAXTIME ( MAXTIME - MTPOSTPROTIME ) #define MIN(x,y) ((x) < (y) ? (x) : (y)) #define MAX(x,y) ((x) > (y) ? (x) : (y)) // data types enum boolean {FALSE=0, TRUE=1}; typedef struct picture { // picture char pic_name; // name of the picture: A..Z char pic_pad; // padding... int pic_hsize; // horizontal size ( >= pic_vsize ) int pic_vsize; // vertical size double pic_aratio; // aspect ratio int pic_area; // area double pic_hvdratio[3]; // hvdratio[0] = pic_aratio - ARDelta; // hvdratio[1] = (pic_hsize/pic_vsize + ARDelta)^(-1); (remember: pic_hsize >= pic_vsize) // hvdratio[2] = pic_aratio + ARDelta; double pic_limaratio[2]; // limaratio[0] = MINLIMARATIO(pic_aratio) // limaratio[1] = pic_aratio + ARLIMIT int pic_minhsize; // min. horizontal size ( >= pic_minvsize ) int pic_minvsize; // min. vertical size int pic_minarea; // = pic_minhsize * pic_minvsize double pic_minhsizedelta;// pic_minhsize * sqrt((pic_aratio+ARLIMIT)/pic_aratio) enum boolean pic_set; // TRUE, if picture set in recursion, else FALSE enum boolean pic_dupl; // TRUE, if this picture has the same aspect ratio than the picture before in the array (sorted by aspect ratio) } pic, *picptr; typedef struct _solpic { // picture and its position of a solution int solpic_index; // index of picture in Pics[] char solpic_name; // name of the picture: A..Z char solpic_pad; // padding... int solpic_hsize; // horizontal size int solpic_vsize; // vertical size int solpic_hpos; // horizontal position of lower left corner int solpic_vpos; // vertical position of lower left corner } solpic, *solpicptr; typedef struct so { // solution: array of pictures and positions enum boolean so_found; // TRUE, if a valid soultion found, else FALSE solpic so_pics[MAXPICS]; // the pictures int so_white; // number of pixels not covered -> to miminize int so_tiebraker; // tiebraker = difference between biggest and smallest picture -> to minimize int so_biggest; // biggest picture int so_smallest; // smallest picture } solution, *solutionptr; typedef struct _flpic { // stretched/shrunk picture int flpic_index; // index of picture in Pics[] char flpic_name; // name of picture = Pics[flpic_index].pic_name char flpic_pad; // padding... double flpic_flhsize; // horizontal size (floating point version) double flpic_flvsize; // vertical size (floating point version) double flpic_flhpos; // horizontal position of left lower corner (floating point version) double flpic_flvpos; // vertical position of left lower corner (floating point version) double flpic_flaratio; // aspect ratio of floating point version of the picture double flpic_flarea; // area of picture (floating point version) double flpic_flminarea; // area of smallest picture up to recursion step n double flpic_flmaxarea; // area of biggest picture upto recursion step n double flpic_tothsize; // total horizontal size of all pictures incl. this one double flpic_totvsize; // total vertical size of all pictures incl. this one double flpic_totaratio; // aspect ratio of total picture incl. this one (flpic_tothsize/flpic_totvsize) int flpic_hsize; // horizontal size (rounded) int flpic_vsize; // vertical size (rounded) int flpic_hpos; // horizontal position of left lower corner (rounded) int flpic_vpos; // vertical position of left lower corner (rounded) int flpic_hpos2; // horizontal position of right upper corner (rounded) int flpic_vpos2; // vertical position of rigth upper corner (rounded) double flpic_aratio; // aspect ratio of rounded integer version of the picture int flpic_area; // area of picture (rounded) } flpic, *flpicptr; typedef struct auo_pair { // a pair of double's (aspect ratios) double au; double ao; } auo, *auoptr; typedef struct dhv_pair { // a pair of double's (horiz. and vert. size) double dh; double dv; } dhv, *dhvptr; struct twopic { // 2 pictures in 1 rectangle: h1=hsize of pic #1, v=vsize of both pictures double tp_h1; // hsize of pic #1 (normalized: h1+h2=1) double tp_v; // vsize of both pics }; typedef struct _twopic4 { // = struct twopic for all 4 combinations of rotations struct twopic tp4_hv[4]; // 0=(F,F), 1=(T,F), 2=(F,T), 3=(T,T) (F=FALSE=no rot., T=TRUE=rotation) double tp4_minv; // minimum of all 4 vsizes } twopic4, *twopic4ptr; typedef struct _alt { double alt_flhsize[2]; // horizontal size of pic #1 and (for 2-pic-alternative) pic #2 double alt_flvsize[2]; // vertical size of pic #1 and (for 2-pic-alternative) pic #2 double alt_flarea[2]; // area of pic #1 and (for 2-pic-alternative) pic #2 double alt_flaratio[2]; // aspect ratio of pic #1 and (for 2-pic-alternative) pic #2 double alt_totaratio; // new total aspect ratio with this alternative double alt_delta; // wheighted mean of the deviations of total aspect ratios and tiebrakers } alt, *altptr; enum direction { SW=0, SE=1, NE=2, NW=3 }; typedef struct _corner { // a corner of a picture int co_hpos; // horizontal position int co_vpos; // vertical position enum direction co_dir; // direction of corner flpicptr co_flp; // pointer to picture } corner, *cornerptr; typedef struct _liflpic { // linked list of pictures flpicptr lifl_flp; // pointwer to picture struct _liflpic *lifl_next; // next list entry } liflpic, *liflpicptr; enum leftright { LEFT=0, RIGHT=1 }; typedef struct _line { // line (may be vertical or horizontal) int line_pos; // position of line (vpos if horizontal, hpos iv vertical line) liflpicptr line_lr[2]; // pictures 'left' and 'right' of the line } line, *lineptr; enum horizvert { HORIZ=0, VERT=1 }; // variables enum boolean Forked = FALSE; // normally we don't fork, but if Num_tot exceeds certain thresholds we create up to MAXTHR-1 childs ! int NumThreads = 1; // number of threads [1..MAXTHR] pid_t Pid[MAXTHR]; // process ID's of child processes short McPicArg[MAXTHR] = { 0 }; // Arguments for calls to McPic with clone() clock_t MaxClockTicks_tot; // max clock ticks, then we quit clock_t MTMaxClockTicks_tot; // max clock tiocks when multithreading clock_t MaxClockTicks[MAXTHR]; // the same per thread clock_t StartClockTicks_tot; // return value of clock() at the beginning of the program clock_t StartClockTicks[MAXTHR]; // the same per thread enum boolean Testing = FALSE; int Num_tot = 0; // number of pictures int Num[MAXTHR] = { 0 }; // number of pictures per thread int HSize_tot = 0; // horizontal size of paper int HSize[MAXTHR] = { 0 }; // horizontal size of paper per thread int VSize_tot = 0; // vertical size of paper int VSize[MAXTHR] = { 0 }; // horizontal size of paper per thread int HPos[MAXTHR] = { 0 }; // horizontal position of left lower corner of sub-page in relation to orig. paper int VPos[MAXTHR] = { 0 }; // vertical position of left lower corner of sub-page in relation to orig. paper int SumPicMinArea[MAXTHR] = { 0 }; // sum of the minimum picture areas per sub-page (i.e. per thread) int SumPicMinArea_tot = 0; // sum of SumPicMinArea[] double SumAspectRatio[MAXTHR] = { 0.0 }; // sum of the aspect ratios per sub-page (i.e. per thread) double SumAspectRatio_tot = 0.0; // sum of SumAspectRatio[] int PageArea_tot = 0; // area of paper int PageArea[MAXTHR] = { 0 }; // areas of sub-papers (sum = PageArea_tot) int MinPictureArea = 0; // min. picture area double MinPictureAreaFloat = 0.0; // min. picture area (floating point version) double PageAspectRatio_tot = 0.0; // aspect ratio of page = HSize_tot/VSize_tot double PageAspectRatio[MAXTHR] = { 0.0 }; // aspect ratio of page = HSize[i]/VSize[i] of thread i int NumCo[MAXTHR]; // number of corners except page corners per thread int MaxHPos[MAXTHR]; // HSize[i] - 1 int MaxVPos[MAXTHR]; // VSize[i] - 1 pic Pics_tot[MAXPICS] = { { 0, 0, 0, 0.0, 0, FALSE } }; // array of all pictures pic Pics[MAXTHR][MAXPICS] = { { { 0, 0, 0, 0.0, 0, FALSE } } }; // array of pictures per thread solution Solution[MAXTHR] = { { FALSE, {{ '\0', '\0', 0, 0, 0 }}, 0, 0, 0, 0 } }; // partial solution per thread flpic Rec[MAXTHR][MAXPICS]; // pictures used in recursion per thread flpic RecCopy[MAXTHR][MAXPICS]; // copy of Rec[i][] of thread i corner Corners[MAXTHR][2*(MAXPICS-1)]; // 50% of the corners of the pictures minus 2 corners of the page per thread double Delta[MAXPICS] = { ARLIMIT, ARLIMIT, ARLIMIT, 0.0185, 0.0175, 0.0155, 0.0130, 0.0075 , 0.0000, -0.0100, -0.0100, -0.0100, -0.0100, -0.0100, -0.0110, -0.0110, -0.0110, -0.0110, -0.0110, -0.0120, -0.0120, -0.0120, -0.0130, -0.0130, -0.0130, -0.0140 }; double ARDelta[MAXTHR]; // = Delta[Num[thr]-1] = deviation of aspect ratio in search algorithm double Weight1[MAXTHR] = { 0.6 }; // for WeightedDelta(): factor for deviation of aspect ratios per thread double Weight2[MAXTHR] = { 0.4 }; // = 1.0 - Weight1; for WeightedDelta(): factor for deviation of tiebrakers per thread twopic4 TwoPic[MAXTHR][MAXPICS2][MAXPICS2]; // all 2-pic-combinations per thread // max. recursion depth using all possible positions/rotations (depending on # of pictures) int MBF[MAXPICS+1] = { 1, 2, 3, 4, 5, 6, 7, 7, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 1, 1 }; int MaxBruteForce[MAXTHR]; line Lines[MAXTHR][2][MAXPICS]; // horiz. and vert. lines, needed by OptimizeTiebraker per thread liflpic FlpicHeap[MAXTHR][4*MAXPICS]; // heap for linked lists needed in 'line', to avoid slow dynamical memory allocation and deallocation per thread // prototypes static void CalcHVDRatios(short thr); static void CalcMoveLine(short thr, lineptr lptr, enum horizvert hv, int fmin, int fmax, int *moveleft, int *moveright); static void CalcStretchShrinkPicBdry(short thr, flpicptr flp, enum horizvert hv, int fmin, int fmax, int *deltamin, int *deltamax); static int CheckSolution(short thr); int cor_h_compare(const cornerptr a, const cornerptr b); int cor_v_compare(const cornerptr a, const cornerptr b); static double EstimateScaling(short thr, flpicptr flp, int n, double *tiebraker); static void FindCorners(short thr, enum horizvert hv); static int FindLines(short thr, enum horizvert hv); static void InitPicture(picptr p); static void InitTwoPic(short thr); #ifdef __linux__ static void JoinSolutions(void); #endif static void McPic(short *thr); int main(int argc, char **argv); // static double max2(double x1, double x2); static double min2(double x1, double x2); static double max3(double x1, double x2, double x3); static double min3(double x1, double x2, double x3); static void MinFit(short thr); static void MinPicture(picptr p); static void MoveLine(lineptr lptr, enum horizvert hv, int move); static enum boolean Opti2Pics(double h, double v, double minarea, auoptr a, dhvptr hv); static void OptimizeTiebraker(short thr, int *biggest, int *smallest, enum boolean endgame); int pic_compare(const picptr a, const picptr b); static void PrintSolution(short thr); static enum boolean ReadInputFile(char *file); // static void ReadValue(const char *scanfstr, void *x, const char *printfstr, ...); static void Search2PictureSolution(short thr); static void SearchSolution(short thr, int n); static void SearchSolutions(short thr); int sol_compare(const solpicptr a, const solpicptr b); static void SortPics(picptr pptr, int n); static void SplitPage(int thr, int numparts, int numpics, int hpos, int vpos, int hsize, int vsize); #ifdef __linux__ int StartThread(void (*fn)(void *), void *data); #endif static void SearchInitialSolution(short thr, enum boolean rowbyrow); static int SimpleFit(short thr, double q, enum boolean rowbyrow); static void SortSolution(short thr); static void StretchShrinkPic(flpicptr flp, enum horizvert hv, enum leftright lr, int delta); static double WeightedDelta(short thr, flpicptr pred, altptr aptr, int mode); //********************************************************************* // int main(int argc, char **argv); // // POTM GLOSSY // Program "mcpic" // Input: paper and picture sizes // Output: pictures sizes and placements //********************************************************************* int main(int argc, char **argv) { short thr, q; // Laufvariablen int pos; // Laufvariablen pid_t pid; // PID int set[MAXTHR] = { 0 }; // number of pictures assigned to each sub-page yet int num_resid; // residual number of pictures (total number of pictures of threads thr, thr+1, ..., NumThreads-1) // set the max. clock ticks we can use StartClockTicks_tot = clock(); MaxClockTicks_tot = StartClockTicks_tot + (clock_t)(MAXTIME * CLOCKS_PER_SEC); MTMaxClockTicks_tot = StartClockTicks_tot + (clock_t)(MTMAXTIME * CLOCKS_PER_SEC); // simple parsing of arguments if(argc < 2) { puts("too few arguments"); return EXIT_FAILURE; } // testing mode ? if more than one argument, yes (to keep it simple) if(argc > 2) Testing = TRUE; // read input file if(!ReadInputFile(argv[1])) { printf("error reading file \"%s\" or invalid file format\n", argv[1]); return EXIT_FAILURE; } #ifdef __linux__ // multi-thread only if it's a Linux box (we use the clone() function) if(Num_tot > THRTHRESHOLD) { // prepare and create child processes Forked = TRUE; if((NumThreads = (int)ceil((double)Num_tot / NUMTHRLIMIT)) > MAXTHR) NumThreads = MAXTHR; // sort the pictures ascending by aspect ratios SortPics(Pics_tot, Num_tot); // calculate the number of pictures per thread and the parameters NumCo[] and MaxBruteForce[] for(thr=0, num_resid=Num_tot; thr= Num[thr]) { // look for the next sub-page not yet completed if(++thr == NumThreads) thr = 0; } Pics[thr][set[thr]++] = Pics_tot[pos]; SumPicMinArea[thr] += Pics_tot[pos].pic_minarea; SumAspectRatio[thr] += Pics_tot[pos].pic_aratio; if(++thr == NumThreads) thr = 0; } for(thr=0; thr= vsize, VERT otherwise int hvmax; // max{hsize, vsize} double factor; int length; // length of sub-page (depending on 'hv', 'numpics' and 'numparts') if(numparts > 1) { // then split the page hv = hsize >= vsize ? HORIZ : VERT; hvmax = MAX(hsize, vsize); HPos[thr] = hpos; VPos[thr] = vpos; // calculate length of sub-page to split from the rest depending on the minimum picture sizes // and the aspect ratios factor = WEIGHT1 * ( ((double)SumPicMinArea[thr]) / ((double)SumPicMinArea_tot) ) + WEIGHT2 * ( SumAspectRatio[thr] / SumAspectRatio_tot ); length = (int)floor( hvmax * factor ); SumPicMinArea_tot -= SumPicMinArea[thr]; SumAspectRatio_tot -= SumAspectRatio[thr]; if(hv == HORIZ) { // split a left sub-page with full height HSize[thr] = length; VSize[thr] = vsize; MaxHPos[thr] = HSize[thr] - 1; MaxVPos[thr] = VSize[thr] - 1; PageArea[thr] = HSize[thr] * VSize[thr]; PageAspectRatio[thr] = ((double)HSize[thr]) / ((double)VSize[thr]); SplitPage(thr+1, numparts-1, numpics-Num[thr], hpos+length, vpos, hsize-length, vsize); } else { // hv == VERT HSize[thr] = hsize; VSize[thr] = length; MaxHPos[thr] = HSize[thr] - 1; MaxVPos[thr] = VSize[thr] - 1; PageArea[thr] = HSize[thr] * VSize[thr]; PageAspectRatio[thr] = ((double)HSize[thr]) / ((double)VSize[thr]); SplitPage(thr+1, numparts-1, numpics-Num[thr], hpos, vpos+length, hsize, vsize-length); } } else { // numparts == 1 -> don't split anymore HPos[thr] = hpos; VPos[thr] = vpos; HSize[thr] = hsize; VSize[thr] = vsize; MaxHPos[thr] = HSize[thr] - 1; MaxVPos[thr] = VSize[thr] - 1; PageArea[thr] = HSize[thr] * VSize[thr]; PageAspectRatio[thr] = ((double)HSize[thr]) / ((double)VSize[thr]); } } #ifdef __linux__ //========================================================================= // int StartThread(void (*fn)(void *), void *data); // // Function originally by Linus Torvalds // http://www.ussg.iu.edu/hypermail/linux/kernel/9509/0287.html // except that it uses the clone() function instead of the x86 asm system // call. // // "This is a "kind-of" thr_create() as in pthreads, but not really. // It needs some fleshing out to work like pthreads thr_create()." //========================================================================= int StartThread(void (*fn)(void *), void *data) { void **newstack; //allocate new stack for subthread if(!(newstack = (void **) malloc(STACKSIZE))) return -1; // Set up the stack for child function, put the (void *) argument on the stack. newstack = (void **) (STACKSIZE + (char *) newstack); *--newstack = data; return clone((int (*)(void *))fn, newstack, (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | SIGCHLD), data); } #endif //========================================================================= // static void McPic(short *thr); // // All the calculations needed to find a solution. 'thr' is the thread // number. When the max. time for this thread is exceeded, PrintSolution() // is called by one of the functions called by McPic. //========================================================================= static void McPic(short *thr) { short t = *thr; if(t) StartClockTicks[t] = clock(); // set start of clock, if we are a child // sort pics by size (descending) and identify duplicate aspect ratios SortPics(&Pics[t][0], Num[t]); // try a first solution with minimal picture sizes MinFit(t); // try to find a inital solution in case the main algorithm fails SearchInitialSolution(t, TRUE); if(PageAspectRatio[t] != 1.0) SearchInitialSolution(t, FALSE); // let's find further solutions using first the default aspect ratio delta... // and, if there is still time, other aspect ratios and weights depending on // the estimated time needed for SearchSolution(0). SearchSolutions(t); // just in case we arrive here (shouldn't be possible) PrintSolution(t); } //========================================================================= // static enum boolean ReadInputFile(char *file); // // ... reads the input file. Format: // PAGE hsize vsize // A hsize vsize // ... //========================================================================= static enum boolean ReadInputFile(char *file) { FILE *fptr = NULL; #define MAXLLEN 256 char line[MAXLLEN] = ""; // we don't expect to get longer lines... int tokens; if(!(fptr=fopen(file,"r"))) return FALSE; while(!feof(fptr) && fgets(line, MAXLLEN, fptr)) { if(ferror(fptr)) goto error; if(strncasecmp("PAGE", line, 4)==0) { // "PAGE hsize vsize" found if(sscanf(line+4, "%d %d", &HSize_tot, &VSize_tot)<2) goto error; if((PageArea_tot = PAGEAREA(HSize_tot, VSize_tot)) == 0) goto error; MinPictureArea = MINAREA(PageArea_tot); MinPictureAreaFloat = MINAREA((double)PageArea_tot); PageAspectRatio_tot = ((double)HSize_tot)/((double)VSize_tot); } else { // "A hsize vsize" if(!(tokens = sscanf(line, "%c %d %d", &Pics_tot[Num_tot].pic_name, &Pics_tot[Num_tot].pic_hsize, &Pics_tot[Num_tot].pic_vsize))) { goto end; } else if(tokens<3) { goto error; } else { InitPicture(&Pics_tot[Num_tot]); if(++Num_tot == MAXPICS) goto end; // don't read more than the allowed number of pictures } } } end: if(Num_tot < MINPICS) goto error; fclose(fptr); return TRUE; error: fclose(fptr); return FALSE; } //========================================================================= // static void InitPicture(picptr p); // // It calculates the area and the aspect ratio (in Pics[n]). // It also ensures that hsize>=vsize. //========================================================================= static void InitPicture(picptr p) { int dummy; if(p->pic_hsize < p->pic_vsize) { // ensure that hsize >= vsize dummy = p->pic_hsize; p->pic_hsize = p->pic_vsize; p->pic_vsize = dummy; } p->pic_aratio = ((double)p->pic_hsize) / ((double)p->pic_vsize); p->pic_limaratio[0] = MINLIMARATIO(p->pic_aratio); p->pic_limaratio[1] = p->pic_aratio + ARLIMIT; p->pic_area = p->pic_hsize * p->pic_vsize; MinPicture(p); p->pic_minhsizedelta = p->pic_minhsize * sqrt(p->pic_limaratio[0] / p->pic_aratio); p->pic_set = FALSE; // initially, picture not yet used (recursion) ... p->pic_dupl = FALSE; } //========================================================================= // static void MinPicture(picptr p); // // It calculates the minimum integer area, hsize and vsize with the // restriction minarea >= MinPictureArea. //========================================================================= static void MinPicture(picptr p) { int h1 = (int)ceil( sqrt( MinPictureArea * p->pic_limaratio[0] ) ); int v1 = (int)ceil( sqrt( MinPictureArea / p->pic_limaratio[1] ) ); int h2 = (int)ceil(MinPictureAreaFloat / ((double)v1)); // => h2 >= h1 int v2 = (int)ceil(MinPictureAreaFloat / ((double)h1)); // => v2 >= v1 int h, v, area; double aratio; p->pic_minarea = INT_MAX; for(h=h1; h<=h2; ++h) { for(v=v1; v<=v2; ++v) { if( (area = h * v) >= MinPictureArea && area < p->pic_minarea && (aratio = ((double) h) / ((double) v)) >= p->pic_limaratio[0] && aratio <= p->pic_limaratio[1] ) { p->pic_minhsize = h; p->pic_minvsize = v; p->pic_minarea = area; } } } if(p->pic_minarea == INT_MAX) { // this is a rare event p->pic_minhsize = h1; p->pic_minvsize = v2; p->pic_minarea = h1 * v2; } } //========================================================================= // static void CalcHVDRatios(short thr); // // Calculates the fields pic_hvdratio[] of the array Pics[thr][], depending // on the global variable ARDelta[thr] //========================================================================= static void CalcHVDRatios(short thr) { int i; picptr pptr; double ardelta = ARDelta[thr]; for(i=0, pptr=&Pics[thr][0]; ipic_hvdratio[0] = pptr->pic_aratio - ardelta; pptr->pic_hvdratio[1] = 1.0 / ( ((double)pptr->pic_hsize) / ((double)pptr->pic_vsize) + ardelta ); pptr->pic_hvdratio[2] = pptr->pic_aratio + ardelta; } } //========================================================================= // static void SortPics(picptr pptr, int n); // // Sort 'n' pictures in array 'pptr' by aspect ratio (ascending) //========================================================================= static void SortPics(picptr pptr, int n) { int i; double ar = pptr->pic_aratio; qsort((void *)pptr, (size_t)n, sizeof(pic), (int (*)(const void *, const void*))pic_compare); for(i=1, ++pptr; ipic_aratio == ar) pptr->pic_dupl = TRUE; // i.e. we have found a duplicate ! else ar = pptr->pic_aratio; } } //********************************************************************* // int pic_compare(const picptr a, const picptr b); // // qsort compare function for the array 'Pic[]': aspect ratio, asc. //********************************************************************* int pic_compare(const picptr a, const picptr b) { if(a->pic_aratio > b->pic_aratio) return 1; if(a->pic_aratio < b->pic_aratio) return -1; return 0; } //========================================================================= // static void MinFit(short thr); // // Produces a solution based on the minimum picture sizes on a row by row // resp. column by column approach. It assumes that the pictures in // Pic[thr][] are sorted according to the aspect ratio (ascending). It // calls CheckSolution(thr). //========================================================================= static void MinFit(short thr) { int i; picptr pptr; flpicptr flp, pred; double hpos = 0.0; // horiz. coordinate of left lower corner double vpos = 0.0; // vert. coordinate of left lower corner double width; // width of current row resp. column int num = Num[thr]; int hsize = HSize[thr]; int vsize = VSize[thr]; if(PageAspectRatio[thr] >= 1.0) { // row by row width = Pics[thr][0].pic_minvsize; for(i=0, pptr=&Pics[thr][0], flp=&Rec[thr][0]; ipic_minhsize) > hsize) { // next row ? if(pptr->pic_minhsize > hsize) return; // picture by far too big ! hpos = 0.0; vpos += width; width = pptr->pic_minvsize; } if(vpos + width > vsize) return; // not solveable ! flp->flpic_index = i; flp->flpic_name = pptr->pic_name; flp->flpic_flhsize = pptr->pic_minhsize; flp->flpic_flvsize = pptr->pic_minvsize; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = pptr->pic_minhsize * pptr->pic_minvsize; if(i==0) { flp->flpic_totvsize = width; } else if(hpos) { flp->flpic_totvsize = pred->flpic_totvsize; } else { flp->flpic_totvsize = pred->flpic_totvsize + width; } hpos += pptr->pic_minhsize; if(i) flp->flpic_tothsize = MAX(pred->flpic_tothsize, hpos); else flp->flpic_tothsize = hpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } } else { // column by column width = Pics[thr][0].pic_minvsize; for(i=0, pptr=&Pics[thr][0], flp=&Rec[thr][0]; ipic_minhsize) > vsize) { // next column ? if(pptr->pic_minhsize > vsize) return; // picture by far too big ! vpos = 0.0; hpos += width; width = pptr->pic_minvsize; } if(hpos + width > hsize) return; // not solveable ! flp->flpic_index = i; flp->flpic_name = pptr->pic_name; flp->flpic_flhsize = pptr->pic_minvsize; flp->flpic_flvsize = pptr->pic_minhsize; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = pptr->pic_minvsize * pptr->pic_minhsize; if(i==0) { flp->flpic_tothsize = width; } else if(vpos) { flp->flpic_tothsize = pred->flpic_tothsize; } else { flp->flpic_tothsize = pred->flpic_tothsize + width; } vpos += pptr->pic_minhsize; if(i) flp->flpic_totvsize = MAX(pred->flpic_totvsize, vpos); else flp->flpic_totvsize = vpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } } CheckSolution(thr); } //========================================================================= // static void SearchInitialSolution(short thr, enum boolean rowbyrow); // // Tries to find an initial solution by simply attaching pictures row by // row (or column by column resp.), depending on PageAspectRatio) and using // a common scaling factor. The scaling factor is found by binary search. // // The function assumes that the picture are sorted according to aspect // ratios (ascending). //========================================================================= static void SearchInitialSolution(short thr, enum boolean rowbyrow) { int i; picptr pptr; double longside = MAX(HSize[thr], VSize[thr]); // length of longer page side double length; // length of picture double sum_length = 0; // sum of hsize's of pictures double sum_area = 0; // sum of area's of pictures double min_vsize, min_vsizesq; // vsize of row and square of it double q1, q2, q; // lower and upper scaling factor for binary search int iter; // number of iterations of binary search double step; // step size for different ARDelta's clock_t maxclkt = MaxClockTicks[thr]; int num = Num[thr]; // determine the minimum total picture area needed min_vsize = Pics[thr][0].pic_minvsize; min_vsizesq = min_vsize * min_vsize; for(i=0, pptr=&Pics[thr][0]; ipic_minvsize) * pptr->pic_minhsize)) > longside) { // next row ? if(length > longside) return; // no chance, invalid input file, picture is far too big !! sum_length = 0; min_vsize = pptr->pic_minvsize; min_vsizesq = min_vsize * min_vsize; } sum_area += min_vsizesq * pptr->pic_aratio; } if(sum_area > PageArea[thr]) return; // page is too small ! step = (2.0 * ARLIMIT) / (NUMSTEPS-1); for(i=0, ARDelta[thr]=ARLIMIT; i= 0) continue; // we are done ! for(iter = 2; iter <= MAXITER && q2-q1>EPS; ++iter) { q = 0.5 * (q1 + q2); if(SimpleFit(thr, q, rowbyrow) == -1) q2 = q; else q1 = q; if(clock() >= maxclkt) PrintSolution(thr); // check, if it's time to quit } } // i } //========================================================================= // static int SimpleFit(short thr, double q, enum boolean rowbyrow); // // Produces a solution based on a common scaling factor on a row by row // resp. column by column approach. It assumes that the pictures in // Pic[thr][] are sorted according to the aspect ratio (ascending). It calls // CheckSolution(thr) and returns its return value (-1 means 'no solution'). //========================================================================= static int SimpleFit(short thr, double q, enum boolean rowbyrow) { int i, j; int num_used = 0; // number of pictures used picptr pptr, pptr2; flpicptr flp, pred = NULL; double hpos = 0.0; // horiz. coordinate of left lower corner double vpos = 0.0; // vert. coordinate of left lower corner double width; // width of current row resp. column double length; // length of current picture double length2; // length of alternately rotated picture int num = Num[thr]; int hsize = HSize[thr]; int vsize = VSize[thr]; flp = &Rec[thr][0]; width = q * Pics[thr][0].pic_minvsize; if(rowbyrow) { // row by row for(i=0, pptr=&Pics[thr][0]; ipic_set) continue; // picture already in use if(hpos + width * pptr->pic_hvdratio[0] > hsize) { // attach picture rotated or next row ? // try to attach some pictures rotated for(j=num-1, pptr2=&Pics[thr][num-1]; j>=i; --j, --pptr2) { if(pptr2->pic_set) continue; if(width >= pptr2->pic_minhsizedelta && hpos + width / pptr2->pic_hvdratio[2] <= hsize) { // attach it length2 = width / pptr2->pic_hvdratio[0]; if(hpos + length2 > hsize) length2 = hsize - hpos; pptr2->pic_set = TRUE; flp->flpic_index = j; flp->flpic_name = pptr2->pic_name; flp->flpic_flhsize = length2; flp->flpic_flvsize = width; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = width >= length2 ? width/length2 : length2/width; flp->flpic_flarea = length2 * width; if(pred) { flp->flpic_totvsize = pred->flpic_totvsize; if(hpos==0.0) flp->flpic_totvsize += width; } else { flp->flpic_totvsize = width; } hpos += length2; if(pred) flp->flpic_tothsize = MAX(pred->flpic_tothsize, hpos); else flp->flpic_tothsize = hpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; if(++num_used == num) goto sf_end; // we are done pred = flp++; } } // j hpos = 0.0; vpos += width; for(pptr2=pptr; pptr2->pic_set; ++pptr2); width = q * pptr2->pic_minvsize; } if(vpos + width > vsize) goto q_too_big; // q is too big ! if(pptr->pic_set) continue; length = width * pptr->pic_hvdratio[2]; if(hpos + length > hsize) { if((length = hsize - hpos) < width * pptr->pic_hvdratio[0]) goto q_too_big; } pptr->pic_set = TRUE; flp->flpic_index = i; flp->flpic_name = pptr->pic_name; flp->flpic_flhsize = length; flp->flpic_flvsize = width; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = length >= width ? length/width : width/length; flp->flpic_flarea = length * width; if(pred) { flp->flpic_totvsize = pred->flpic_totvsize; if(hpos==0.0) flp->flpic_totvsize += width; } else { flp->flpic_totvsize = width; } hpos += length; if(pred) flp->flpic_tothsize = MAX(pred->flpic_tothsize, hpos); else flp->flpic_tothsize = hpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; if(++num_used == num) goto sf_end; // we are done pred = flp++; } // i } else { // column by column for(i=0, pptr=&Pics[thr][0]; ipic_set) continue; // picture already in use if(vpos + width * pptr->pic_hvdratio[0] > vsize) { // attach picture rotated or next column ? // try to attach some pictures rotated for(j=num-1, pptr2=&Pics[thr][num-1]; j>=i; --j, --pptr2) { if(pptr2->pic_set) continue; if(width >= pptr2->pic_minhsizedelta && vpos + width / pptr2->pic_hvdratio[2] <= vsize) { // attach it length2 = width / pptr2->pic_hvdratio[0]; if(vpos + length2 > vsize) length2 = vsize - vpos; pptr2->pic_set = TRUE; flp->flpic_index = j; flp->flpic_name = pptr2->pic_name; flp->flpic_flhsize = width; flp->flpic_flvsize = length2; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = width >= length2 ? width/length2 : length2/width; flp->flpic_flarea = length * width; if(pred) { flp->flpic_tothsize = pred->flpic_tothsize; if(hpos==0.0) flp->flpic_tothsize += width; } else { flp->flpic_tothsize = width; } vpos += length2; if(pred) flp->flpic_totvsize = MAX(pred->flpic_totvsize, vpos); else flp->flpic_totvsize = vpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; if(++num_used == num) goto sf_end; // we are done pred = flp++; } } // j vpos = 0.0; hpos += width; for(pptr2=pptr; pptr2->pic_set; ++pptr2); width = q * pptr2->pic_minvsize; } if(hpos + width > hsize) goto q_too_big; // q is too big ! if(pptr->pic_set) continue; length = width * pptr->pic_hvdratio[2]; if(vpos + length > vsize) { if((length = vsize - vpos) < width * pptr->pic_hvdratio[0]) goto q_too_big; } pptr->pic_set = TRUE; flp->flpic_index = i; flp->flpic_name = pptr->pic_name; flp->flpic_flhsize = width; flp->flpic_flvsize = length; flp->flpic_flhpos = hpos; flp->flpic_flvpos = vpos; flp->flpic_flaratio = length >= width ? length/width : width/length; flp->flpic_flarea = length * width; if(pred) { flp->flpic_tothsize = pred->flpic_tothsize; if(hpos==0.0) flp->flpic_tothsize += width; } else { flp->flpic_tothsize = width; } vpos += length; if(i) flp->flpic_totvsize = MAX(pred->flpic_totvsize, vpos); else flp->flpic_totvsize = vpos; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; if(++num_used == num) goto sf_end; // we are done pred = flp++; } } sf_end: for(i=0, pptr=&Pics[thr][0]; ipic_set = FALSE; return (num_used == num ? CheckSolution(thr) : -1); q_too_big: for(i=0, pptr=&Pics[thr][0]; ipic_set = FALSE; return -1; } //========================================================================= // static void InitTwoPic(short thr); // // Initialize the matrix TwoPic[thr][] //========================================================================= static void InitTwoPic(short thr) { int i, j, k; picptr piptr, pjptr; twopic4ptr tp4ijptr, tp4jiptr; double v, minv, h1; int num = Num[thr]; for(i=0, piptr=&Pics[thr][0]; itp4_hv[0].tp_v = tp4jiptr->tp4_hv[0].tp_v = 1.0 / (piptr->pic_hvdratio[0] + pjptr->pic_hvdratio[0]); if(v < minv) minv = v; h1 = tp4ijptr->tp4_hv[0].tp_h1 = piptr->pic_hvdratio[0] * v; tp4jiptr->tp4_hv[0].tp_h1 = 1.0 - h1; break; case 1: // (T,F) for (i,j); (F,T) for (j,i) v = tp4ijptr->tp4_hv[1].tp_v = tp4jiptr->tp4_hv[2].tp_v = 1.0 / (piptr->pic_hvdratio[1] + pjptr->pic_hvdratio[0]); if(v < minv) minv = v; h1 = tp4ijptr->tp4_hv[1].tp_h1 = piptr->pic_hvdratio[1] * v; tp4jiptr->tp4_hv[2].tp_h1 = 1.0 - h1; break; case 2: // (F,T) for (i,j); (T,F) for (j,i) v = tp4ijptr->tp4_hv[2].tp_v = tp4jiptr->tp4_hv[1].tp_v = 1.0 / (piptr->pic_hvdratio[0] + pjptr->pic_hvdratio[1]); if(v < minv) minv = v; h1 = tp4ijptr->tp4_hv[2].tp_h1 = piptr->pic_hvdratio[0] * v; tp4jiptr->tp4_hv[1].tp_h1 = 1.0 - h1; break; case 3: // (T,T) v = tp4ijptr->tp4_hv[3].tp_v = tp4jiptr->tp4_hv[3].tp_v = 1.0 / (piptr->pic_hvdratio[1] + pjptr->pic_hvdratio[1]); if(v < minv) minv = v; h1 = tp4ijptr->tp4_hv[3].tp_h1 = piptr->pic_hvdratio[1] * v; tp4jiptr->tp4_hv[3].tp_h1 = 1.0 - h1; } // switch tp4ijptr->tp4_minv = tp4jiptr->tp4_minv = minv; } // k } // i } // j } //========================================================================= // static void SearchSolutions(short thr); // // Successive calls of SEARCHSOLUTION depending on the two variables // 'ARDelta[thr]' and (if Num[thr]>BRUTEFORCE) 'Weight1[thr]'. The grid size // is determined by the estimated time needed per SEARCHSOLUTION call. // // SEARCHSOLUTION = CalcHVDRatios(); InitTwoPic(); SearchSolution(0); //========================================================================= static void SearchSolutions(short thr) { int num; // number of SEARCHSOLUTION calls so far clock_t time_begin; // start time of first SEARCHSOLUTION call clock_t time_current; // current time clock_t time_delta; // difference between max. time stamp and current time stamp clock_t time_needed; // mean time needed per SEARCHSOLUTION call double numf_ar; // number of points on the ARDelta axis (floating point version) double numf_we; // number of points on the Weight1 axis (floating point version) int num_ar; // number of points on the ARDelta axis int num_we; // number of points on the Weight1 axis double q; // approx. ratio num_ar / num_we double delta_ar; // increment on the ARDelta axis double delta_we; // increment on the Weight axis int i, ar; // Laufvariable int white, tiebraker; double lower, upper; enum boolean improved; int numthr = Num[thr]; clock_t maxclkt = MaxClockTicks[thr]; solutionptr sptr = &Solution[thr]; ARDelta[thr] = Delta[numthr-1]; time_begin = clock(); CalcHVDRatios(thr); InitTwoPic(thr); SearchSolution(thr, 0); time_current = clock(); num = 1; time_delta = maxclkt - time_current; time_needed = time_current - time_begin; if(numthr <= BRUTEFORCE) { // result is independent of 'Weight1' // do a kind of 'grid search' first white = sptr->so_white; tiebraker = sptr->so_tiebraker; lower = ARMIN; upper = ARMAX; do { improved = FALSE; delta_ar = (upper - lower) / (NUMGRIDPTS - 1); for(i=0, ARDelta[thr]=lower; iso_white < white || sptr->so_tiebraker < tiebraker) { ar = ARDelta[thr]; white = sptr->so_white; tiebraker = sptr->so_tiebraker; improved = TRUE; } } num += NUMGRIDPTS; if(!improved) break; delta_ar = GRIDSHRINK * (upper - lower); if((lower = ar - delta_ar) < ARMIN) lower = ARMIN; if((upper = ar + delta_ar) > ARMAX) upper = ARMAX; } while(1); // finally do a linar search time_current = clock(); time_delta = maxclkt - time_current; time_needed = (time_current - time_begin) / num; ARDelta[thr] = ARMIN + (ARMAX - ARMIN) / ( ((double)time_delta) / ((double)time_needed) ); do { CalcHVDRatios(thr); InitTwoPic(thr); SearchSolution(thr, 0); time_current = clock(); time_delta = maxclkt - time_current; time_needed = (time_current - time_begin) / ++num; ARDelta[thr] += (ARMAX - ARDelta[thr]) / ( ((double)time_delta) / ((double)time_needed) ); } while(ARDelta[thr] < ARMAX); } else { // Num > BRUTEFORCE q = ARWEQ; numf_ar = sqrt(q * ((double)time_delta) / ((double)time_needed)); numf_we = numf_ar / q; if((num_ar = ceil(numf_ar - RDEPS)) < 2) num_ar = 2; if((num_we = ceil(numf_we - RDEPS)) < 2) num_we = 2; delta_ar = ARRANGE / (num_ar - 1); delta_we = WERANGE / (num_we - 1); Weight1[thr] = WEMIN; Weight2[thr] = 1.0 - WEMIN; do { for(ar=0, ARDelta[thr]=ARMAX; ar= maxclkt) PrintSolution(thr); // check, if it's time to quit for(i=0; ipic_set || // picture i is already used in recursion (i && pptr->pic_dupl && !(pptr-1)->pic_set) ) // picture is a duplicate of the picture before and this wasn't used yet => discard this permutation continue; pptr->pic_set = TRUE; // i.e. we decided to try it with this picture flp->flpic_index = i; flp->flpic_name = pptr->pic_name; for(s=0, u=used; s<4; ++s, ++u) *u = FALSE; if(n==0) { // beginning of the recursion // variants adding ARDelta to the aspect ratio flp->flpic_flhpos = flp->flpic_flvpos = 0.0; flp->flpic_flaratio = pptr->pic_hvdratio[2]; if(flp->flpic_flaratio >= 1.0) { flp->flpic_flhsize = (double)pptr->pic_minvsize * flp->flpic_flaratio; flp->flpic_flvsize = (double)pptr->pic_minvsize; } else { flp->flpic_flhsize = (double)pptr->pic_minvsize; flp->flpic_flvsize = (double)pptr->pic_minvsize / flp->flpic_flaratio; } flp->flpic_flarea = flp->flpic_flminarea = flp->flpic_flmaxarea = flp->flpic_flhsize * flp->flpic_flvsize; flp->flpic_tothsize = flp->flpic_flhsize; flp->flpic_totvsize = flp->flpic_flvsize; flp->flpic_totaratio = flp->flpic_flaratio; SearchSolution(thr, 1); if(pptr->pic_aratio != 1.0) { // try the rotation dummy = flp->flpic_flhsize; flp->flpic_flhsize = flp->flpic_tothsize = flp->flpic_flvsize; flp->flpic_flvsize = flp->flpic_totvsize = dummy; SearchSolution(thr, 1); } // variants subtracting ARDelta from the aspect ratio flp->flpic_flhpos = flp->flpic_flvpos = 0.0; flp->flpic_flaratio = pptr->pic_hvdratio[0]; if(flp->flpic_flaratio >= 1.0) { flp->flpic_flhsize = (double)pptr->pic_minvsize * flp->flpic_flaratio; flp->flpic_flvsize = (double)pptr->pic_minvsize; } else { flp->flpic_flhsize = (double)pptr->pic_minvsize; flp->flpic_flvsize = (double)pptr->pic_minvsize / flp->flpic_flaratio; } flp->flpic_flarea = flp->flpic_flminarea = flp->flpic_flmaxarea = flp->flpic_flhsize * flp->flpic_flvsize; flp->flpic_tothsize = flp->flpic_flhsize; flp->flpic_totvsize = flp->flpic_flvsize; flp->flpic_totaratio = flp->flpic_flaratio; SearchSolution(thr, 1); if(pptr->pic_aratio != 1.0) { // try the rotation dummy = flp->flpic_flhsize; flp->flpic_flhsize = flp->flpic_tothsize = flp->flpic_flvsize; flp->flpic_flvsize = flp->flpic_totvsize = dummy; SearchSolution(thr, 1); } } else if(n < num-1) { nobruteforce = (enum boolean)(n >= MaxBruteForce[thr]); if(n == num-2) { // 2 pictures left - try to find optimal solution for this subproblem for(s=i+1; salt_flaratio[0] = pptr->pic_hvdratio[2]; aptr->alt_flhsize[0] = pred->flpic_totvsize * aptr->alt_flaratio[0]; aptr->alt_flvsize[0] = pred->flpic_totvsize; aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_totaratio = (pred->flpic_tothsize + aptr->alt_flhsize[0]) / pred->flpic_totvsize; if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 1); // Alt. 2: attach one picture to the right + rotate ++aptr; aptr->alt_flaratio[0] = pptr->pic_hvdratio[0]; aptr->alt_flhsize[0] = pred->flpic_totvsize / aptr->alt_flaratio[0]; aptr->alt_flvsize[0] = pred->flpic_totvsize; aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_totaratio = (pred->flpic_tothsize + aptr->alt_flhsize[0]) / pred->flpic_totvsize; if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 1); // Alt. 3: attach one picture to the top + don't rotate ++aptr; aptr->alt_flaratio[0] = pptr->pic_hvdratio[0]; aptr->alt_flhsize[0] = pred->flpic_tothsize; aptr->alt_flvsize[0] = pred->flpic_tothsize / aptr->alt_flaratio[0]; aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_totaratio = pred->flpic_tothsize / (pred->flpic_totvsize + aptr->alt_flvsize[0]); if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 1); // Alt. 4: attach one picture to the top + rotate ++aptr; aptr->alt_flaratio[0] = pptr->pic_hvdratio[2]; aptr->alt_flhsize[0] = pred->flpic_tothsize; aptr->alt_flvsize[0] = pred->flpic_tothsize * aptr->alt_flaratio[0]; aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_totaratio = pred->flpic_tothsize / (pred->flpic_totvsize + aptr->alt_flvsize[0]); if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 1); for(j=num-1; j>=0; --j) { p2ptr = &Pics[thr][j]; if( p2ptr->pic_set || // picture j is already used in recursion (j && p2ptr->pic_dupl && !(p2ptr-1)->pic_set) ) // picture j is a duplicate of the picture before and this wasn't used yet => discard this permutation continue; tp4ijptr = &TwoPic[thr][i][j]; fl2p->flpic_index = j; fl2p->flpic_name = p2ptr->pic_name; if(n < num-2) { // in case n==Num-2 we already tried Search2PictureSolution() // calculate data for the alternatives 5..8: attach pictures to the right aptr = &a[4]; for(k=0; k<4; ++k, ++aptr) { aptr->alt_flhsize[0] = tp4ijptr->tp4_hv[k].tp_v * pred->flpic_totvsize; aptr->alt_flvsize[0] = tp4ijptr->tp4_hv[k].tp_h1 * pred->flpic_totvsize; aptr->alt_flaratio[0] = (aptr->alt_flhsize[0] >= aptr->alt_flvsize[0] ? aptr->alt_flhsize[0] / aptr->alt_flvsize[0] : aptr->alt_flvsize[0] / aptr->alt_flhsize[0]); aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_flhsize[1] = aptr->alt_flhsize[0]; aptr->alt_flvsize[1] = pred->flpic_totvsize - aptr->alt_flvsize[0]; aptr->alt_flaratio[1] = (aptr->alt_flhsize[1] >= aptr->alt_flvsize[1] ? aptr->alt_flhsize[1] / aptr->alt_flvsize[1] : aptr->alt_flvsize[1] / aptr->alt_flhsize[1]); aptr->alt_flarea[1] = aptr->alt_flhsize[1] * aptr->alt_flvsize[1]; aptr->alt_totaratio = (pred->flpic_tothsize + aptr->alt_flhsize[0]) / pred->flpic_totvsize; if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 2); } // calculate data for the alternatives 9..12: attach pictures to the top for(k=0; k<4; ++k, ++aptr) { aptr->alt_flhsize[0] = tp4ijptr->tp4_hv[k].tp_h1 * pred->flpic_tothsize; aptr->alt_flvsize[0] = tp4ijptr->tp4_hv[k].tp_v * pred->flpic_tothsize; aptr->alt_flaratio[0] = (aptr->alt_flhsize[0] >= aptr->alt_flvsize[0] ? aptr->alt_flhsize[0] / aptr->alt_flvsize[0] : aptr->alt_flvsize[0] / aptr->alt_flhsize[0]); aptr->alt_flarea[0] = aptr->alt_flhsize[0] * aptr->alt_flvsize[0]; aptr->alt_flhsize[1] = pred->flpic_tothsize - aptr->alt_flhsize[0]; aptr->alt_flvsize[1] = aptr->alt_flvsize[0]; aptr->alt_flaratio[1] = (aptr->alt_flhsize[1] >= aptr->alt_flvsize[1] ? aptr->alt_flhsize[1] / aptr->alt_flvsize[1] : aptr->alt_flvsize[1] / aptr->alt_flhsize[1]); aptr->alt_flarea[1] = aptr->alt_flhsize[1] * aptr->alt_flvsize[1]; aptr->alt_totaratio = pred->flpic_tothsize / (pred->flpic_totvsize + aptr->alt_flvsize[0]); if(nobruteforce) aptr->alt_delta = WeightedDelta(thr, pred, aptr, 2); } } if(nobruteforce) { // then do the recursion only for the 'best' candidate mindelta = INT_MAX; found = FALSE; for(s=0, aptr=&a[0]; s<12; ++s, ++aptr) { if((s<4 && !used[s]) || (s>=4 && nalt_delta <= mindelta) { found = TRUE; kmin = s; mindelta = aptr->alt_delta; } } } if(!found) continue; // i.e. no 'best' candidate found, every alternative already used kmax = kmin; } else { // try all alternatives ! kmin = 0; kmax = (n=kmin; --k) { if(k<4 && used[k]) continue; // i.e. we've already tried to attach picture i in that way aptr = &a[k]; switch(k) { case 0: // Alt. 1: attach picture to the right + don't rotate case 1: // Alt. 2: attach picture to the right + rotate used[k] = TRUE; flp->flpic_flaratio = aptr->alt_flaratio[0]; flp->flpic_flhsize = aptr->alt_flhsize[0]; flp->flpic_flvsize = aptr->alt_flvsize[0]; flp->flpic_flhpos = pred->flpic_tothsize; flp->flpic_flvpos = 0.0; flp->flpic_flarea = aptr->alt_flarea[0]; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize + flp->flpic_flhsize; flp->flpic_totvsize = pred->flpic_totvsize; flp->flpic_totaratio = aptr->alt_totaratio; break; case 2: // Alt. 3: attach picture to the top + don't rotate case 3: // Alt. 4: attach picture to the top + rotate used[k] = TRUE; flp->flpic_flaratio = aptr->alt_flaratio[0]; flp->flpic_flhsize = aptr->alt_flhsize[0]; flp->flpic_flvsize = aptr->alt_flvsize[0]; flp->flpic_flhpos = 0.0; flp->flpic_flvpos = pred->flpic_totvsize; flp->flpic_flarea = aptr->alt_flarea[0]; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize; flp->flpic_totvsize = pred->flpic_totvsize + flp->flpic_flvsize; flp->flpic_totaratio = aptr->alt_totaratio; break; case 4: // Alt. 5: attach 2 pictures to the right (F,F) case 5: // Alt. 6: attach 2 pictures to the right (T,F) case 6: // Alt. 7: attach 2 pictures to the right (F,T) case 7: // Alt. 8: attach 2 pictures to the right (T,T) p2ptr->pic_set = TRUE; flp->flpic_flaratio = aptr->alt_flaratio[0]; flp->flpic_flhsize = aptr->alt_flhsize[0]; flp->flpic_flvsize = aptr->alt_flvsize[0]; flp->flpic_flhpos = pred->flpic_tothsize; flp->flpic_flvpos = 0.0; flp->flpic_flarea = aptr->alt_flarea[0]; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); fl2p->flpic_flaratio = aptr->alt_flaratio[1]; fl2p->flpic_flhsize = aptr->alt_flhsize[1]; fl2p->flpic_flvsize = aptr->alt_flvsize[1]; fl2p->flpic_flhpos = pred->flpic_tothsize; fl2p->flpic_flvpos = flp->flpic_flvsize; fl2p->flpic_flarea = aptr->alt_flarea[1]; fl2p->flpic_flminarea = (fl2p->flpic_flarea < flp->flpic_flminarea ? fl2p->flpic_flarea : flp->flpic_flminarea); fl2p->flpic_flmaxarea = (fl2p->flpic_flarea > flp->flpic_flmaxarea ? fl2p->flpic_flarea : flp->flpic_flmaxarea); fl2p->flpic_tothsize = pred->flpic_tothsize + flp->flpic_flhsize; fl2p->flpic_totvsize = pred->flpic_totvsize; fl2p->flpic_totaratio = aptr->alt_totaratio; break; case 8: // Alt. 9 : attach 2 pictures to the top (F,F) case 9: // Alt. 10: attach 2 pictures to the top (T,F) case 10: // Alt. 11: attach 2 pictures to the top (F,T) case 11: // Alt. 12: attach 2 pictures to the top (T,T) p2ptr->pic_set = TRUE; flp->flpic_flaratio = aptr->alt_flaratio[0]; flp->flpic_flhsize = aptr->alt_flhsize[0]; flp->flpic_flvsize = aptr->alt_flvsize[0]; flp->flpic_flhpos = 0.0; flp->flpic_flvpos = pred->flpic_totvsize; flp->flpic_flarea = aptr->alt_flarea[0]; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); fl2p->flpic_flaratio = aptr->alt_flaratio[1]; fl2p->flpic_flhsize = aptr->alt_flhsize[1]; fl2p->flpic_flvsize = aptr->alt_flvsize[1]; fl2p->flpic_flhpos = flp->flpic_flhsize; fl2p->flpic_flvpos = flp->flpic_flvpos; fl2p->flpic_flarea = aptr->alt_flarea[1]; fl2p->flpic_flminarea = (fl2p->flpic_flarea < flp->flpic_flminarea ? fl2p->flpic_flarea : flp->flpic_flminarea); fl2p->flpic_flmaxarea = (fl2p->flpic_flarea > flp->flpic_flmaxarea ? fl2p->flpic_flarea : flp->flpic_flmaxarea); fl2p->flpic_tothsize = pred->flpic_tothsize; fl2p->flpic_totvsize = pred->flpic_totvsize + flp->flpic_flvsize; fl2p->flpic_totaratio = aptr->alt_totaratio; break; } // recurse only, if Num is small enough, or otherwise if up to now // the minimum picture size holds and in case a solution with 'white==0' // is already found if the lower bound for the tiebraker is smaller // than the current tiebraker if( num <= BRUTEFORCE || (((scaling=EstimateScaling(thr, flp, n, &tiebraker)) >= 1.0 || flp->flpic_flminarea * scaling >= MinPictureArea) && (!Solution[thr].so_found || Solution[thr].so_white > 0 || tiebraker < Solution[thr].so_tiebraker)) ) { if(k<4) { SearchSolution(thr, n+1); // recurse into next picture } else { SearchSolution(thr, n+2); // recurse into next 2 pictures } } else { if(clock() >= maxclkt) PrintSolution(thr); // check, if it's time to quit } p2ptr->pic_set = FALSE; } // k } // j } else { // n == Num-1 => end recursion pred = &Rec[thr][n-1]; // predecessor of flp if(pred->flpic_totaratio <= page_ar) { // attach picture to the right if((dx = pred->flpic_totvsize * page_ar - pred->flpic_tothsize) <= 0) goto nocheck; // first try to rotate (= Alt. 2) factor[1] = dx / pptr->pic_vsize; if((dy = factor[1] * pptr->pic_hsize) <= pred->flpic_totvsize) { // ok, let's attach it flp->flpic_flhsize = dx; flp->flpic_flvsize = dy; flp->flpic_flhpos = pred->flpic_tothsize; flp->flpic_flvpos = 0.0; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = factor[1] * factor[1] * pptr->pic_area; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize + dx; flp->flpic_totvsize = pred->flpic_totvsize; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } else { // don't rotate (= Alt. 1) factor[0] = dx / pptr->pic_hsize; dy = factor[0] * pptr->pic_vsize; flp->flpic_flhsize = dx; flp->flpic_flvsize = dy; flp->flpic_flhpos = pred->flpic_tothsize; flp->flpic_flvpos = 0.0; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = factor[0] * factor[0] * pptr->pic_area; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize + dx; flp->flpic_totvsize = pred->flpic_totvsize; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } } else { // attach picture to the top if((dy = pred->flpic_tothsize / page_ar - pred->flpic_totvsize) <= 0) goto nocheck; // first don't try to rotate (= Alt. 3) factor[2] = dy / pptr->pic_vsize; if((dx = factor[2] * pptr->pic_hsize) <= pred->flpic_tothsize) { // ok, let's attach it flp->flpic_flhsize = dx; flp->flpic_flvsize = dy; flp->flpic_flhpos = 0.0; flp->flpic_flvpos = pred->flpic_totvsize; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = factor[2] * factor[2] * pptr->pic_area; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize; flp->flpic_totvsize = pred->flpic_totvsize + dy; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } else { // rotate (= Alt. 4) factor[3] = dy / pptr->pic_hsize; dx = factor[3] * pptr->pic_vsize; flp->flpic_flhsize = dx; flp->flpic_flvsize = dy; flp->flpic_flhpos = 0.0; flp->flpic_flvpos = pred->flpic_totvsize; flp->flpic_flaratio = pptr->pic_aratio; flp->flpic_flarea = factor[3] * factor[3] * pptr->pic_area; flp->flpic_flminarea = (flp->flpic_flarea < pred->flpic_flminarea ? flp->flpic_flarea : pred->flpic_flminarea); flp->flpic_flmaxarea = (flp->flpic_flarea > pred->flpic_flmaxarea ? flp->flpic_flarea : pred->flpic_flmaxarea); flp->flpic_tothsize = pred->flpic_tothsize; flp->flpic_totvsize = pred->flpic_totvsize + dy; flp->flpic_totaratio = flp->flpic_tothsize / flp->flpic_totvsize; } } CheckSolution(thr); // end recursion nocheck: if(clock() >= maxclkt) PrintSolution(thr); // then we have to quit } pptr->pic_set = FALSE; // since we backtracked, free this picture again } } //========================================================================= // static double WeightedDelta(short thr, flpicptr pred, altptr aptr, // int mode); // // Calculates and returns the weighted mean of // a) deviation of total aspect ratio incl. alternative 'aptr' to // the page aspect ratio, and // b) deviation of tiebraker incl. alternative 'aptr' to the tiebraker // so far in 'pred' //========================================================================= static double WeightedDelta(short thr, flpicptr pred, altptr aptr, int mode) { double delta_ar, delta_tb; // delta of aspect ratios and delta of tiebrakers double tb_old, tb_new; // tiebraker old, tiebraker new double page_ar = PageAspectRatio[thr]; delta_ar = fabs(aptr->alt_totaratio - page_ar) / page_ar; tb_old = pred->flpic_flmaxarea - pred->flpic_flminarea; if(mode == 1) { tb_new = MAX(pred->flpic_flmaxarea, aptr->alt_flarea[0]) - MIN(pred->flpic_flminarea, aptr->alt_flarea[0]); } else { tb_new = max3(pred->flpic_flmaxarea, aptr->alt_flarea[0], aptr->alt_flarea[1]) - min3(pred->flpic_flminarea, aptr->alt_flarea[0], aptr->alt_flarea[1]); } delta_tb = (tb_new - tb_old) / tb_old; return(Weight1[thr] * delta_ar + Weight2[thr] * delta_tb); } //========================================================================= // static void Search2PictureSolution(short thr) // // This function is called when only two pictures are remaining in // SearchSolution(). // Rec[Num-3]: rectangle up to this level of recursion // Rec[Num-2]: first of the two pictures to set // Rec[Num-1]: second of the two pictures to set //========================================================================= static void Search2PictureSolution(short thr) { int i, k; double h; // horiz. size of rectangle double v; // vert. size of rectangle double minarea; // minimum area of pictures double factor; auo a[2]; // aspect ratios min/max (can be < 1 !) dhv hv[2]; // horiz. and vert. sizes flpicptr pred; flpicptr fptr[2]; enum boolean top; // TRUE, if attach to top, else FALSE picptr pptr[2]; int num = Num[thr]; int hsize = HSize[thr]; int vsize = VSize[thr]; double page_ar = PageAspectRatio[thr]; // set 'h', 'v', and 'top' if(num == 2) { // these two pictures are the only ones ! top = TRUE; h = hsize; v = vsize; } else { // more than two pictures in total pred = &Rec[thr][num-3]; if(pred->flpic_totaratio > page_ar) { top = TRUE; h = pred->flpic_tothsize; v = h / page_ar - pred->flpic_totvsize; } else { top = FALSE; h = pred->flpic_totvsize; v = h * page_ar - pred->flpic_tothsize; } } // set 'minarea' factor = (top ? hsize : vsize) / h; minarea = MinPictureAreaFloat / (factor * factor); // set pointers to pictures for(i=0; i<2; ++i) { fptr[i] = &Rec[thr][num-2+i]; pptr[i] = &Pics[thr][fptr[i]->flpic_index]; } // try all 4 combinations for(k=0; k<4; ++k) { switch(k) { case 0: a[0].au = pptr[0]->pic_limaratio[0]; // no rotations a[0].ao = pptr[0]->pic_limaratio[1]; a[1].au = pptr[1]->pic_limaratio[0]; a[1].ao = pptr[1]->pic_limaratio[1]; break; case 1: a[0].au = 1.0 / pptr[0]->pic_limaratio[1]; // rotate picture #1 a[0].ao = 1.0 / pptr[0]->pic_limaratio[0]; // picture #2 unchanged break; case 2: a[1].au = 1.0 / pptr[1]->pic_limaratio[1]; // rotate picture #2 a[1].ao = 1.0 / pptr[1]->pic_limaratio[0]; // picture #1 unchanged (i.e. both are rotated now) break; case 3: a[0].au = pptr[0]->pic_limaratio[0]; // normal orientation of picture #1 a[0].ao = pptr[0]->pic_limaratio[1]; // only picture 2 is rotated } if(Opti2Pics(h, v, minarea, a, hv)) { if(top) { // attach to the top fptr[0]->flpic_flhsize = hv[0].dh; fptr[0]->flpic_flvsize = hv[0].dv; fptr[0]->flpic_flhpos = 0; fptr[0]->flpic_flvpos = (num == 2 ? 0 : pred->flpic_totvsize); fptr[0]->flpic_flaratio = (hv[0].dh >= hv[0].dv ? hv[0].dh / hv[0].dv : hv[0].dv / hv[0].dh); fptr[0]->flpic_flarea = fptr[0]->flpic_flhsize * fptr[0]->flpic_flvsize; fptr[1]->flpic_flhsize = hv[1].dh; fptr[1]->flpic_flvsize = hv[1].dv; fptr[1]->flpic_flhpos = fptr[0]->flpic_flhsize; fptr[1]->flpic_flvpos = fptr[0]->flpic_flvpos; fptr[1]->flpic_flaratio = (hv[1].dh >= hv[1].dv ? hv[1].dh / hv[1].dv : hv[1].dv / hv[1].dh); fptr[1]->flpic_flarea = fptr[1]->flpic_flhsize * fptr[1]->flpic_flvsize; fptr[1]->flpic_tothsize = h; fptr[1]->flpic_totvsize = MAX(fptr[0]->flpic_flvsize, fptr[1]->flpic_flvsize); if(num > 2) fptr[1]->flpic_totvsize += pred->flpic_totvsize; fptr[1]->flpic_totaratio = fptr[1]->flpic_tothsize / fptr[1]->flpic_totvsize; CheckSolution(thr); } else { // attach to the right fptr[0]->flpic_flhsize = hv[0].dv; fptr[0]->flpic_flvsize = hv[0].dh; fptr[0]->flpic_flhpos = (num == 2 ? 0 : pred->flpic_tothsize); fptr[0]->flpic_flvpos = 0; fptr[0]->flpic_flaratio = (hv[0].dh >= hv[0].dv ? hv[0].dh / hv[0].dv : hv[0].dv / hv[0].dh); fptr[0]->flpic_flarea = fptr[0]->flpic_flhsize * fptr[0]->flpic_flvsize; fptr[1]->flpic_flhsize = hv[1].dv; fptr[1]->flpic_flvsize = hv[1].dh; fptr[1]->flpic_flhpos = fptr[0]->flpic_flhpos; fptr[1]->flpic_flvpos = fptr[0]->flpic_flvsize; fptr[1]->flpic_flaratio = (hv[1].dh >= hv[1].dv ? hv[1].dh / hv[1].dv : hv[1].dv / hv[1].dh); fptr[1]->flpic_flarea = fptr[1]->flpic_flhsize * fptr[1]->flpic_flvsize; fptr[1]->flpic_totvsize = h; fptr[1]->flpic_tothsize = MAX(fptr[0]->flpic_flhsize, fptr[1]->flpic_flhsize); if(num > 2) fptr[1]->flpic_tothsize += pred->flpic_tothsize; fptr[1]->flpic_totaratio = fptr[1]->flpic_tothsize / fptr[1]->flpic_totvsize; CheckSolution(thr); } } } } //========================================================================= // static enum boolean Opti2Pics(double h, double v, double minarea, // auoptr a, dhvptr hv); // // Optimize the placement of two pictures into a rectangle respecting min. // and max. aspect ratios. // // h : horiz. size of rectangle // v : vert. size of rectangle // minarea : min. area of each of the pictures // a : a[2]: array of aspect ratios (min. and max.) // The aspect ratios are always h/v, i.e. they can be < 1 !! // hv : hv[2]: Output of the program: horiz. and vert. sizes // // Opti2Pics() returns FALSE, if no solution, otherwise TRUE. //========================================================================= static enum boolean Opti2Pics(double h, double v, double minarea, auoptr a, dhvptr hv) { int i; double h_min[2]; // minimum horiz. sizes double h_max[2]; // maximum horiz. sizes double a_v; // aspect ratio of rectangle with min. area and vert. size v double l, r; // [l,r] = interval of possible solutions dhv hvl[2], hvr[2]; // two possible candidates at x=l and x=r // if 2 * min. area > area of rectangle quit if(h * v < 2 * minarea) return FALSE; // calculate minimum horiz. sizes a_v = minarea / (v * v); for(i=0; i<2; ++i) { if( a_v > a[i].ao || // greater than max. vert. size (h_min[i] = (a_v >= a[i].au ? v * a_v : sqrt(minarea * a[i].au))) >= h ) { // horiz. size of rectangle exceeded return FALSE; } } if(h_min[0] + h_min[1] > h) return FALSE; // horiz. size of rectangle exceeded // calculate maximum horiz. sizes for(i=0; i<2; ++i) { if((h_max[i] = a[i].ao * v) > h) h_max[i] = h; } // case 1: maximum pictures are distinct if(h_max[0] + h_max[1] <= h) { for(i=0; i<2; ++i) { hv[i].dh = h_max[i]; hv[i].dv = v; } return TRUE; } // case 2: maximum pictures aren't distinct if((l = h - h_max[1]) < h_min[0]) l = h_min[0]; if((r = h - h_min[1]) > h_max[0]) r = h_max[0]; if(l > r) return FALSE; // no solutions // calculate solution at x=l hvl[0].dh = l; if((hvl[0].dv = l / a[0].au) > v) hvl[0].dv = v; hvl[1].dh = h - l; if((hvl[1].dv = hvl[1].dh / a[1].au) > v) hvl[1].dv = v; // calculate solution at x=r hvr[0].dh = r; if((hvr[0].dv = r / a[0].au) > v) hvr[0].dv = v; hvr[1].dh = h - r; if((hvr[1].dv = hvr[1].dh / a[1].au) > v) hvr[1].dv = v; // decide which to choose if( hvl[0].dh * hvl[0].dv + hvl[1].dh * hvl[1].dv >= hvr[0].dh * hvr[0].dv + hvr[1].dh * hvr[1].dv ) { hv[0] = hvl[0]; hv[1] = hvl[1]; } else { hv[0] = hvr[0]; hv[1] = hvr[1]; } return TRUE; } //========================================================================= // static int CheckSolution(short thr); // // Try to transform the relaxed 'floating point solution' into a real // integer solution. If a valid solution is found and if it is the // first one found or a better one than the best solution then store // it as new best solution (and sort it iro the picture names). // CheckSolution tries two possible ways to come from the 'relaxed' // floating point solution to the integer solution: rounding the corners // up and rounding them down. Sometimes this makes a big difference for // the result ! If the tiebraker is zero, CheckSolution tries to further // optimize the tiebraker by moving some lines. // Return value = white space (min. of the two variants) or -1 if both // variants lead to no solution //========================================================================= static int CheckSolution(short thr) { flpicptr flp; solpicptr sop; double factor; int i, k, m; double flhpos2, flvpos2; // coordinates of right top corner (floating point version) int hpos2, vpos2; // coordinates of right top corner double vpos0; // intersection with x-axis double q; // slope double hdummy; int dv, dh; // add. amounts to increase the last picture int totarea; // total area used int white[2]; // pixels left white int biggest; // biggest picture int smallest; // smallest picture int tiebraker; // = biggest - smallest picptr pptr; // pointer to original picture int dummy; enum boolean valid; // FALSE, if at one stage of the check we find that the solution is invalid int num = Num[thr]; int hsize = HSize[thr]; int vsize = VSize[thr]; double page_ar = PageAspectRatio[thr]; solutionptr sptr; memcpy((void *)&RecCopy[thr][0], (void *)&Rec[thr][0], (size_t)(num * sizeof(flpic))); flp = &RecCopy[thr][num-1]; // determine factor to fit the relaxed solution into the Page factor = flp->flpic_totaratio <= page_ar ? vsize / flp->flpic_totvsize : hsize / flp->flpic_tothsize; for(i=0, flp = &RecCopy[thr][0]; iflpic_flhsize *= factor; flp->flpic_flvsize *= factor; flp->flpic_flhpos *= factor; flp->flpic_flvpos *= factor; if(i==num-1) { // additionally stretch/shrink the last picture q = flp->flpic_flvsize / flp->flpic_flhsize; vpos0 = flp->flpic_flvpos - q * flp->flpic_flhpos; if(hsize <= (hdummy = ((double)vsize - vpos0) / q)) { flp->flpic_flvsize = (q * (double)hsize + vpos0) - flp->flpic_flvpos; flp->flpic_flhsize = flp->flpic_flvsize / q; } else { flp->flpic_flhsize = hdummy - flp->flpic_flhpos; flp->flpic_flvsize = flp->flpic_flhsize * q; } } // calculate aratio and area (floating point version) flp->flpic_flaratio = flp->flpic_flhsize >= flp->flpic_flvsize ? flp->flpic_flhsize / flp->flpic_flvsize : flp->flpic_flvsize / flp->flpic_flhsize; flp->flpic_flarea = flp->flpic_flhsize * flp->flpic_flvsize; } for(k=0; k<2; ++k) { // k == 0 means 'rounding down', k == 1 means 'rounding up' valid = TRUE; totarea = 0; biggest = 0; smallest = INT_MAX; for(i=0, flp = &RecCopy[thr][0]; iflpic_index]; // calculate the coordinates of the right top corner (floating point version) flhpos2 = flp->flpic_flhpos + flp->flpic_flhsize; flvpos2 = flp->flpic_flvpos + flp->flpic_flvsize; // round the corners switch(k) { case 0: // round down flp->flpic_hpos = (int)floor(flp->flpic_flhpos + RDEPS); flp->flpic_vpos = (int)floor(flp->flpic_flvpos + RDEPS); flp->flpic_hsize = (hpos2 = (int)floor(flhpos2 + RDEPS)) - flp->flpic_hpos; flp->flpic_vsize = (vpos2 = (int)floor(flvpos2 + RDEPS)) - flp->flpic_vpos; break; case 1: // round up flp->flpic_hpos = (int)ceil(flp->flpic_flhpos - RDEPS); flp->flpic_vpos = (int)ceil(flp->flpic_flvpos - RDEPS); flp->flpic_hsize = (hpos2 = (int)ceil(flhpos2 - RDEPS)) - flp->flpic_hpos; flp->flpic_vsize = (vpos2 = (int)ceil(flvpos2 - RDEPS)) - flp->flpic_vpos; } // make some corrections at the right and top border if(--hpos2 >= hsize) { hpos2 = hsize - 1; flp->flpic_hsize = hsize - flp->flpic_flhpos; } else if(hpos2 == hsize-2) { ++hpos2; ++flp->flpic_hsize; } if(--vpos2 >= vsize) { vpos2 = vsize - 1; flp->flpic_vsize = vsize - flp->flpic_flvpos; } else if(vpos2 == vsize-2) { ++vpos2; ++flp->flpic_vsize; } // try to increase the last picture if(i==num-1) { if(flp->flpic_vsize >= flp->flpic_hsize) { dv = (int)floor(flp->flpic_hsize * pptr->pic_limaratio[1] - flp->flpic_vsize + RDEPS); dh = (int)floor(flp->flpic_vsize / pptr->pic_limaratio[0] - flp->flpic_hsize + RDEPS); } else { dv = (int)floor(flp->flpic_hsize / pptr->pic_limaratio[0] - flp->flpic_vsize + RDEPS); dh = (int)floor(flp->flpic_vsize * pptr->pic_limaratio[1] - flp->flpic_hsize + RDEPS); } if((dummy = (vsize-1) - vpos2) < dv) dv = dummy; flp->flpic_vsize += dv; vpos2 += dv; if((dummy = (hsize-1) - hpos2) < dh) dh = dummy; flp->flpic_hsize += dh; hpos2 += dh; } // calculate new aspect ratio and area flp->flpic_aratio = flp->flpic_hsize >= flp->flpic_vsize ? ((double)flp->flpic_hsize) / ((double)flp->flpic_vsize) : ((double)flp->flpic_vsize) / ((double)flp->flpic_hsize); flp->flpic_area = flp->flpic_hsize * flp->flpic_vsize; // check aspect ratio for(m=0; m < 2 && fabs(flp->flpic_aratio - pptr->pic_aratio) > ARLIMIT; ++m) { // shrink picture if(pptr->pic_aratio > flp->flpic_aratio) { if(flp->flpic_hsize >= flp->flpic_vsize) { flp->flpic_vsize -= (int)ceil((double)flp->flpic_vsize - (double)flp->flpic_hsize / pptr->pic_limaratio[0] - RDEPS); } else { flp->flpic_hsize -= (int)ceil((double)flp->flpic_hsize - (double)flp->flpic_vsize / pptr->pic_limaratio[0] - RDEPS); } } else { if(flp->flpic_hsize >= flp->flpic_vsize) { flp->flpic_hsize -= (int)ceil((double)flp->flpic_hsize - (double)flp->flpic_vsize * pptr->pic_limaratio[1] - RDEPS); } else { flp->flpic_vsize -= (int)ceil((double)flp->flpic_vsize - (double)flp->flpic_hsize * pptr->pic_limaratio[1] - RDEPS); } } flp->flpic_aratio = flp->flpic_hsize >= flp->flpic_vsize ? ((double)flp->flpic_hsize) / ((double)flp->flpic_vsize) : ((double)flp->flpic_vsize) / ((double)flp->flpic_hsize); } // check validity of the solution if((flp->flpic_area = flp->flpic_hsize*flp->flpic_vsize) < MinPictureArea || fabs(flp->flpic_aratio - pptr->pic_aratio) > ARLIMIT) { valid = FALSE; } else { totarea += flp->flpic_area; if(flp->flpic_area < smallest) smallest = flp->flpic_area; if(flp->flpic_area > biggest) biggest = flp->flpic_area; } flp->flpic_hpos2 = flp->flpic_hpos + flp->flpic_hsize - 1; flp->flpic_vpos2 = flp->flpic_vpos + flp->flpic_vsize - 1; } // i if(valid) { if((white[k] = PageArea[thr] - totarea) < 0) { // something went wrong, solution is not valid !? valid = FALSE; } if(!white[k]) OptimizeTiebraker(thr, &biggest, &smallest, FALSE); tiebraker = biggest - smallest; } if(valid) { sptr = &Solution[thr]; if(!sptr->so_found || // i.e. it is the first solution found -> take it white[k] < sptr->so_white || // we have found a better candidate ! (white[k] == sptr->so_white && tiebraker < sptr->so_tiebraker) ) { // this solution has a better tiebraker ! sptr->so_found = TRUE; sptr->so_white = white[k]; sptr->so_tiebraker = tiebraker; sptr->so_biggest = biggest; sptr->so_smallest = smallest; for(i=0, flp=&RecCopy[thr][0], sop=&sptr->so_pics[0]; isolpic_index = flp->flpic_index; sop->solpic_name = flp->flpic_name; sop->solpic_hsize = flp->flpic_hsize; sop->solpic_vsize = flp->flpic_vsize; sop->solpic_hpos = flp->flpic_hpos; sop->solpic_vpos = flp->flpic_vpos; } if(white[k] == 0 && tiebraker == 0) PrintSolution(thr); // no better solution possible } } } // k if(white[0] >= 0 && white[1] >= 0) return MIN(white[0], white[1]); if(white[0] == -1) return white[1]; return white[0]; } //========================================================================= // static void SortSolution(short thr); // // Sort 'Num[thr]' pictures in array 'Solution[thr].so_pics[]' by name // (ascending) //========================================================================= static void SortSolution(short thr) { qsort((void *)&Solution[thr].so_pics[0], (size_t)Num[thr], sizeof(solpic), (int (*)(const void *, const void*))sol_compare); } //********************************************************************* // int sol_compare(const solpicptr a, const solpicptr b); // // qsort compare function for the array 'Solution.so_pics[]' //********************************************************************* int sol_compare(const solpicptr a, const solpicptr b) { if(a->solpic_name > b->solpic_name) return 1; if(a->solpic_name < b->solpic_name) return -1; return 0; } //********************************************************************* // static void OptimizeTiebraker(short thr, int *biggest, // int *smallest, enum boolean endgame); // // OptimizeTiebraker() is called, when we have found a solution with no // uncovered pixels. It tries to further improve the result, i.e. to // reduce the tiebraker, by fiddling around with some "lines". // // If endgame=FALSE, then call PrintSolution() if the time is up. // Otherwise just return (because then we come from PrintSolution()'s // postprocessing of the multi-threading result). //********************************************************************* static void OptimizeTiebraker(short thr, int *biggest, int *smallest, enum boolean endgame) { int numlines; // number of horiz. or vert. lines int newsmallest, newbiggest; // values after some line moves int moveleft, moveright; // number of pixels to move the line left / right int move; // number of pixels to move the line (negative or positive) enum boolean moved; // TRUE, if there are still lines that can be moved enum boolean tbchanged; // TRUE, if the tiebraker has changed int numiter = 0; // number of iterations with no tiebraker improvement lineptr lptr; // pointer to horiz. or vert. linked list of lines int i, p; // Laufvariablen flpicptr flp; int num = Num[thr]; clock_t maxclkt = MaxClockTicks[thr]; // move some lines... do { moved = FALSE; tbchanged = FALSE; // first the horizontal lines FindCorners(thr, HORIZ); if((numlines = FindLines(thr, HORIZ))) { for(i=0, lptr=&Lines[thr][HORIZ][0]; i= moveright) ? moveleft : -moveright) != 0) { MoveLine(lptr, HORIZ, move); moved = TRUE; } ++lptr; } } // now the horizontal lines. Important: Do not mix horiz. and vert. line optimizatio, it // has to be done one after another. One also has to 'refind' the corners, because they // may have moved and lines previously independent may no longer be independent and // vice versa !! FindCorners(thr, VERT); if((numlines = FindLines(thr, VERT))) { for(i=0, lptr=&Lines[thr][VERT][0]; i= moveright) ? -moveleft : moveright) != 0) { MoveLine(lptr, VERT, move); moved = TRUE; } ++lptr; } } // let's see if the tiebraker has changed newsmallest = INT_MAX; newbiggest = 0; for(p=0, flp=&RecCopy[thr][0]; pflpic_area < newsmallest) newsmallest = flp->flpic_area; if(flp->flpic_area > newbiggest) newbiggest = flp->flpic_area; } if(newsmallest > *smallest) { // ">" because tiebrakers get smaller ! *smallest = newsmallest; tbchanged = TRUE; } if(newbiggest < *biggest) { // "<" because tiebrakers get smaller ! *biggest = newbiggest; tbchanged = TRUE; } if(clock() >= maxclkt) { // check, if it's time to quit if(endgame) return; // we were called by PrintSolution PrintSolution(thr); } if(tbchanged) numiter = 0; else ++numiter; } while(moved && numiter < MAXLINEITER); } //********************************************************************* // static void FindCorners(short thr, enum horizvert hv); // // Fill Corners[] with corners of all pictures except page corners // and corners not needed for the lines with direction 'hv' in // FindLines(): // hv = HORIZ: throw away SW and NW // hv = VERT : throw away SW and SE //********************************************************************* static void FindCorners(short thr, enum horizvert hv) { int i; flpicptr flp; cornerptr cop; int num = Num[thr]; int maxhpos = MaxHPos[thr]; int maxvpos = MaxVPos[thr]; if(hv == HORIZ) { for(i=0, flp=&RecCopy[thr][0], cop=&Corners[thr][0]; iflpic_hpos2 < maxhpos || flp->flpic_vpos) { cop->co_hpos = flp->flpic_hpos2; cop->co_vpos = flp->flpic_vpos; cop->co_dir = SE; cop->co_flp = flp; ++cop; } // NE if(flp->flpic_hpos2 < maxhpos || flp->flpic_vpos2 < maxvpos) { cop->co_hpos = flp->flpic_hpos2; cop->co_vpos = flp->flpic_vpos2; cop->co_dir = NE; cop->co_flp = flp; ++cop; } } // i } else { // hv == VERT for(i=0, flp=&RecCopy[thr][0], cop=&Corners[thr][0]; iflpic_hpos2 < maxhpos || flp->flpic_vpos2 < maxvpos) { cop->co_hpos = flp->flpic_hpos2; cop->co_vpos = flp->flpic_vpos2; cop->co_dir = NE; cop->co_flp = flp; ++cop; } // NW if(flp->flpic_hpos || flp->flpic_vpos2 < maxvpos) { cop->co_hpos = flp->flpic_hpos; cop->co_vpos = flp->flpic_vpos2; cop->co_dir = NW; cop->co_flp = flp; ++cop; } } // i } } //********************************************************************* // static int FindLines(short thr, enum horizvert hv); // // Find all horizontal (hv=HORIZ) or vertical lines (hv = VERT) // (which can independently be moved). The function returns the number // of lines found. //********************************************************************* static int FindLines(short thr, enum horizvert hv) { int i; cornerptr cop; liflpicptr heap = &FlpicHeap[thr][0]; liflpicptr leftliptr, rightliptr; int leftpos, rightpos; lineptr lptr, lptr2; int pos; enum leftright lr; int numlines = 0; int numco = NumCo[thr]; int maxhpos = MaxHPos[thr]; int maxvpos = MaxVPos[thr]; if(hv == HORIZ) { // horizontal lines qsort((void *)&Corners[thr][0], (size_t)numco, sizeof(corner), (int (*)(const void *, const void*))cor_v_compare); for(i=0, cop=&Corners[thr][0], pos=0, lptr=NULL; ico_vpos) continue; // throw away western corner points if(cop->co_vpos == maxvpos) break; if((cop->co_dir == NE && cop->co_vpos > pos) || // start a new line (cop->co_dir == SE && cop->co_vpos - pos > 1) ) { ++numlines; if(lptr) ++lptr; else lptr = &Lines[thr][HORIZ][0]; lptr->line_pos = pos = cop->co_vpos; lptr->line_lr[LEFT] = lptr->line_lr[RIGHT] = NULL; } // attach picture to the list it belongs to (LEFT or RIGHT) lr = (cop->co_dir == SE) ? LEFT : RIGHT; heap->lifl_flp = cop->co_flp; heap->lifl_next = lptr->line_lr[lr]; lptr->line_lr[lr] = heap++; } // We now have a number of horizontal lines that we may perhaps be able to split into independent parts // The hpos entries in the two picture lists are sorted descending (so if we successively attach them // in front of the picture lists we get ascending order) for(i=0, lptr=&Lines[thr][HORIZ][0], lptr2=&Lines[thr][HORIZ][numlines]; iline_lr[LEFT]; // != NULL by definition (no uncovered pixels) leftpos = leftliptr->lifl_flp->flpic_hpos2; rightliptr = lptr->line_lr[RIGHT]; // != NULL by definition (no uncovered pixels) rightpos = rightliptr->lifl_flp->flpic_hpos2; while(leftliptr && rightliptr) { if(leftpos < rightpos) { leftliptr = leftliptr->lifl_next; if(leftliptr) leftpos = leftliptr->lifl_flp->flpic_hpos2; continue; } if(rightpos < leftpos) { rightliptr = rightliptr->lifl_next; if(rightliptr) rightpos = rightliptr->lifl_flp->flpic_hpos2; continue; } // rightpos == leftpos => start a new line (if we are not at the end of the list) if(leftliptr->lifl_next) { // then by definition also rightliptr->lifl_next != NULL lptr2->line_pos = lptr->line_pos; lptr2->line_lr[LEFT] = leftliptr->lifl_next; lptr2->line_lr[RIGHT] = rightliptr->lifl_next; leftliptr->lifl_next = rightliptr->lifl_next = NULL; ++numlines; ++lptr2; } leftliptr = NULL; // so that we escape the while loop and go to the next line } } } else { // hv == VERT, i.e. we look for vertical lines qsort((void *)&Corners[thr][0], (size_t)numco, sizeof(corner), (int (*)(const void *, const void*))cor_h_compare); for(i=0, cop=&Corners[thr][0], pos=0, lptr=NULL; ico_hpos) continue; // throw away southern corner points if(cop->co_hpos == maxhpos) break; if((cop->co_dir == NE && cop->co_hpos > pos) || // start a new line (cop->co_dir == NW && cop->co_hpos - pos > 1) ) { ++numlines; if(lptr) ++lptr; else lptr = &Lines[thr][VERT][0]; lptr->line_pos = pos = cop->co_hpos; lptr->line_lr[LEFT] = lptr->line_lr[RIGHT] = NULL; } // attach picture to the list it belongs to (LEFT or RIGHT) lr = (cop->co_dir == NE) ? LEFT : RIGHT; heap->lifl_flp = cop->co_flp; heap->lifl_next = lptr->line_lr[lr]; lptr->line_lr[lr] = heap++; } // We now have a number of vertical lines that we may perhaps be able to split into independent parts // The vpos entries in the two picture lists are sorted descending (so if we successively attach them // in front of the picture lists we get ascending order) for(i=0, lptr=&Lines[thr][VERT][0], lptr2=&Lines[thr][VERT][numlines]; iline_lr[LEFT]; // != NULL by definition (no uncovered pixels) leftpos = leftliptr->lifl_flp->flpic_vpos2; rightliptr = lptr->line_lr[RIGHT]; // != NULL by definition (no uncovered pixels) rightpos = rightliptr->lifl_flp->flpic_vpos2; while(leftliptr && rightliptr) { if(leftpos < rightpos) { leftliptr = leftliptr->lifl_next; if(leftliptr) leftpos = leftliptr->lifl_flp->flpic_vpos2; continue; } if(rightpos < leftpos) { rightliptr = rightliptr->lifl_next; if(rightliptr) rightpos = rightliptr->lifl_flp->flpic_vpos2; continue; } // rightpos == leftpos => start a new line (if we are not at the end of the list) if(leftliptr->lifl_next) { // then by definition also rightliptr->lifl_next != NULL lptr2->line_pos = lptr->line_pos; lptr2->line_lr[LEFT] = leftliptr->lifl_next; lptr2->line_lr[RIGHT] = rightliptr->lifl_next; leftliptr->lifl_next = rightliptr->lifl_next = NULL; ++numlines; ++lptr2; } leftliptr = NULL; // so that we escape the while loop and go to the next line } } } return numlines; } //********************************************************************* // int cor_v_compare(const cornerptr a, const cornerptr b); // // qsort compare function for the array 'Corners[]' // (vpos first (ascending), then southern corners, then hpos // (descending)) //********************************************************************* int cor_v_compare(const cornerptr a, const cornerptr b) { if(a->co_vpos > b->co_vpos) return 1; if(a->co_vpos < b->co_vpos) return -1; if((a->co_dir == NW || a->co_dir == NE) && (b->co_dir == SW || b->co_dir == SE)) return 1; if((a->co_dir == SW || a->co_dir == SE) && (b->co_dir == NW || b->co_dir == NE)) return -1; if(a->co_hpos > b->co_hpos) return -1; if(a->co_hpos < b->co_hpos) return 1; return 0; // <- this case should not happen } //********************************************************************* // int cor_h_compare(const cornerptr a, const cornerptr b); // // qsort compare function for the array 'Corners[]' // (hpos first (ascending), then western corners, then vpos // (descending)) //********************************************************************* int cor_h_compare(const cornerptr a, const cornerptr b) { if(a->co_hpos > b->co_hpos) return 1; if(a->co_hpos < b->co_hpos) return -1; if((a->co_dir == NE || a->co_dir == SE) && (b->co_dir == NW || b->co_dir == SW)) return 1; if((a->co_dir == NW || a->co_dir == SW) && (b->co_dir == NE || b->co_dir == SE)) return -1; if(a->co_vpos > b->co_vpos) return -1; if(a->co_vpos < b->co_vpos) return 1; return 0; // <- this case should not happen } //========================================================================= // static void CalcStretchShrinkPicBdry(short thr, flpicptr flp, // enum horizvert hv, int fmin, int fmax, int *deltamin, int *deltamax); // // The function calculates the minimum (deltamin) and maximum (deltamax) // the picture can be shrunken or enlarged in the direction 'hv' respecting // minimum and maxiomum aspect ratios and minimum and maximum area ('fmin' // and 'fmax' resp.). // // deltamin is non-positive, deltamax is non-negative. //========================================================================= static void CalcStretchShrinkPicBdry(short thr, flpicptr flp, enum horizvert hv, int fmin, int fmax, int *deltamin, int *deltamax) { picptr pic = &Pics[thr][flp->flpic_index]; if(hv == VERT) { if(flp->flpic_hsize >= flp->flpic_vsize) { *deltamin = (int)ceil( max3(((double)flp->flpic_vsize) * pic->pic_limaratio[0], ((double)fmin) / ((double)flp->flpic_vsize), 1.0) - RDEPS) - flp->flpic_hsize; *deltamax = (int)floor(min2(((double)flp->flpic_vsize) * pic->pic_limaratio[1], ((double)fmax) / ((double)flp->flpic_vsize)) + RDEPS) - flp->flpic_hsize; } else { // flp->flpic_hsize < flp->flpic_vsize *deltamin = (int)ceil( max3(((double)flp->flpic_vsize) / pic->pic_limaratio[1], ((double)fmin) / ((double)flp->flpic_vsize), 1.0) - RDEPS) - flp->flpic_hsize; *deltamax = (int)floor(min2(((double)flp->flpic_vsize) / pic->pic_limaratio[0], ((double)fmax) / ((double)flp->flpic_vsize)) + RDEPS) - flp->flpic_hsize; } } else { // hv == HORIZ if(flp->flpic_hsize >= flp->flpic_vsize) { *deltamin = (int)ceil( max3(((double)flp->flpic_hsize) / pic->pic_limaratio[1], ((double)fmin) / ((double)flp->flpic_hsize), 1.0) - RDEPS) - flp->flpic_vsize; *deltamax = (int)floor(min2(((double)flp->flpic_hsize) / pic->pic_limaratio[0], ((double)fmax) / ((double)flp->flpic_hsize)) + RDEPS) - flp->flpic_vsize; } else { // flp->flpic_hsize < flp->flpic_vsize *deltamin = (int)ceil( max3(((double)flp->flpic_hsize) * pic->pic_limaratio[0], ((double)fmin) / ((double)flp->flpic_hsize), 1.0) - RDEPS) - flp->flpic_vsize; *deltamax = (int)floor(min2(((double)flp->flpic_hsize) * pic->pic_limaratio[1], ((double)fmax) / ((double)flp->flpic_hsize)) + RDEPS) - flp->flpic_vsize; } } if(*deltamin > 0) *deltamin = 0; if(*deltamax < 0) *deltamax = 0; } //========================================================================= // static void StretchShrinkPic(flpicptr flp, enum horizvert hv, // enum leftright lr, int delta); // // Stretch/Shrink picture 'flp' by delta pixels. If hv = VERT, then LEFT // means right side and RIGHT means left side. IF hv = HORIZ, then LEFT // means bottom side and RIGHT means top side. //========================================================================= static void StretchShrinkPic(flpicptr flp, enum horizvert hv, enum leftright lr, int delta) { if(hv == VERT) { if(lr == RIGHT) { // left side flp->flpic_hpos -= delta; } else { // lr == LEFT => right side flp->flpic_hpos2 += delta; } flp->flpic_hsize += delta; } else { // hv == HORIZ if(lr == RIGHT) { // top side flp->flpic_vpos2 += delta; } else { // lr == LEFT => bottom side flp->flpic_vpos -= delta; } flp->flpic_vsize += delta; } flp->flpic_aratio = flp->flpic_hsize >= flp->flpic_vsize ? ((double)flp->flpic_hsize) / ((double)flp->flpic_vsize) : ((double)flp->flpic_vsize) / ((double)flp->flpic_hsize); flp->flpic_area = flp->flpic_hsize * flp->flpic_vsize; } //========================================================================= // static void CalcMoveLine(short thr, lineptr lptr, enum horizvert hv, // int fmin, int fmax, int *moveleft, int *moveright); // // The function calculates the max. number of pixels we can move the line // to the left (moveleft) and to the right (moveright). Both variables // are non-negative. 'hv' tells the function whether it's a vertical or // a horizontal line. 'fmin' and 'fmax' are the minimum and maximum // picture areas. // The function assumes that lptr != NULL. //========================================================================= static void CalcMoveLine(short thr, lineptr lptr, enum horizvert hv, int fmin, int fmax, int *moveleft, int *moveright) { liflpicptr lifptr; int deltamin, deltamax; *moveleft = *moveright = INT_MAX; // left pictures for(lifptr = lptr->line_lr[LEFT]; lifptr; lifptr = lifptr->lifl_next) { CalcStretchShrinkPicBdry(thr, lifptr->lifl_flp, hv, fmin, fmax, &deltamin, &deltamax); if((deltamin = -deltamin) < *moveleft) *moveleft = deltamin; if(deltamax < *moveright) *moveright = deltamax; } // right pictures for(lifptr = lptr->line_lr[RIGHT]; lifptr; lifptr = lifptr->lifl_next) { CalcStretchShrinkPicBdry(thr, lifptr->lifl_flp, hv, fmin, fmax, &deltamin, &deltamax); if(deltamax < *moveleft) *moveleft = deltamax; if((deltamin = -deltamin) < *moveright) *moveright = deltamin; } } //========================================================================= // static void MoveLine(lineptr lptr, enum horizvert hv, int move); // // Moves line 'lptr' by 'move' pixels ('move' may be negative). // 'hv' tells the function whether it's a vertical or a horizontal line. // The function assumes that lptr != NULL. //========================================================================= static void MoveLine(lineptr lptr, enum horizvert hv, int move) { liflpicptr lifptr; int delta; // left pictures delta = (hv == VERT) ? move : -move; for(lifptr = lptr->line_lr[LEFT]; lifptr; lifptr = lifptr->lifl_next) StretchShrinkPic(lifptr->lifl_flp, hv, LEFT, delta); // right pictures delta = -delta; for(lifptr = lptr->line_lr[RIGHT]; lifptr; lifptr = lifptr->lifl_next) StretchShrinkPic(lifptr->lifl_flp, hv, RIGHT, delta); lptr->line_pos += move; } //========================================================================= // static double EstimateScaling(short thr, flpicptr flp, int n, // double *tiebraker); // // Estimates a lower bound for the area scaling of the final solution to // fit into the page based on the pictures chosen so far (including the last // one 'flp'). 'n' is the current recursion level. // // The function also returns a lower bound for the tiebraker. //========================================================================= static double EstimateScaling(short thr, flpicptr flp, int n, double *tiebraker) { int i, j, minj; picptr pptr; double minlength; // min{tothsize, totvsize} double minlengthsq; // = minlength^2 double minarea; // min. of area used by this solution enum boolean used[MAXPICS]; double minv, dummy; double scaling; int num = Num[thr]; // scaling: Attach remaining pictures, each with minimal possible areas // Calculate the scaling based on the total area. minlength = MIN(flp->flpic_tothsize, flp->flpic_totvsize); minlengthsq = minlength * minlength; minarea = flp->flpic_tothsize * flp->flpic_totvsize; if(n < num-2) { // i.e. there are still at least two pictures not used in recursion // initialize used[] for(i=0, pptr=&Pics[thr][0]; ipic_set; for(i=0; iflpic_flmaxarea - flp->flpic_flminarea) * scaling; return scaling; } //========================================================================= // static void PrintSolution(short thr); // // Print the current solution to stdout (or "no solution found" if // we were unsuccessfull. // // If thr>0 (i.e. we are a child process) then we just exit. // If thr=0 then we are the parent. In this case we wait for the child // processes to finish and then merge all the solutions to the solution // of the whole problem. //========================================================================= static void PrintSolution(short thr) { int i; #ifdef __linux__ flpicptr flp; solpicptr sop; if(thr) exit(EXIT_SUCCESS); // if we are a child process, then exit if(Forked) { for(i=1; isolpic_index = flp->flpic_index; sop->solpic_name = flp->flpic_name; sop->solpic_hsize = flp->flpic_hsize; sop->solpic_vsize = flp->flpic_vsize; sop->solpic_hpos = flp->flpic_hpos; sop->solpic_vpos = flp->flpic_vpos; } if(!Solution[0].so_white) Solution[0].so_tiebraker = Solution[0].so_biggest - Solution[0].so_smallest; } #endif // sort the solution SortSolution(0); if(Testing) printf("whitespace = %d\ntiebraker = %d\n", Solution[0].so_white, Solution[0].so_tiebraker); for(i=0; i Solution[0].so_biggest) Solution[0].so_biggest = Solution[i].so_biggest; if(Solution[i].so_smallest < Solution[0].so_smallest) Solution[0].so_smallest = Solution[i].so_smallest; } Solution[0].so_tiebraker = Solution[0].so_biggest - Solution[0].so_smallest; // copy pictures of threads (> 0) into Pic[0] for(i=1, pptr0=&Pics[0][Num[0]]; iflpic_name = spptr->solpic_name; flptr0->flpic_index = spptr->solpic_index + pos; flptr0->flpic_hpos = spptr->solpic_hpos + HPos[i]; flptr0->flpic_hsize = spptr->solpic_hsize; flptr0->flpic_hpos2 = flptr0->flpic_hpos + flptr0->flpic_hsize - 1; flptr0->flpic_vpos = spptr->solpic_vpos + VPos[i]; flptr0->flpic_vsize = spptr->solpic_vsize; flptr0->flpic_vpos2 = flptr0->flpic_vpos + flptr0->flpic_vsize - 1; } } // adjust problem parameters Num[0] = Num_tot; NumCo[0] = 2 * (Num_tot - 1); HSize[0] = HSize_tot; VSize[0] = VSize_tot; MaxHPos[0] = HSize_tot - 1; MaxVPos[0] = VSize_tot - 1; PageArea[0] = PageArea_tot; PageAspectRatio[0] = PageAspectRatio_tot; MaxClockTicks[0] = MaxClockTicks_tot; // set max. time } #endif static double min2(double x1, double x2) { return ( x1 < x2 ? x1 : x2 ); } // static double // max2(double x1, double x2) // { // return ( x1 > x2 ? x1 : x2 ); // } static double min3(double x1, double x2, double x3) { return ( x1 < x2 ? ( x1 < x3 ? x1 : x3 ) : ( x2 < x3 ? x2 : x3 ) ); } static double max3(double x1, double x2, double x3) { return ( x1 > x2 ? ( x1 > x3 ? x1 : x3 ) : ( x2 > x3 ? x2 : x3 ) ); } // //========================================================================= // // static void // // ReadValue(const char *scanfstr, void *x, const char *printfstr, ...); // // // // Hilfsfunktion zum Einlesen eines Wertes von stdin. // // scanfstr = Formatstring f?r scanf() // // x = Zeiger auf den einzulesenden Wert // // printfstr = Formatstring f?r printf() // // ... = eventuelle Parameter f?r printf() // //========================================================================= // // static void // ReadValue(const char *scanfstr, void *x, const char *printfstr, ...) // { // #define RVBUFLEN 121 // char buf[RVBUFLEN]; // // va_list arglist; // // fflush(stdout); // va_start(arglist, printfstr); // vprintf(printfstr, arglist); // va_end(arglist); // fflush(stdout); // // fflush(stdin); // fgets(buf, RVBUFLEN, stdin); // sscanf(buf, scanfstr, x); // fflush(stdin); // }