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