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