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 }