]> mj.ucw.cz Git - leo.git/blob - lab-bitmaps.c
Labelling: Support for better bitmaps granularity
[leo.git] / lab-bitmaps.c
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <math.h>
5
6 #include <ucw/lib.h>
7 #include <ucw/gary.h>
8
9 #include "leo.h"
10 #include "sym.h"
11 #include "map.h"
12 #include "labeller.h"
13 #include "lab-bitmaps.h"
14 #include "lab-utils.h"
15 #include "lab-evolution.h"
16
17 static void make_bitmap_icon(struct variant *v, struct sym_icon *si);
18 static void make_bitmap_point(struct variant *v, struct sym_point *sp);
19 static void make_bitmap_label(struct variant *v, struct sym_text *text);
20
21 static int overlaps(struct placement *p1, struct placement *p2);
22
23 static struct map_part **get_map_parts(struct placement *p);
24 static struct placement **get_overlapping(struct placement *p);
25
26 double bitmap_granularity = 1;
27
28 int page_width_gran, page_height_gran;
29
30
31 void make_bitmap(struct variant *v, struct symbol *sym)
32 {
33   v->offset_x = v->offset_y = 0;
34
35   switch (sym->type)
36   {
37     case SYMBOLIZER_POINT:
38       make_bitmap_point(v, (struct sym_point *) sym);
39       break;
40     case SYMBOLIZER_ICON:
41       make_bitmap_icon(v, (struct sym_icon *) sym);
42       break;
43     case SYMBOLIZER_TEXT:
44       make_bitmap_label(v, (struct sym_text *) sym);
45       break;
46     default:
47       ASSERT(sym->type != SYMBOLIZER_INVALID);
48   }
49 }
50
51 static void make_bitmap_icon(struct variant *v, struct sym_icon *si)
52 {
53   v->width = si->sir.width + 1;
54   v->height = si->sir.height + 1;
55   v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
56   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
57 }
58
59 static void make_bitmap_point(struct variant *v, struct sym_point *sp)
60 {
61   v->width = v->height = sp->size + 1;
62   v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
63   // FIXME: Okay, memset would be much nicer here
64   for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
65 }
66
67 static void make_bitmap_label(struct variant *v, struct sym_text *text)
68 {
69   int tw = ceil(text->tw);
70   int th = ceil(text->th);
71
72   double rotate_rad = convert_to_rad(text->rotate);
73
74   // Initially, ll = [0; 0], lr = [tw, 0], ul = [0, th], ur = [tw, th]
75   // They could be declared before but should not be initialized in code
76   // as reassigning x-coordinate affects computation of y-cordinate
77   int llx = 0;
78   int lly = 0;
79
80   int lrx = tw * cos(rotate_rad);
81   int lry = tw * sin(rotate_rad);
82
83   int ulx = th * sin(rotate_rad);
84   int uly = th * cos(rotate_rad);
85
86   int urx = tw * cos(rotate_rad) + th * sin(rotate_rad);
87   int ury = tw * sin(rotate_rad) + th * cos(rotate_rad);
88
89   int min_x = min4(llx, lrx, ulx, urx);
90   int min_y = min4(lly, lry, uly, ury);
91   int max_x = max4(llx, lrx, ulx, urx);
92   int max_y = max4(lly, lry, uly, ury);
93
94   v->width = max_x - min_x + 1;
95   v->height = max_y - min_y + 1;
96   v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
97   memset(v->bitmap, 0, v->width * v->height * sizeof(bool));
98
99   for (int i=0; i<th; i++)
100   {
101     for (int j=0; j<tw; j++)
102     {
103       int nx = j*cos(rotate_rad) + i*sin(rotate_rad);
104       int ny = j*sin(rotate_rad) + i*cos(rotate_rad);
105       v->bitmap[(ny-min_y)*v->width + (nx-min_x)] = 1;
106     }
107   }
108 }
109
110 void dump_bitmaps(struct individual *individual)
111 {
112   bool *bitmap = xmalloc(page_width_gran * page_height_gran * sizeof(bool));
113   printf("Bitmap size is %d\n", page_width_gran * page_height_gran);
114   for (int i=0; i<page_height_gran; i++)
115     for (int j=0; j<page_width_gran; j++)
116       bitmap[i*page_width_gran + j] = 0;
117
118   int total = 0;
119   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
120   {
121     if (individual->placements[i].variant_used == -1) continue;
122
123     struct placement *p = &(individual->placements[i]);
124     struct variant *v = NULL;
125
126     switch (p->request->type)
127     {
128       case REQUEST_SEGMENT: ;
129       case REQUEST_POINT: ;
130       case REQUEST_AREA: ;
131         v = &(p->request->variants[p->variant_used]);
132         break;
133       default:
134         ASSERT(p->request->type != REQUEST_INVALID);
135         continue;
136     }
137
138     // FIXME:
139     // if e.g. granularity is 2, p->x = 2.4 and v->width = 4
140     // then <2, 2.5> will be marked as occupied while <4, 4.5> won't be,
141     // though the variant occupies <2.4, 4,4> and therefore occupies much
142     // more of <4, 4.5> than of <2, 2.5>
143     int base_x = p->x * bitmap_granularity;
144     int base_y = p->y * bitmap_granularity;
145     int max_dr = min2(v->height - 1, (page_height - p->y) * bitmap_granularity);
146     int max_dc = min2(v->width - 1, (page_width - p->x) * bitmap_granularity);
147     for (int dr = max2(0, 0-p->y); dr < max_dr; dr++)
148     {
149       for (int dc = max2(0, 0-p->x); dc < max_dc; dc++)
150       {
151         if (v->bitmap[dr * v->width + dc])
152         {
153           if (bitmap[(base_y + dr) * page_width_int + (base_x + dc)]) total += 1;
154           bitmap[(base_y + dr) * page_width_int + (base_x + dc)] = 1;
155         }
156       }
157     }
158   }
159   DEBUG(dbg_overlaps, VERBOSITY_GENERAL, "There were %d collisions during bitmap dump\n", total);
160
161   FILE *fd_dump = fopen("dump.pbm", "w");
162   fprintf(fd_dump, "P1\n");
163   fprintf(fd_dump, "%d %d\n", page_width_gran, page_height_gran);
164   for (int i=0; i<page_height_gran; i++)
165   {
166     for (int j=0; j<page_width_gran; j++)
167     {
168       fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int*bitmap_granularity + j)] ? 1 : 0);
169     }
170     fprintf(fd_dump, "\n");
171   }
172   fclose(fd_dump);
173
174   free(bitmap);
175 }
176
177 static struct map_part **get_map_parts(struct placement *p)
178 {
179   if (p->variant_used < 0) return NULL;
180
181   struct map_part **buffer;
182   GARY_INIT(buffer, 0);
183
184   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Looking for map parts containing placement of request %d, placed at [%.2f; %.2f]\n", p->request->ind, p->x, p->y);
185
186   struct variant v;
187   switch (p->request->type)
188   {
189     case REQUEST_POINT:
190     case REQUEST_SEGMENT:
191     case REQUEST_AREA:
192       v = p->request->variants[p->variant_used];
193       break;
194     default:
195       DEBUG(dbg_map_parts, VERBOSITY_ALL, "Skipping unsupported request type (%d)\n", p->request->type);
196       return NULL;
197   }
198
199   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Bitmap is %d x %d\n", v.width, v.height);
200
201   int x_min = max2(0, p->x) / conf_map_part_width;
202   // CHECK ME: Is rounding needed?
203   int x_max = min2(page_width_int, (p->x + v.width / bitmap_granularity)) / conf_map_part_width;
204   int y_min = max2(0, p->y) / conf_map_part_height;
205   // CHECK ME: Is rounding needed?
206   int y_max = min2(page_height_int, (p->y + v.height / bitmap_granularity)) / conf_map_part_height;
207
208   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
209
210   for (int y=y_min; y<=y_max; y++)
211     for (int x=x_min; x<=x_max; x++)
212     {
213       struct map_part **m = GARY_PUSH(buffer);
214       DEBUG(dbg_map_parts, VERBOSITY_ALL, "Asking for %d of %zu\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
215       *m = p->individual->map[y * num_map_parts_row + x];
216     }
217
218   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Returning %zu map parts potentially containing the symbol\n", GARY_SIZE(buffer));
219
220   return buffer;
221 }
222
223 void update_map_parts_delete(struct placement *p)
224 {
225   struct map_placement *mp = p->map_links;
226   while (mp)
227   {
228     mp->prev_in_map->next_in_map = mp->next_in_map;
229     if (mp->next_in_map)
230       mp->next_in_map->prev_in_map = mp->prev_in_map;
231
232     struct map_placement *tmp = mp;
233     mp = mp->next_in_placement;
234     free(tmp);
235   }
236   p->map_links = NULL;
237 }
238
239 void update_map_parts_create(struct placement *p)
240 {
241   struct map_part **parts = get_map_parts(p);
242   if (parts == NULL) return;
243
244   for (uns i=0; i<GARY_SIZE(parts); i++)
245   {
246     struct map_placement *mp = xmalloc(sizeof(struct map_placement));
247     mp->placement = p;
248     mp->part = parts[i];
249
250     mp->next_in_map = parts[i]->placement->next_in_map;
251     mp->prev_in_map = parts[i]->placement;
252     parts[i]->placement->next_in_map = mp;
253     if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;
254
255     mp->next_in_placement = p->map_links;
256     mp->prev_in_placement = NULL;
257     p->map_links = mp;
258   }
259
260   GARY_FREE(parts);
261 }
262
263 void update_map_parts(struct placement *p)
264 {
265   update_map_parts_delete(p);
266   update_map_parts_create(p);
267 }
268
269 struct placement **get_closure(struct placement *placement)
270 {
271   struct placement **closure;
272   GARY_INIT(closure, 0);
273   bool *chosen = xmalloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
274   for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
275   chosen[placement->request->ind] = 1;
276
277   struct placement **p = GARY_PUSH(closure); *p = placement;
278
279   uns first = 0;
280   while (first < GARY_SIZE(closure))
281   {
282     DEBUG(dbg_breeding, VERBOSITY_ALL, "Iterating, first is %u of current %zu\n", first, GARY_SIZE(closure));
283     struct placement **overlapping = get_overlapping(placement);
284     if (! overlapping) { first++; continue; }
285
286     struct placement **filtered = filter(overlapping, &chosen);
287     DEBUG(dbg_breeding, VERBOSITY_ALL, "There are %zu new overlapping symbols\n", GARY_SIZE(filtered));
288     GARY_FREE(overlapping);
289     overlapping = filtered;
290     for (uns j=0; j<GARY_SIZE(overlapping); j++)
291     {
292       if (! chosen[overlapping[j]->request->ind])
293       {
294         if (overlaps(*p, overlapping[j]))
295         {
296           p = GARY_PUSH(closure); *p = overlapping[j];
297           DEBUG(dbg_breeding, VERBOSITY_ALL, "Adding placement of request %d (in fact at [%.2f; %.2f] of size %d x %d)\n", overlapping[j]->request->ind, overlapping[j]->x, overlapping[j]->y, overlapping[j]->request->variants[overlapping[j]->variant_used].width, overlapping[j]->request->variants[overlapping[j]->variant_used].height);
298           chosen[overlapping[j]->request->ind] = 1;
299         }
300       }
301     }
302     GARY_FREE(overlapping);
303     first++;
304   }
305
306   free(chosen);
307
308   return closure;
309 }
310
311 static struct placement **get_overlapping(struct placement *p)
312 {
313   struct placement **buffer;
314   GARY_INIT(buffer, 0);
315
316   struct map_part **parts = get_map_parts(p);
317   if (! parts) return NULL;
318
319   for (uns i=0; i<GARY_SIZE(parts); i++)
320   {
321     struct map_placement *mp = parts[i]->placement->next_in_map;
322     while (mp)
323     {
324       if (p->variant_used >= 0)
325       {
326         struct placement **p = GARY_PUSH(buffer);
327         *p = mp->placement;
328       }
329       mp = mp->next_in_map;
330     }
331   }
332   GARY_FREE(parts);
333
334   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Returning %zu potentially overlapping placements\n", GARY_SIZE(buffer));
335
336   return buffer;
337 }
338
339 static int overlaps(struct placement *p1, struct placement *p2)
340 {
341   if (p1->request->type != REQUEST_POINT &&
342       p1->request->type != REQUEST_SEGMENT &&
343       p1->request->type != REQUEST_AREA)
344     return 0;
345
346   if (p2->request->type != REQUEST_POINT &&
347       p2->request->type != REQUEST_SEGMENT &&
348       p2->request->type != REQUEST_AREA)
349     return 0;
350
351   if (p1->variant_used == -1 || p2->variant_used == -1)
352     return 0;
353
354   struct variant *v1, *v2;
355
356   v1 = &(p1->request->variants[p1->variant_used]);
357   v2 = &(p2->request->variants[p2->variant_used]);
358
359   int x1, x2;
360   // FIXME: CHECK ME: Is rounding working all right here?
361   if (p1->x > p2->x)
362   {
363     x1 = 0;
364     x2 = (p1->x - p2->y) * bitmap_granularity;
365   }
366   else
367   {
368     x1 = (p2->x - p1->x) * bitmap_granularity;
369     x2 = 0;
370   }
371
372   int max_iter_x = min2(v1->width-1-x1, v2->width-1-x2);
373
374   int y1, y2;
375   if (p1->y > p2->y)
376   {
377     y1 = 0;
378     y2 = (p1->y - p2->y) * bitmap_granularity;
379   }
380   else
381   {
382     y1 = (p2->y - p1->y) * bitmap_granularity;
383     y2 = 0;
384   }
385
386   int max_iter_y = min2(v1->width-1-y1, v2->width-1-y2);
387
388   int overlap = 0;
389   for (int j=0; j<max_iter_y; j++, y1++, y2++) {
390     for (int i=0; i<max_iter_x; i++, x1++, x2++) {
391       if (v1->bitmap[y1*v1->width + x1] && v2->bitmap[y2*v2->width + x2])
392         overlap++;
393     }
394   }
395
396   return overlap;
397 }
398
399 int get_overlap(struct placement *p, int **planned_ptr, int iteration)
400 {
401   int *planned = *planned_ptr;
402
403   if (p->variant_used == -1) return 0;
404
405   struct map_part **parts = get_map_parts(p);
406   if (! parts)
407   {
408     DEBUG(dbg_overlaps, VERBOSITY_PLACEMENT, "Placement of request %d seems not to be placed\n", p->request->ind);
409     return 0;
410   }
411
412   struct placement **others;
413
414   planned[p->request->ind] = iteration;
415   GARY_INIT(others, 0);
416
417 //printf("Iterating over parts of placement %d (at [%.2f; %.2f] / %d)\n", p->ind, p->x, p->y, p->variant_used);
418   for (uns i=0; i<GARY_SIZE(parts); i++)
419   {
420   //printf("%d:\t", parts[i]->ind);
421   //dump_part_links(parts[i]);
422     struct map_placement *mp = parts[i]->placement->next_in_map;
423     while (mp)
424     {
425       if (planned[mp->placement->request->ind] != iteration)
426       {
427         struct placement **p = GARY_PUSH(others);
428         *p = mp->placement;
429         planned[mp->placement->request->ind] = iteration;
430       }
431       mp = mp->next_in_map;
432     }
433   }
434
435   int overlap = 0;
436   for (uns i=0; i<GARY_SIZE(others); i++)
437   {
438     overlap += overlaps(p, others[i]);
439   }
440
441   GARY_FREE(parts);
442   GARY_FREE(others);
443
444   if (dbg_overlaps >= VERBOSITY_PLACEMENT)
445   {
446     printf("Placement %d (of request %d) add %d to overlaps", p->ind, p->request->ind, overlap);
447     //dump_placement_links(p);
448   }
449
450   if (p->x < 0) overlap += (0 - p->x) * bitmap_granularity;
451   if (p->x + p->request->variants[p->variant_used].width * bitmap_granularity > page_width)
452     overlap += p->x + p->request->variants[p->variant_used].width * bitmap_granularity - page_width;
453
454   if (p->y < 0) overlap += (0 - p->y) * bitmap_granularity;
455   if (p->y + p->request->variants[p->variant_used].height * bitmap_granularity > page_height)
456     overlap += p->y + p->request->variants[p->variant_used].height * bitmap_granularity - page_height;
457
458   return overlap;
459 }
460
461 void dump_label(struct symbol *sym)
462 {
463   switch (sym->type)
464   {
465     case SYMBOLIZER_TEXT: ;
466       struct sym_text *st = (struct sym_text *) sym;
467       printf("%s\n", osm_val_decode(st->text));
468     default:
469       // FIXME
470       ;
471   }
472 }