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;
13 static bool
14 possibly_eq(double const a, double const b)
15 {
16 return abs(a - b) < 1e-13;
17 }
19 static bool
20 possibly_le(double const a, double const b)
21 {
22 return a - b < 1e-13;
23 }
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 }
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 }
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 }
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 }
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 }
116 int main()
117 {
118 srand(time(NULL));
120 /* Ensure that the program doesn't run for more than 30 seconds. */
121 alarm(30);
123 utest_start("removeRectangleOverlap(zero gaps)");
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 }
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
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
293 return ( utest_end()
294 ? EXIT_SUCCESS
295 : EXIT_FAILURE );
296 }
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 :