--- /dev/null
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#include <ucw/lib.h>
+#include <ucw/gary.h>
+
+#include "leo.h"
+#include "sym.h"
+#include "labeller.h"
+#include "lab-bitmaps.h"
+#include "lab-utils.h"
+
+static void make_bitmap_icon(struct variant *v, struct sym_icon *si);
+static void make_bitmap_point(struct variant *v, struct sym_point *sp);
+static void make_bitmap_label(struct variant *v, struct sym_text *text);
+
+static int overlaps(struct placement *p1, struct placement *p2);
+
+static struct map_part **get_map_parts(struct placement *p);
+static struct placement **get_overlapping(struct placement *p);
+
+
+void make_bitmap(struct variant *v, struct symbol *sym)
+{
+ v->offset_x = v->offset_y = 0;
+
+ switch (sym->type)
+ {
+ case SYMBOLIZER_POINT:
+ make_bitmap_point(v, (struct sym_point *) sym);
+ break;
+ case SYMBOLIZER_ICON:
+ make_bitmap_icon(v, (struct sym_icon *) sym);
+ break;
+ case SYMBOLIZER_TEXT:
+ make_bitmap_label(v, (struct sym_text *) sym);
+ break;
+ default:
+ ASSERT(sym->type != SYMBOLIZER_INVALID);
+ }
+}
+
+static void make_bitmap_icon(struct variant *v, struct sym_icon *si)
+{
+ v->width = si->sir.width + 1;
+ v->height = si->sir.height + 1;
+ v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
+ for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
+}
+
+static void make_bitmap_point(struct variant *v, struct sym_point *sp)
+{
+ v->width = v->height = sp->size + 1;
+ v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
+ // FIXME: Okay, memset would be much nicer here
+ for (int i=0; i<sp->size*sp->size; i++) v->bitmap[i] = 1;
+}
+
+static void make_bitmap_label(struct variant *v, struct sym_text *text)
+{
+ int tw = ceil(text->tw);
+ int th = ceil(text->th);
+
+ double rotate_rad = convert_to_rad(text->rotate);
+
+ // Initially, ll = [0; 0], lr = [tw, 0], ul = [0, th], ur = [tw, th]
+ // They could be declared before but should not be initialized in code
+ // as reassigning x-coordinate affects computation of y-cordinate
+ int llx = 0;
+ int lly = 0;
+
+ int lrx = tw * cos(rotate_rad);
+ int lry = tw * sin(rotate_rad);
+
+ int ulx = th * sin(rotate_rad);
+ int uly = th * cos(rotate_rad);
+
+ int urx = tw * cos(rotate_rad) + th * sin(rotate_rad);
+ int ury = tw * sin(rotate_rad) + th * cos(rotate_rad);
+
+ int min_x = min4(llx, lrx, ulx, urx);
+ int min_y = min4(lly, lry, uly, ury);
+ int max_x = max4(llx, lrx, ulx, urx);
+ int max_y = max4(lly, lry, uly, ury);
+
+ v->width = max_x - min_x + 1;
+ v->height = max_y - min_y + 1;
+ v->bitmap = xmalloc(v->width * v->height * sizeof(bool));
+ memset(v->bitmap, 0, v->width * v->height * sizeof(bool));
+
+ for (int i=0; i<th; i++)
+ {
+ for (int j=0; j<tw; j++)
+ {
+ int nx = j*cos(rotate_rad) + i*sin(rotate_rad);
+ int ny = j*sin(rotate_rad) + i*cos(rotate_rad);
+ v->bitmap[(ny-min_y)*v->width + (nx-min_x)] = 1;
+ }
+ }
+}
+
+void dump_bitmaps(struct individual *individual)
+{
+ bool *bitmap = xmalloc(page_width_int * page_height_int * sizeof(bool));
+ printf("Bitmap size is %d\n", page_width_int * page_height_int);
+ for (int i=0; i<page_height_int; i++)
+ for (int j=0; j<page_width_int; j++)
+ bitmap[i*page_width_int + j] = 0;
+
+ int total = 0;
+ for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+ {
+ if (individual->placements[i].variant_used == -1) continue;
+
+ struct placement *p = &(individual->placements[i]);
+ struct variant *v = NULL;
+
+ switch (p->request->type)
+ {
+ case REQUEST_SEGMENT: ;
+ case REQUEST_POINT: ;
+ case REQUEST_AREA: ;
+ v = &(p->request->variants[p->variant_used]);
+ break;
+ default:
+ ASSERT(p->request->type != REQUEST_INVALID);
+ continue;
+ }
+
+ int base_x = p->x; int base_y = p->y;
+ for (int dr = max2(0, 0-p->y); dr < v->height; dr++)
+ {
+ for (int dc = max2(0, 0-p->x); dc < v->width; dc++)
+ {
+ if (v->bitmap[dr * v->width + dc])
+ {
+ if (bitmap[(base_y + dr) * page_width_int + (base_x + dc)]) total += 1;
+ bitmap[(base_y + dr) * page_width_int + (base_x + dc)] = 1;
+ }
+ }
+ }
+ }
+ DEBUG(dbg_overlaps, VERBOSITY_GENERAL, "There were %d collisions during bitmap dump\n", total);
+
+ FILE *fd_dump = fopen("dump.pbm", "w");
+ fprintf(fd_dump, "P1\n");
+ fprintf(fd_dump, "%d %d\n", page_width_int, page_height_int);
+ for (int i=0; i<page_height_int; i++)
+ {
+ for (int j=0; j<page_width_int; j++)
+ {
+ fprintf(fd_dump, "%d", bitmap[(int) (i*page_width_int + j)] ? 1 : 0);
+ }
+ fprintf(fd_dump, "\n");
+ }
+ fclose(fd_dump);
+
+ free(bitmap);
+}
+
+static struct map_part **get_map_parts(struct placement *p)
+{
+ if (p->variant_used < 0) return NULL;
+
+ struct map_part **buffer;
+ GARY_INIT(buffer, 0);
+
+ 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);
+
+ struct variant v;
+ switch (p->request->type)
+ {
+ case REQUEST_POINT:
+ case REQUEST_SEGMENT:
+ case REQUEST_AREA:
+ v = p->request->variants[p->variant_used];
+ break;
+ default:
+ DEBUG(dbg_map_parts, VERBOSITY_ALL, "Skipping unsupported request type (%d)\n", p->request->type);
+ return NULL;
+ }
+
+ DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Bitmap is %d x %d\n", v.width, v.height);
+
+ int x_min = max2(0, p->x) / conf_map_part_width;
+ // CHECK ME: Is rounding needed?
+ int x_max = min2(page_width_int, (p->x + v.width)) / conf_map_part_width;
+ int y_min = max2(0, p->y) / conf_map_part_height;
+ // CHECK ME: Is rounding needed?
+ int y_max = min2(page_height_int, (p->y + v.height)) / conf_map_part_height;
+
+ DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Cells between [%d; %d] and [%d; %d] generated\n", x_min, y_min, x_max, y_max);
+
+ for (int y=y_min; y<=y_max; y++)
+ for (int x=x_min; x<=x_max; x++)
+ {
+ struct map_part **m = GARY_PUSH(buffer);
+ DEBUG(dbg_map_parts, VERBOSITY_ALL, "Asking for %d of %zu\n", y * num_map_parts_row + x, GARY_SIZE(p->individual->map));
+ *m = p->individual->map[y * num_map_parts_row + x];
+ }
+
+ DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Returning %zu map parts potentially containing the symbol\n", GARY_SIZE(buffer));
+
+ return buffer;
+}
+
+void update_map_parts_delete(struct placement *p)
+{
+ struct map_placement *mp = p->map_links;
+ while (mp)
+ {
+ mp->prev_in_map->next_in_map = mp->next_in_map;
+ if (mp->next_in_map)
+ mp->next_in_map->prev_in_map = mp->prev_in_map;
+
+ struct map_placement *tmp = mp;
+ mp = mp->next_in_placement;
+ free(tmp);
+ }
+ p->map_links = NULL;
+}
+
+void update_map_parts_create(struct placement *p)
+{
+ struct map_part **parts = get_map_parts(p);
+ if (parts == NULL) return;
+
+ for (uns i=0; i<GARY_SIZE(parts); i++)
+ {
+ struct map_placement *mp = xmalloc(sizeof(struct map_placement));
+ mp->placement = p;
+ mp->part = parts[i];
+
+ mp->next_in_map = parts[i]->placement->next_in_map;
+ mp->prev_in_map = parts[i]->placement;
+ parts[i]->placement->next_in_map = mp;
+ if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;
+
+ mp->next_in_placement = p->map_links;
+ mp->prev_in_placement = NULL;
+ p->map_links = mp;
+ }
+
+ GARY_FREE(parts);
+}
+
+void update_map_parts(struct placement *p)
+{
+ update_map_parts_delete(p);
+ update_map_parts_create(p);
+}
+
+struct placement **get_closure(struct placement *placement)
+{
+ struct placement **closure;
+ GARY_INIT(closure, 0);
+ bool *chosen = xmalloc(GARY_SIZE(placement->individual->placements) * sizeof(bool));
+ for (uns i=0; i<GARY_SIZE(placement->individual->placements); i++) { chosen[i] = 0; }
+ chosen[placement->request->ind] = 1;
+
+ struct placement **p = GARY_PUSH(closure); *p = placement;
+
+ uns first = 0;
+ while (first < GARY_SIZE(closure))
+ {
+ DEBUG(dbg_breeding, VERBOSITY_ALL, "Iterating, first is %u of current %zu\n", first, GARY_SIZE(closure));
+ struct placement **overlapping = get_overlapping(placement);
+ if (! overlapping) { first++; continue; }
+
+ struct placement **filtered = filter(overlapping, &chosen);
+ DEBUG(dbg_breeding, VERBOSITY_ALL, "There are %zu new overlapping symbols\n", GARY_SIZE(filtered));
+ GARY_FREE(overlapping);
+ overlapping = filtered;
+ for (uns j=0; j<GARY_SIZE(overlapping); j++)
+ {
+ if (! chosen[overlapping[j]->request->ind])
+ {
+ if (overlaps(*p, overlapping[j]))
+ {
+ p = GARY_PUSH(closure); *p = overlapping[j];
+ 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);
+ chosen[overlapping[j]->request->ind] = 1;
+ }
+ }
+ }
+ GARY_FREE(overlapping);
+ first++;
+ }
+
+ free(chosen);
+
+ return closure;
+}
+
+static struct placement **get_overlapping(struct placement *p)
+{
+ struct placement **buffer;
+ GARY_INIT(buffer, 0);
+
+ struct map_part **parts = get_map_parts(p);
+ if (! parts) return NULL;
+
+ for (uns i=0; i<GARY_SIZE(parts); i++)
+ {
+ struct map_placement *mp = parts[i]->placement->next_in_map;
+ while (mp)
+ {
+ if (p->variant_used >= 0)
+ {
+ struct placement **p = GARY_PUSH(buffer);
+ *p = mp->placement;
+ }
+ mp = mp->next_in_map;
+ }
+ }
+ GARY_FREE(parts);
+
+ DEBUG(dbg_map_parts, VERBOSITY_PLACEMENT, "Returning %zu potentially overlapping placements\n", GARY_SIZE(buffer));
+
+ return buffer;
+}
+
+static int overlaps(struct placement *p1, struct placement *p2)
+{
+ if (p1->request->type != REQUEST_POINT &&
+ p1->request->type != REQUEST_SEGMENT &&
+ p1->request->type != REQUEST_AREA)
+ return 0;
+
+ if (p2->request->type != REQUEST_POINT &&
+ p2->request->type != REQUEST_SEGMENT &&
+ p2->request->type != REQUEST_AREA)
+ return 0;
+
+ if (p1->variant_used == -1 || p2->variant_used == -1)
+ return 0;
+
+ struct variant *v1, *v2;
+
+ v1 = &(p1->request->variants[p1->variant_used]);
+ v2 = &(p2->request->variants[p2->variant_used]);
+
+ // FIXME: This doesn't fully respect offset which it probably should
+ int p1x = p1->x; int p1y = p1->y;
+ int p2x = p2->x; int p2y = p2->y;
+
+ int overlap = 0;
+ for (int y=max2(0, max2(p1y, p2y)); y<min2(page_height_int, min2(p1y+v1->height, p2y+v2->height)); y++)
+ for (int x=max2(0, max2(p1x, p2x)); x<min2(page_width_int, min2(p1x+v1->width, p2x+v2->width)); x++)
+ {
+ if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] &&
+ v2->bitmap[(y-p2y)*v2->width + (x-p2x)])
+ overlap++;
+ }
+
+ return overlap;
+}
+
+int get_overlap(struct placement *p, int **planned_ptr, int iteration)
+{
+ int *planned = *planned_ptr;
+
+ if (p->variant_used == -1) return 0;
+
+ struct map_part **parts = get_map_parts(p);
+ if (! parts)
+ {
+ DEBUG(dbg_overlaps, VERBOSITY_PLACEMENT, "Placement of request %d seems not to be placed\n", p->request->ind);
+ return 0;
+ }
+
+ struct placement **others;
+
+ planned[p->request->ind] = iteration;
+ GARY_INIT(others, 0);
+
+//printf("Iterating over parts of placement %d (at [%.2f; %.2f] / %d)\n", p->ind, p->x, p->y, p->variant_used);
+ for (uns i=0; i<GARY_SIZE(parts); i++)
+ {
+ //printf("%d:\t", parts[i]->ind);
+ //dump_part_links(parts[i]);
+ struct map_placement *mp = parts[i]->placement->next_in_map;
+ while (mp)
+ {
+ if (planned[mp->placement->request->ind] != iteration)
+ {
+ struct placement **p = GARY_PUSH(others);
+ *p = mp->placement;
+ planned[mp->placement->request->ind] = iteration;
+ }
+ mp = mp->next_in_map;
+ }
+ }
+
+ int overlap = 0;
+ for (uns i=0; i<GARY_SIZE(others); i++)
+ {
+ overlap += overlaps(p, others[i]);
+ }
+
+ GARY_FREE(parts);
+ GARY_FREE(others);
+
+ if (dbg_overlaps >= VERBOSITY_PLACEMENT)
+ {
+ printf("Placement %d (of request %d) add %d to overlaps", p->ind, p->request->ind, overlap);
+ //dump_placement_links(p);
+ }
+
+ if (p->x < 0) overlap += 0 - p->x;
+ if (p->x + p->request->variants[p->variant_used].width > page_width_int)
+ overlap += p->x + p->request->variants[p->variant_used].width - page_width_int;
+
+ if (p->y < 0) overlap += 0 - p->y;
+ if (p->y + p->request->variants[p->variant_used].height > page_height_int)
+ overlap += p->y + p->request->variants[p->variant_used].height - page_height_int;
+
+ return overlap;
+}
+
+void dump_label(struct symbol *sym)
+{
+ switch (sym->type)
+ {
+ case SYMBOLIZER_TEXT: ;
+ struct sym_text *st = (struct sym_text *) sym;
+ printf("%s\n", osm_val_decode(st->text));
+ default:
+ // FIXME
+ ;
+ }
+}
projects / leo.git / blobdiff