examples/parallel_for/polygon_overlay/polymain.cpp

   1 /*
   2     Copyright (c) 2005-2019 Intel Corporation
   3
   4     Licensed under the Apache License, Version 2.0 (the "License");
   5     you may not use this file except in compliance with the License.
   6     You may obtain a copy of the License at
   7
   8         http://www.apache.org/licenses/LICENSE-2.0
   9
  10     Unless required by applicable law or agreed to in writing, software
  11     distributed under the License is distributed on an "AS IS" BASIS,
  12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13     See the License for the specific language governing permissions and
  14     limitations under the License.
  15 */
  16
  17 // Polygon overlay
  18 //
  19 // Don't want warnings about deprecated sscanf, getenv
  20 #ifndef _CRT_SECURE_NO_DEPRECATE
  21 #define _CRT_SECURE_NO_DEPRECATE
  22 #endif
  23 #define _MAIN_C_ 1
  24 #include <iostream>
  25 #include <iomanip>
  26 #include <algorithm>
  27 #include <cstring>
  28
  29 #include "tbb/tick_count.h"
  30 #include "tbb/task_scheduler_init.h"
  31 #include "pover_global.h"
  32 #include "polyover.h"
  33 #include "pover_video.h"
  34 #include "polymain.h"
  35
  36 using namespace std;
  37
  38 #if _DEBUG
  39 const char *faceNames[] = { "North", "East", "South", "West" };
  40 #endif
  41
  42 /**
  43 **/
  44 int main( int argc, char **argv) {
  45     pover_video poly;
  46     poly.threaded = true;
  47     gVideo = &poly;
  48
  49     if(!initializeVideo(argc, argv)) {
  50         return 1;
  51     }
  52
  53     gIsGraphicalVersion = poly.graphic_display();
  54     if(argc > 1) {
  55         if(!ParseCmdLine(argc, argv)) {
  56             if(gIsGraphicalVersion) rt_sleep(10000);
  57             // if graphical, we haven't opened the console window so all the error messages we
  58             // so carefully wrote out disappeared into the ether.  :(
  59             exit(1);
  60         }
  61     }
  62
  63     if(gCsvFilename != NULL) {
  64 #define BUFLEN 1000
  65         std::string fname_buf = gCsvFilename;
  66         fname_buf += ".csv";
  67         gCsvFile.open(fname_buf.c_str());
  68     }
  69
  70     // we have gMapXSize and gMapYSize determining the number of "squares"
  71     // we have g_xwinsize and g_ywinsize the total size of the window
  72     // we also have BORDER_SIZE the size of the border between maps
  73     // we need to determine
  74     //      g_polyBoxSize -- the number of pixels on each size of each square
  75
  76     if(gIsGraphicalVersion) {
  77         int xpixelsPerMap = (g_xwinsize - 4*BORDER_SIZE) / 3;  // three maps, with borders between and outside
  78         gMapXSize = xpixelsPerMap;   // make the boxes one per pixel
  79         gPolyXBoxSize = xpixelsPerMap / gMapXSize;
  80         int ypixelsPerMap = (g_ywinsize - 2*BORDER_SIZE);       // one map vertically
  81         gMapYSize = ypixelsPerMap;   // one pixel per box, rather.
  82
  83         gPolyYBoxSize = ypixelsPerMap / gMapYSize;
  84         if((gPolyXBoxSize == 0) || (gPolyYBoxSize == 0)) {
  85             cout << "The display window is not large enough to show the maps" << std::endl;
  86             int minxSize = 4*BORDER_SIZE + 3*gMapXSize;
  87             int minySize = 2*BORDER_SIZE + gMapYSize;
  88             cout << "  Should be at least " << minxSize << " x " << minySize << "." << std::endl;
  89             return 1;
  90         }
  91         map2XLoc = 2*BORDER_SIZE + gMapXSize * gPolyXBoxSize;
  92         maprXLoc = 3*BORDER_SIZE + 2 * gMapXSize * gPolyXBoxSize;
  93
  94     }
  95     else {  // not gIsGraphicalVersion
  96         // gMapXSize, gMapYSize, gNPolygons defined in pover_global.h
  97     }
  98
  99     // create two polygon maps
 100     SetRandomSeed(gMyRandomSeed);  // for repeatability
 101
 102     gVideo->main_loop();
 103 }
 104
 105 void Usage(int argc, char **argv) {
 106     char *cmdTail = strrchr(*argv, '\\');
 107     if(cmdTail == NULL)  {
 108         cmdTail = *argv;
 109     }
 110     else {
 111         cmdTail++;
 112     }
 113     cout << cmdTail << " [threads[:threads2]] [--polys npolys] [--size nnnxnnn] [--seed nnn]" << std::endl;
 114     cout << "Create polygon maps and overlay them." << std::endl << std::endl;
 115     cout << "Parameters:" << std::endl;
 116     cout << "   threads[:threads2] - number of threads to run" << std::endl;
 117     cout << "   --polys npolys - number of polygons in each map" << std::endl;
 118     cout << "   --size nnnxnnn - size of each map (X x Y)" << std::endl;
 119     cout << "   --seed nnn - initial value of random number generator" << std::endl;
 120     cout << "   --csv filename - write timing data to CSV-format file" << std::endl;
 121     cout << "   --grainsize n - set grainsize to n" << std::endl;
 122     cout << "   --use_malloc - allocate polygons with malloc instead of scalable allocator" << std::endl;
 123     cout << std::endl;
 124     cout << "npolys must be smaller than the size of the map" << std::endl;
 125     cout << std::endl;
 126     exit(1);
 127 }
 128
 129 bool ParseCmdLine(int argc, char **argv ) {
 130     bool error_found = false;
 131     bool nPolysSpecified = false;
 132     bool nMapSizeSpecified = false;
 133     bool nSeedSpecified = false;
 134     bool csvSpecified = false;
 135     bool grainsizeSpecified = false;
 136     bool mallocSpecified = false;
 137     int origArgc = argc;
 138     char** origArgv = argv;
 139     unsigned int newnPolygons = gNPolygons;
 140     unsigned int newSeed = gMyRandomSeed;
 141     unsigned int newX = gMapXSize;
 142     unsigned int newY = gMapYSize;
 143     unsigned int newGrainSize = gGrainSize;
 144     argc--; argv++;
 145     if(argc > 0 && isdigit((*argv)[0])) {
 146         // first argument is one or two numbers, specifying how mny threads to run
 147         char* end; gThreadsHigh = gThreadsLow = (int)strtol(argv[0],&end,0);
 148         switch( *end) {
 149             case ':': gThreadsHigh = (int)strtol(end+1,0,0); break;
 150             case '\0': break;
 151             default: cout << "Unexpected character in thread specifier: " << *end << std::endl; break;
 152         }
 153         if(gThreadsLow > gThreadsHigh) {
 154             int t = gThreadsLow;
 155             gThreadsLow = gThreadsHigh;
 156             gThreadsHigh = t;
 157         }
 158         argv++; argc--;
 159     }
 160     while(argc > 0) {
 161         // format 1: --size nnnxnnn, where nnn in {0 .. 9}+ -- size of map in "squares"
 162         if(!strncmp("--size", *argv, (size_t)6)) {
 163             if(nMapSizeSpecified) {
 164                 cout << " Error: map size multiply specified" << std::endl;
 165                 error_found = true;
 166             }
 167             else  {
 168                 argv++; argc--;
 169                 if(argc == 0) {
 170                     error_found = true;
 171                     cout << " Error: --size must have a value" << std::endl;
 172                 }
 173                 if(strchr(*argv, 'x') != strrchr(*argv,'x')) {
 174                     // more than one 'x'
 175                     cout << "Error: map size should be nnnxnnn (" << *argv << ")" << std::endl;
 176                     error_found = true;
 177                 }
 178                 else {
 179                     int rval;
 180                     rval = sscanf(*argv, "%ux%u", &newX, &newY);
 181                     if(rval != 2) {
 182                         cout << "Error parsing map size (format should be nnnxnnn (" << *argv << ")" << std::endl;
 183                         error_found = true;
 184                     }
 185                     if(newX == 0 || newY == 0) {
 186                         cout << "Error: size of map should be greater than 0 (" << *argv << ")" << std::endl;
 187                         error_found = true;
 188                     }
 189                 }
 190             }
 191             argc--; argv++;
 192         }
 193         // format 2: --seed nnn -- initial random number seed
 194         else if(!strncmp("--seed", *argv, (size_t)6)) {
 195             argv++; argc--;
 196             if(nSeedSpecified) {
 197                 cout << "Error: new seed multiply specified" << std::endl;
 198                 error_found = true;
 199             }
 200             else {
 201                 nSeedSpecified = true;
 202                 int rtval = sscanf(*argv, "%u", &newSeed);
 203                 if(rtval == 0) {
 204                     cout << "Error: --seed should be an unsigned number (instead of " << *argv << ")" << std::endl;
 205                     error_found = true;
 206                 }
 207             }
 208             argv++; argc--;
 209         }
 210         // format 3: --polys n[n] -- number of polygons in each map
 211         else if(!strncmp("--polys", *argv, (size_t)7)) {
 212             //unsigned int newnPolygons;
 213             argv++; argc--;
 214             if(nPolysSpecified) {
 215                 cout << "Error: number of polygons multiply-specified" << std::endl;
 216                 error_found = true;
 217             }else {
 218                 int rtval = sscanf(*argv, "%u", &newnPolygons);
 219                 if(newnPolygons == 0) {
 220                     cout << "Error: number of polygons must be greater than 0 (" << *argv << ")" << std::endl;
 221                 }
 222             }
 223             argv++; argc--;
 224         }
 225         // format 4: --csv <fileroot> -- name of CSV output file ("xxx" for "xxx.csv")
 226         else if(!strncmp("--csv", *argv, (size_t)5)) {
 227             argv++; argc--;
 228             if(csvSpecified) {
 229                 cout << "Error: Multiple specification of CSV file" << std::endl;
 230                 error_found = true;
 231             }
 232             else {
 233                 gCsvFilename = *argv;
 234                 argv++; argc--;
 235                 csvSpecified = true;
 236             }
 237         }
 238         else if(!strncmp("--grainsize", *argv, (size_t)11)) {
 239             argv++; argc--;
 240             if(grainsizeSpecified) {
 241                 cout << "Error: Multiple specification of grainsize" << std::endl;
 242                 error_found = true;
 243             }
 244             else {
 245                 int grval = sscanf(*argv, "%u", &newGrainSize);
 246                 grainsizeSpecified = true;
 247                 if(newGrainSize == 0) {
 248                     cout << "Error: grainsize must be greater than 0" << std::endl;
 249                     error_found = true;
 250                 }
 251             }
 252             argv++; argc--;
 253         }
 254         else if(!strncmp("--use_malloc", *argv, (size_t)12)) {
 255             argv++; argc--;
 256             if(mallocSpecified) {
 257                 cout << "Error: --use_malloc multiply-specified" << std::endl;
 258                 error_found = true;
 259             }
 260             else {
 261                 mallocSpecified = true;
 262                 gMBehavior = UseMalloc;
 263             }
 264         }
 265         else {
 266             cout << "Error: unrecognized argument: " << *argv << std::endl;
 267             error_found = true;
 268             argv++; argc--;
 269         }
 270     }
 271     if(!error_found) {
 272         if(newX * newY < newnPolygons) {
 273             error_found = true;
 274             cout << "Error: map size should not be smaller than the number of polygons (gNPolygons = " << newnPolygons << ", map size " << newX << "x" << newY << ")" << std::endl;
 275         }
 276     }
 277     if(!error_found) {
 278         gMapXSize = newX;
 279         gMapYSize = newY;
 280         gNPolygons = newnPolygons;
 281         gMyRandomSeed = newSeed;
 282         gGrainSize = (int)newGrainSize;
 283     }
 284     else {
 285         Usage(origArgc, origArgv);
 286     }
 287     return !error_found;
 288 }
 289
 290 // create a polygon map with at least gNPolygons polygons.
 291 // Usually more than gNPolygons polygons will be generated, because the
 292 // process of growing the polygons results in holes.
 293 bool GenerateMap(Polygon_map_t **newMap, int xSize, int ySize, int gNPolygons, colorcomp_t maxR, colorcomp_t maxG, colorcomp_t maxB) {
 294     bool error_found = false;
 295     int  *validPolys;
 296     int  *validSide;
 297     int maxSides;
 298     RPolygon *newPoly;
 299
 300     if(xSize <= 0) {
 301         cout << "xSize (" << xSize << ") should be > 0." << std::endl;
 302         error_found = true;
 303     }
 304     if(ySize <= 0) {
 305         cout << "ySize (" << ySize << ") should be > 0." << std::endl;
 306         error_found = true;
 307     }
 308     if(gNPolygons > (xSize * ySize)) {
 309         cout << "gNPolygons (" << gNPolygons << ") should be less than " << (xSize * ySize) << std::endl;
 310         error_found = true;
 311     }
 312     if(error_found) return false;
 313     // the whole map is [xSize x ySize] squares
 314     // the way we create the map is to
 315     //    1) pick nPolygon discrete squares on an [xSize x ySize] grid
 316     //    2) while there are unused squares on the grid
 317     //        3) pick a polygon with a side that has unused squares on a side
 318     //        4) expand the polygon by 1 to occupy the unused squares
 319     //
 320     // Continue until every square on the grid is occupied by a polygon
 321     int *tempMap;
 322     tempMap = (int *)malloc(xSize * ySize * sizeof(int));
 323     for(int i=0;i < xSize; i++) {
 324         for(int j=0;j < ySize; j++) {
 325             tempMap[i*ySize + j] = 0;
 326         }
 327     }
 328
 329     // *newMap = new vector<RPolygon>;
 330     *newMap = new Polygon_map_t;
 331     (*newMap)->reserve(gNPolygons + 1);  // how much bigger does this need to be on average?
 332     (*newMap)->push_back(RPolygon(0,0,xSize-1, ySize-1));
 333     for(int i=0; i < gNPolygons; i++) {
 334         int nX;
 335         int nY;
 336         do {    // look for an empty square.
 337             nX = NextRan(xSize);
 338             nY = NextRan(ySize);
 339         } while(tempMap[nX * ySize + nY] != 0);
 340         int nR = (maxR * NextRan(1000)) / 999;
 341         int nG = (maxG * NextRan(1000)) / 999;
 342         int nB = (maxB * NextRan(1000)) / 999;
 343         (*newMap)->push_back(RPolygon(nX,nY,nX,nY,nR,nG,nB));
 344         tempMap[nX * ySize + nY] = i+1;     // index of this polygon + 1
 345     }
 346     // now have to grow polygons to fill the space.
 347     validPolys = (int *)malloc(4*gNPolygons * sizeof(int));
 348     validSide = (int *)malloc(4*gNPolygons * sizeof(int));
 349     for(int i=0;i<gNPolygons;i++) {
 350         validPolys[4*i] = validPolys[4*i + 1] = validPolys[4*i + 2] = validPolys[4*i + 3] = i + 1;
 351         validSide[4*i] = NORTH_SIDE;
 352         validSide[4*i+1] = EAST_SIDE;
 353         validSide[4*i+2] = SOUTH_SIDE;
 354         validSide[4*i+3] = WEST_SIDE;
 355     }
 356     maxSides = 4*gNPolygons;
 357     while(maxSides > 0) {
 358         int indx = NextRan(maxSides);
 359         int polyIndx = validPolys[indx];
 360         int checkSide = validSide[indx];
 361         int xlow, xhigh, ylow, yhigh;
 362         int xlnew, xhnew, ylnew, yhnew;
 363         (**newMap)[polyIndx].get(&xlow,&ylow,&xhigh,&yhigh);
 364         xlnew = xlow;
 365         xhnew = xhigh;
 366         ylnew = ylow;
 367         yhnew = yhigh;
 368         // can this polygon be expanded along the chosen side?
 369         switch(checkSide) {
 370         case NORTH_SIDE:
 371             // y-1 from xlow to xhigh
 372             ylow = yhigh = (ylow - 1);
 373             ylnew--;
 374             break;
 375         case EAST_SIDE:
 376             // x+1 from ylow to yhigh
 377             xlow = xhigh = (xhigh + 1);
 378             xhnew++;
 379             break;
 380         case SOUTH_SIDE:
 381             // y+1 from xlow to xhigh
 382             ylow = yhigh = (yhigh+1);
 383             yhnew++;
 384             break;
 385         case WEST_SIDE:
 386             // x-1 from ylow to yhigh
 387             xlow = xhigh = (xlow - 1);
 388             xlnew--;
 389             break;
 390         }
 391         bool okay_to_extend = !(((xlow < 0) || (xlow >= xSize)) || ((ylow < 0) || (ylow >= ySize)));
 392         for(int ii = xlow; (ii <= xhigh) && okay_to_extend; ii++) {
 393             for(int jj=ylow; (jj <= yhigh) && okay_to_extend; jj++) {
 394                 okay_to_extend = tempMap[ii*ySize + jj] == 0;
 395             }
 396         }
 397         if(okay_to_extend) {
 398             (**newMap)[polyIndx].set(xlnew,ylnew,xhnew,yhnew);
 399             for(int ii = xlow; ii <= xhigh; ii++) {
 400                 for(int jj=ylow; jj <= yhigh && okay_to_extend; jj++) {
 401                     tempMap[ii*ySize + jj] = polyIndx;
 402                 }
 403             }
 404         }
 405         else {
 406             // once we cannot expand along a side, we will never be able to; remove from the list.
 407             for(int i=indx + 1; i < maxSides; i++) {
 408                 validPolys[i-1] = validPolys[i];
 409                 validSide[i-1] = validSide[i];
 410             }
 411             maxSides--;
 412         }
 413     }
 414
 415     // Once no polygons can be grown, look for unused squares, and fill them with polygons.
 416     for(int j=0;j<ySize;j++) {
 417         for(int i=0;i<xSize;i++) {
 418             if(tempMap[i*ySize+j] == 0) {
 419                 // try to grow in the x direction, then the y direction
 420                 int ilen = i;
 421                 int jlen = j;
 422                 while(ilen < (xSize - 1) && tempMap[(ilen+1)*ySize + jlen] == 0) {
 423                     ilen++;
 424                 }
 425                 bool yok = true;
 426                 while(yok && jlen < (ySize - 1)) {
 427                     for(int ii = i; ii <= ilen && yok; ii++) {
 428                         yok = (tempMap[ii*ySize + jlen + 1] == 0);
 429                     }
 430                     if(yok) {
 431                         jlen++;
 432                     }
 433                 }
 434
 435                 // create new polygon and push it on our list.
 436                 int nR = (maxR * NextRan(1000)) / 999;
 437                 int nG = (maxG * NextRan(1000)) / 999;
 438                 int nB = (maxB * NextRan(1000)) / 999;
 439                 (*newMap)->push_back(RPolygon(i,j,ilen,jlen,nR,nG,nB));
 440                 gNPolygons++;
 441                 for(int ii=i; ii<=ilen;ii++) {
 442                     for(int jj=j;jj<=jlen;jj++) {
 443                         tempMap[ii*ySize + jj] = gNPolygons;
 444                     }
 445                 }
 446             }
 447         }
 448     }
 449
 450 #if _DEBUG
 451     if(!gIsGraphicalVersion) {
 452         cout << std::endl << "Final Map:" << std::endl;
 453         for(int j=0; j < ySize; j++ ) {
 454             cout << "Row " << setw(2) << j << ":";
 455             for(int i=0;i<xSize;i++) {
 456                 int it = tempMap[i*ySize + j];
 457                 if(it<10) {
 458                     cout << setw(2) << it;
 459                 }
 460                 else {
 461                     char ct = (int)'a' + it - 10;
 462                     cout << " " << ct;
 463                 }
 464             }
 465             cout << std::endl;
 466         }
 467     }
 468 #endif  // _DEBUG
 469     free(tempMap);
 470     free(validPolys);
 471     free(validSide);
 472     return true;
 473 }
 474
 475 void CheckPolygonMap(Polygon_map_t *checkMap) {
 476 #define indx(i,j) (i*gMapYSize + j)
 477 #define rangeCheck(str,n,limit) if(((n)<0)||((n)>=limit)) {cout << "checkMap error: " << str << " out of range (" << n << ")" << std::endl;anError=true;}
 478 #define xRangeCheck(str,n) rangeCheck(str,n,gMapXSize)
 479 #define yRangeCheck(str,n) rangeCheck(str,n,gMapYSize)
 480     // The first polygon is the whole map.
 481     bool anError = false;
 482     int *cArray;
 483     if(checkMap->size() <= 0) {
 484         cout << "checkMap error: no polygons in map" << std::endl;
 485         return;
 486     }
 487     // mapXhigh and mapYhigh are inclusive, that is, if the map is 5x5, those values would be 4.
 488     int mapXhigh, mapYhigh, mapLowX, mapLowY;
 489     int gMapXSize, gMapYSize;
 490     (*checkMap)[0].get(&mapLowX, &mapLowY, &mapXhigh, &mapYhigh);
 491     if((mapLowX !=0) || (mapLowY != 0)) {
 492         cout << "checkMap error: map origin not (0,0) (X=" << mapLowX << ", Y=" << mapLowY << ")" << std::endl;
 493         anError = true;
 494     }
 495     if((mapXhigh < 0) || (mapYhigh < 0)) {
 496         cout << "checkMap error: no area in map (X=" << mapXhigh << ", Y=" << mapYhigh << ")" << std::endl;
 497         anError = true;
 498     }
 499     if(anError) return;
 500     // bounds for array.
 501     gMapXSize = mapXhigh + 1;
 502     gMapYSize = mapYhigh + 1;
 503     cArray = (int *)malloc(sizeof(int)*(gMapXSize*gMapYSize));
 504
 505     for(int i=0; i<gMapXSize; i++) {
 506         for(int j=0; j< gMapYSize; j++) {
 507             cArray[indx(i,j)] = 0;
 508         }
 509     }
 510
 511     int xlow, xhigh, ylow, yhigh;
 512     for(int p=1; p < int(checkMap->size()) && !anError; p++) {
 513         (*checkMap)[p].get(&xlow, &ylow, &xhigh, &yhigh);
 514         xRangeCheck("xlow", xlow);
 515         yRangeCheck("ylow", ylow);
 516         xRangeCheck("xhigh", xhigh);
 517         yRangeCheck("yhigh", yhigh);
 518         if(xlow>xhigh) {
 519             cout << "checkMap error: xlow > xhigh (" << xlow << "," << xhigh << ")" << std::endl;
 520             anError = true;
 521         }
 522         if(ylow>yhigh) {
 523             cout << "checkMap error: ylow > yhigh (" << ylow << "," << yhigh << ")" << std::endl;
 524             anError = true;
 525         }
 526         for(int ii = xlow; ii <= xhigh; ii++) {
 527             for(int jj = ylow; jj <= yhigh; jj++) {
 528                 if(cArray[indx(ii,jj)] != 0) {
 529                     cout << "checkMap error: polygons " << cArray[indx(ii,jj)] << " and " << p << " intersect" << std::endl;
 530                     anError = true;
 531                 }
 532                 cArray[indx(ii,jj)] = p;
 533             }
 534         }
 535     }
 536     for(int ii=0; ii < gMapXSize; ii++) {
 537         for(int jj=0; jj < gMapYSize; jj++) {
 538             if(cArray[indx(ii,jj)] == 0) {
 539                 cout << "checkMap error: block(" << ii << ", " << jj << ") not in any polygon" << std::endl;
 540                 anError = true;
 541             }
 542         }
 543     }
 544     free(cArray);
 545 }
 546
 547 bool CompOnePolygon(RPolygon &p1, RPolygon &p2) {
 548     int xl1, xh1, yl1, yh1;
 549     int xl2, xh2, yl2, yh2;
 550     p1.get(&xl1, &yl1, &xh1, &yh1);
 551     p2.get(&xl2, &yl2, &xh2, &yh2);
 552     if(yl1>yl2) return true;
 553     if(yl1<yl2) return false;
 554     return (xl1 > xl2);
 555 }
 556
 557 bool PolygonsEqual(RPolygon *p1, RPolygon *p2) {
 558     int xl1, xh1, yl1, yh1;
 559     int xl2, xh2, yl2, yh2;
 560     p1->get(&xl1, &yl1, &xh1, &yh1);
 561     p2->get(&xl2, &yl2, &xh2, &yh2);
 562     return ((xl1 == xl2) && (yl1==yl2) && (xh1 == xh2) && (yh1 == yh2));
 563 }
 564
 565 bool ComparePolygonMaps(Polygon_map_t *map1, Polygon_map_t *map2) {
 566     // create two new polygon maps, copy the pointers from the original to these.
 567     // we have to skip the first polygon, which is the size of the whole map
 568     Polygon_map_t *t1, *t2;
 569     bool is_ok = true;
 570     t1 = new Polygon_map_t;
 571     t1->reserve(map1->size());
 572     for(unsigned int i=1;i<map1->size(); i++) {
 573         t1->push_back(map1->at(i));
 574     }
 575     t2 = new Polygon_map_t;
 576     t2->reserve(map2->size());
 577     for(unsigned int i=1;i<map2->size();i++) {
 578         t2->push_back(map2->at(i));
 579     }
 580     // sort the two created maps by (xlow, ylow)
 581     sort(t1->begin(), t1->end());
 582     sort(t2->begin(), t2->end());
 583     // compare each element of both maps.
 584     if(t1->size() != t2->size()) {
 585         cout << "Error: maps not the same size ( " << int(t1->size()) << " vs " << int(t2->size()) << ")." << std::endl;
 586     }
 587     int maxSize = (int)((t1->size() < t2->size()) ? t1->size() : t2->size());
 588     for(int i=0; i < maxSize; i++) {
 589         if(!PolygonsEqual(&((*t1)[i]), &((*t2)[i]))) {
 590             cout << "Error: polygons unequal (" << (*t1)[i] << " vs " << (*t2)[i] << std::endl;
 591             is_ok = false;
 592         }
 593     }
 594     delete t1;
 595     delete t2;
 596     return is_ok;
 597 }
 598
 599 void SetRandomSeed(int newSeed) {
 600     srand((unsigned)newSeed);
 601 }
 602
 603 int NextRan(int n) {
 604     // assert(n > 1);
 605     // if we are given 1, we will just return 0
 606     //assert(n < RAND_MAX);
 607     int rrand = rand() << 15 | rand();
 608     if(rrand < 0) rrand = -rrand;
 609     return rrand % n;
 610 }
 611
 612 std::ostream& operator<<(std::ostream& s, const RPolygon &p) {
 613     int xl, yl, xh, yh;
 614     p.get(&xl, &yl, &xh, &yh);
 615     return s << "[(" << xl << "," << yl << ")-(" << xh << "," << yh << ")] ";
 616 }