src/removeoverlap/remove_rectangle_overlap-test.cpp

   1 #include "removeoverlap/remove_rectangle_overlap.h"
   2 #include <unistd.h>  // for alarm()
   3 #include <time.h>  // for srand seed and clock().
   4 #include <glib/gmacros.h>
   5 #include <glib/gmem.h>
   6 #include <cstdlib>
   7 #include <cmath>
   8 #include "removeoverlap/generate-constraints.h"
   9 #include "utest/utest.h"
  10 using std::abs;
  11 using std::rand;
  12
  13 static bool
  14 possibly_eq(double const a, double const b)
  15 {
  16     return abs(a - b) < 1e-13;
  17 }
  18
  19 static bool
  20 possibly_le(double const a, double const b)
  21 {
  22     return a - b < 1e-13;
  23 }
  24
  25 static void
  26 show_rects(unsigned const n_rects, double const rect2coords[][4])
  27 {
  28     for (unsigned i = 0; i < n_rects; ++i) {
  29         printf("{%g, %g, %g, %g},\n",
  30                rect2coords[i][0],
  31                rect2coords[i][1],
  32                rect2coords[i][2],
  33                rect2coords[i][3]);
  34     }
  35 }
  36
  37 /**
  38  * Returns the signum of x, but erring towards returning 0 if x is "not too far" from 0.  ("Not too
  39  * far from 0" means [-0.9, 0.9] in current version.)
  40  */
  41 static int
  42 sgn0(double const x)
  43 {
  44     if (x <= -0.9) {
  45         return -1;
  46     } else if (0.9 <= x) {
  47         return 1;
  48     } else {
  49         return 0;
  50     }
  51 }
  52
  53 static void
  54 test_case(unsigned const n_rects, double const rect2coords[][4])
  55 {
  56     Rectangle **rs = (Rectangle **) g_malloc(sizeof(Rectangle*) * n_rects);
  57     for (unsigned i = 0; i < n_rects; ++i) {
  58         rs[i] = new Rectangle(rect2coords[i][0],
  59                               rect2coords[i][1],
  60                               rect2coords[i][2],
  61                               rect2coords[i][3]);
  62     }
  63     removeRectangleOverlap(rs, n_rects, 0.0, 0.0);
  64     for (unsigned i = 0; i < n_rects; ++i) {
  65         UTEST_ASSERT(possibly_eq(rs[i]->width(), (rect2coords[i][1] -
  66                                                   rect2coords[i][0]  )));
  67         UTEST_ASSERT(possibly_eq(rs[i]->height(), (rect2coords[i][3] -
  68                                                    rect2coords[i][2]  )));
  69         for (unsigned j = 0; j < i; ++j) {
  70             if (!( possibly_le(rs[i]->getMaxX(), rs[j]->getMinX()) ||
  71                    possibly_le(rs[j]->getMaxX(), rs[i]->getMinX()) ||
  72                    possibly_le(rs[i]->getMaxY(), rs[j]->getMinY()) ||
  73                    possibly_le(rs[j]->getMaxY(), rs[i]->getMinY())   )) {
  74                 show_rects(n_rects, rect2coords);
  75                 char buf[32];
  76                 sprintf(buf, "[%u],[%u] of %u", j, i, n_rects);
  77                 utest__fail("Found overlap among ", buf, " rectangles");
  78             }
  79         }
  80
  81         /* Optimality test. */
  82         {
  83             bool found_block[2] = {false, false};
  84             int const desired_movement[2] = {sgn0(rect2coords[i][0] - rs[i]->getMinX()),
  85                                              sgn0(rect2coords[i][2] - rs[i]->getMinY())};
  86             for (unsigned j = 0; j < n_rects; ++j) {
  87                 if (j == i)
  88                     continue;
  89                 for (unsigned d = 0; d < 2; ++d) {
  90                     if ( ( desired_movement[d] < 0
  91                            ? abs(rs[j]->getMaxD(d) - rs[i]->getMinD(d))
  92                            : abs(rs[i]->getMaxD(d) - rs[j]->getMinD(d)) )
  93                          < .002 ) {
  94                         found_block[d] = true;
  95                     }
  96                 }
  97             }
  98
  99             for (unsigned d = 0; d < 2; ++d) {
 100                 if ( !found_block[d]
 101                      && desired_movement[d] != 0 ) {
 102                     show_rects(n_rects, rect2coords);
 103                     char buf[32];
 104                     sprintf(buf, "%c in rectangle [%u] of %u", "XY"[d], i, n_rects);
 105                     utest__fail("Found clear non-optimality in ", buf, " rectangles");
 106                 }
 107             }
 108         }
 109     }
 110     for (unsigned i = 0; i < n_rects; ++i) {
 111         delete rs[i];
 112     }
 113     g_free(rs);
 114 }
 115
 116 int main()
 117 {
 118     srand(time(NULL));
 119
 120     /* Ensure that the program doesn't run for more than 30 seconds. */
 121     alarm(30);
 122
 123     utest_start("removeRectangleOverlap(zero gaps)");
 124
 125     /* Derived from Bulia's initial test case.  This used to crash. */
 126     UTEST_TEST("eg0") {
 127         double case0[][4] = {
 128             {-180.5, 69.072, 368.071, 629.071},
 129             {99.5, 297.644, 319.5, 449.071},
 130             {199.5, 483.358, 450.929, 571.929},
 131             {168.071, 277.644, 462.357, 623.357},
 132             {99.5, 99.751, 479.5, 674.786},
 133             {-111.929, 103.358, 453.786, 611.929},
 134             {-29.0714, 143.358, 273.786, 557.643},
 135             {122.357, 269.072, 322.357, 531.929},
 136             {256.643, 357.644, 396.643, 520.5}
 137         };
 138         test_case(G_N_ELEMENTS(case0), case0);
 139     }
 140
 141 #if 0 /* This involves a zero-height rect, so we'll ignore for the moment. */
 142     UTEST_TEST("eg1") {
 143         double case1[][4] = {
 144             {5, 14, 9, 14},
 145             {6, 13, 6, 8},
 146             {11, 12, 5, 5},
 147             {5, 8, 5, 7},
 148             {12, 14, 14, 15},
 149             {12, 14, 1, 14},
 150             {1, 15, 14, 15},
 151             {5, 6, 13, 13}
 152         };
 153         test_case(G_N_ELEMENTS(case1), case1);
 154     }
 155 #endif
 156
 157     /* The next few examples used to result in overlaps. */
 158     UTEST_TEST("eg2") {
 159         double case2[][4] = {
 160             {3, 4, 6, 13},
 161             {0, 1, 0, 5},
 162             {0, 4, 1, 6},
 163             {2, 5, 0, 6},
 164             {0, 10, 9, 13},
 165             {5, 11, 1, 13},
 166             {1, 2, 3, 8}
 167         };
 168         test_case(G_N_ELEMENTS(case2), case2);
 169     }
 170
 171     UTEST_TEST("eg3") {
 172         double case3[][4] = {
 173             {0, 5, 0, 3},
 174             {1, 2, 1, 3},
 175             {3, 7, 4, 7},
 176             {0, 9, 4, 5},
 177             {3, 7, 0, 3}
 178         };
 179         test_case(G_N_ELEMENTS(case3), case3);
 180     }
 181
 182     UTEST_TEST("eg4") {
 183         double case4[][4] = {
 184             {0, 1, 2, 3},
 185             {0, 4, 0, 4},
 186             {1, 6, 0, 4},
 187             {2, 3, 4, 5},
 188             {0, 5, 4, 6}
 189         };
 190         test_case(G_N_ELEMENTS(case4), case4);
 191     }
 192
 193     UTEST_TEST("eg5") {
 194         double case5[][4] = {
 195             {1, 5, 1, 2},
 196             {1, 6, 5, 7},
 197             {6, 8, 1, 2},
 198             {2, 3, 1, 4},
 199             {5, 8, 2, 6}
 200         };
 201         test_case(G_N_ELEMENTS(case5), case5);
 202     }
 203
 204     /* This one causes overlap in 2005-12-19 04:00 UTC version. */
 205     UTEST_TEST("olap6") {
 206         double case6[][4] = {
 207             {7, 22, 39, 54},
 208             {7, 33, 0, 59},
 209             {3, 26, 16, 56},
 210             {7, 17, 18, 20},
 211             {1, 59, 11, 26},
 212             {19, 20, 13, 49},
 213             {1, 10, 0, 4},
 214             {47, 52, 1, 3}
 215         };
 216         test_case(G_N_ELEMENTS(case6), case6);
 217     }
 218
 219     /* The next two examples caused loops in the version at 2005-12-07 04:00 UTC. */
 220     UTEST_TEST("loop0") {
 221         double loop0[][4] = {
 222             {13, 16, 6, 27},
 223             {0, 6, 0, 12},
 224             {11, 14, 1, 10},
 225             {12, 39, 5, 24},
 226             {14, 34, 4, 7},
 227             {1, 30, 20, 27},
 228             {1, 6, 1, 2},
 229             {19, 28, 10, 24},
 230             {4, 34, 15, 21},
 231             {7, 13, 13, 34}
 232         };
 233         test_case(G_N_ELEMENTS(loop0), loop0);
 234     }
 235
 236     UTEST_TEST("loop1") {
 237         double loop1[][4] = {
 238             {6, 18, 9, 16},
 239             {8, 26, 10, 13},
 240             {3, 10, 0, 14},
 241             {0, 5, 16, 22},
 242             {1, 8, 11, 21},
 243             {1, 5, 0, 13},
 244             {24, 25, 0, 2}
 245         };
 246         test_case(G_N_ELEMENTS(loop1), loop1);
 247     }
 248
 249     UTEST_TEST("loop2") {
 250         double loop2[][4] = {
 251             {16, 22, 9, 16},
 252             {8, 9, 14, 19},
 253             {17, 25, 8, 13},
 254             {10, 26, 26, 29},
 255             {14, 19, 9, 19},
 256             {0, 18, 3, 12},
 257             {7, 8, 14, 22},
 258             {14, 20, 25, 29}
 259         };
 260         test_case(G_N_ELEMENTS(loop2), loop2);
 261     }
 262
 263     /* Random cases of up to 10 rectangles, with small non-neg int coords. */
 264     for (unsigned n = 0; n <= 10; ++n) {
 265         char buf[64];
 266         sprintf(buf, "random ints with %u rectangles", n);
 267         UTEST_TEST(buf) {
 268             unsigned const fld_size = 8 * n;
 269             double (*coords)[4] = (double (*)[4]) g_malloc(n * 4 * sizeof(double));
 270             clock_t const clock_stop = clock() + CLOCKS_PER_SEC;
 271             for (unsigned repeat = (n == 0 ? 1
 272                                     : n == 1 ? 36
 273                                     : (1 << 16)  ); repeat--;) {
 274                 for (unsigned i = 0; i < n; ++i) {
 275                     for (unsigned d = 0; d < 2; ++d) {
 276                         //unsigned const start = rand() % fld_size;
 277                         //unsigned const end = start + rand() % (fld_size - start);
 278                         unsigned const end = 1 + (rand() % (fld_size - 1));
 279                         unsigned const start = rand() % end;
 280                         coords[i][2 * d] = start;
 281                         coords[i][2 * d + 1] = end;
 282                     }
 283                 }
 284                 test_case(n, coords);
 285                 if (clock() >= clock_stop) {
 286                     break;
 287                 }
 288             }
 289             g_free(coords);
 290         }
 291     }
 292
 293     return ( utest_end()
 294              ? EXIT_SUCCESS
 295              : EXIT_FAILURE );
 296 }
 297
 298
 299 /*
 300   Local Variables:
 301   mode:c++
 302   c-file-style:"stroustrup"
 303   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 304   indent-tabs-mode:nil
 305   fill-column:99
 306   End:
 307 */
 308 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :