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_in(struct placement *p, struct individual *individual);
  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, struct individual *other)
 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_in(closure[first], other);
 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);
 297           *p = &(placement->individual->placements[overlapping[j]->request->ind]);
 298           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);
 299           chosen[overlapping[j]->request->ind] = 1;
 300         }
 301       }
 302     }
 303     GARY_FREE(overlapping);
 304     first++;
 305   }
 306
 307   free(chosen);
 308
 309   return closure;
 310 }
 311
 312 static struct placement **get_overlapping_in(struct placement *p, struct individual *individual)
 313 {
 314   struct placement **buffer;
 315   GARY_INIT(buffer, 0);
 316
 317   struct map_part **parts = get_map_parts(p);
 318   if (! parts) return NULL;
 319
 320   for (uns i=0; i<GARY_SIZE(parts); i++)
 321   {
 322     struct map_placement *mp = individual->map[parts[i]->ind]->placement->next_in_map;
 323     while (mp)
 324     {
 325       if (p->variant_used >= 0)
 326       {
 327         struct placement **p = GARY_PUSH(buffer);
 328         *p = mp->placement;
 329       }
 330       mp = mp->next_in_map;
 331     }
 332   }
 333   GARY_FREE(parts);
 334
 335   DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Returning %zu potentially overlapping placements\n", GARY_SIZE(buffer));
 336
 337   return buffer;
 338 }
 339
 340 static int overlaps(struct placement *p1, struct placement *p2)
 341 {
 342   if (p1->request->type != REQUEST_POINT &&
 343       p1->request->type != REQUEST_SEGMENT &&
 344       p1->request->type != REQUEST_AREA)
 345     return 0;
 346
 347   if (p2->request->type != REQUEST_POINT &&
 348       p2->request->type != REQUEST_SEGMENT &&
 349       p2->request->type != REQUEST_AREA)
 350     return 0;
 351
 352   if (p1->variant_used == -1 || p2->variant_used == -1)
 353     return 0;
 354
 355   struct variant *v1, *v2;
 356
 357   v1 = &(p1->request->variants[p1->variant_used]);
 358   v2 = &(p2->request->variants[p2->variant_used]);
 359
 360   int x1, x2;
 361   // FIXME: CHECK ME: Is rounding working all right here?
 362   if (p1->x > p2->x)
 363   {
 364     x1 = 0;
 365     x2 = (p1->x - p2->y) * bitmap_granularity;
 366   }
 367   else
 368   {
 369     x1 = (p2->x - p1->x) * bitmap_granularity;
 370     x2 = 0;
 371   }
 372
 373   int max_iter_x = min2(v1->width-1-x1, v2->width-1-x2);
 374
 375   int y1, y2;
 376   if (p1->y > p2->y)
 377   {
 378     y1 = 0;
 379     y2 = (p1->y - p2->y) * bitmap_granularity;
 380   }
 381   else
 382   {
 383     y1 = (p2->y - p1->y) * bitmap_granularity;
 384     y2 = 0;
 385   }
 386
 387   int max_iter_y = min2(v1->width-1-y1, v2->width-1-y2);
 388
 389   int overlap = 0;
 390   for (int j=0; j<max_iter_y; j++, y1++, y2++) {
 391     for (int i=0; i<max_iter_x; i++, x1++, x2++) {
 392       if (v1->bitmap[y1*v1->width + x1] && v2->bitmap[y2*v2->width + x2])
 393         overlap++;
 394     }
 395   }
 396
 397   return overlap;
 398 }
 399
 400 int get_overlap(struct placement *p, int **planned_ptr, int iteration)
 401 {
 402   int *planned = *planned_ptr;
 403
 404   if (p->variant_used == -1) return 0;
 405
 406   struct map_part **parts = get_map_parts(p);
 407   if (! parts)
 408   {
 409     DEBUG(dbg_overlaps, VERBOSITY_PLACEMENT, "Placement of request %d seems not to be placed\n", p->request->ind);
 410     return 0;
 411   }
 412
 413   struct placement **others;
 414
 415   planned[p->request->ind] = iteration;
 416   GARY_INIT(others, 0);
 417
 418 //printf("Iterating over parts of placement %d (at [%.2f; %.2f] / %d)\n", p->ind, p->x, p->y, p->variant_used);
 419   for (uns i=0; i<GARY_SIZE(parts); i++)
 420   {
 421   //printf("%d:\t", parts[i]->ind);
 422   //dump_part_links(parts[i]);
 423     struct map_placement *mp = parts[i]->placement->next_in_map;
 424     while (mp)
 425     {
 426       if (planned[mp->placement->request->ind] != iteration)
 427       {
 428         struct placement **p = GARY_PUSH(others);
 429         *p = mp->placement;
 430         planned[mp->placement->request->ind] = iteration;
 431       }
 432       mp = mp->next_in_map;
 433     }
 434   }
 435
 436   int overlap = 0;
 437   for (uns i=0; i<GARY_SIZE(others); i++)
 438   {
 439     overlap += overlaps(p, others[i]);
 440   }
 441
 442   GARY_FREE(parts);
 443   GARY_FREE(others);
 444
 445   if (dbg_overlaps >= VERBOSITY_PLACEMENT)
 446   {
 447     printf("Placement %d (of request %d) add %d to overlaps", p->ind, p->request->ind, overlap);
 448     //dump_placement_links(p);
 449   }
 450
 451   if (p->x < 0) overlap += (0 - p->x) * bitmap_granularity;
 452   if (p->x + p->request->variants[p->variant_used].width * bitmap_granularity > page_width)
 453     overlap += p->x + p->request->variants[p->variant_used].width * bitmap_granularity - page_width;
 454
 455   if (p->y < 0) overlap += (0 - p->y) * bitmap_granularity;
 456   if (p->y + p->request->variants[p->variant_used].height * bitmap_granularity > page_height)
 457     overlap += p->y + p->request->variants[p->variant_used].height * bitmap_granularity - page_height;
 458
 459   return overlap;
 460 }
 461
 462 void dump_label(struct symbol *sym)
 463 {
 464   switch (sym->type)
 465   {
 466     case SYMBOLIZER_TEXT: ;
 467       struct sym_text *st = (struct sym_text *) sym;
 468       printf("%s\n", osm_val_decode(st->text));
 469     default:
 470       // FIXME
 471       ;
 472   }
 473 }