From f6bd1d0d00551ffb56e49dfce583a74009887463 Mon Sep 17 00:00:00 2001 From: Karryanna Date: Fri, 3 Jul 2015 16:56:33 +0200 Subject: [PATCH] Labelling: Support for better bitmaps granularity Hasn't been extensively tested yet --- lab-bitmaps.c | 93 +++++++++++++++++++++++++++++++++++---------------- lab-bitmaps.h | 3 ++ lab-lines.c | 16 +-------- lab-lines.h | 2 ++ labeller.c | 15 ++++++++- map.cf | 14 +++++--- 6 files changed, 94 insertions(+), 49 deletions(-) diff --git a/lab-bitmaps.c b/lab-bitmaps.c index 8845eac..f5822e6 100644 --- a/lab-bitmaps.c +++ b/lab-bitmaps.c @@ -8,6 +8,7 @@ #include "leo.h" #include "sym.h" +#include "map.h" #include "labeller.h" #include "lab-bitmaps.h" #include "lab-utils.h" @@ -22,6 +23,10 @@ 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); +double bitmap_granularity = 1; + +int page_width_gran, page_height_gran; + void make_bitmap(struct variant *v, struct symbol *sym) { @@ -104,11 +109,11 @@ static void make_bitmap_label(struct variant *v, struct sym_text *text) 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; iplacements); i++) @@ -130,10 +135,18 @@ void dump_bitmaps(struct individual *individual) continue; } - int base_x = p->x; int base_y = p->y; - for (int dr = max2(0, 0-p->y); dr < v->height; dr++) + // FIXME: + // if e.g. granularity is 2, p->x = 2.4 and v->width = 4 + // then <2, 2.5> will be marked as occupied while <4, 4.5> won't be, + // though the variant occupies <2.4, 4,4> and therefore occupies much + // more of <4, 4.5> than of <2, 2.5> + int base_x = p->x * bitmap_granularity; + int base_y = p->y * bitmap_granularity; + int max_dr = min2(v->height - 1, (page_height - p->y) * bitmap_granularity); + int max_dc = min2(v->width - 1, (page_width - p->x) * bitmap_granularity); + for (int dr = max2(0, 0-p->y); dr < max_dr; dr++) { - for (int dc = max2(0, 0-p->x); dc < v->width; dc++) + for (int dc = max2(0, 0-p->x); dc < max_dc; dc++) { if (v->bitmap[dr * v->width + dc]) { @@ -147,12 +160,12 @@ void dump_bitmaps(struct individual *individual) 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; ix) / 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 x_max = min2(page_width_int, (p->x + v.width / bitmap_granularity)) / 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; + int y_max = min2(page_height_int, (p->y + v.height / bitmap_granularity)) / 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); @@ -343,18 +356,42 @@ static int overlaps(struct placement *p1, struct placement *p2) 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 x1, x2; + // FIXME: CHECK ME: Is rounding working all right here? + if (p1->x > p2->x) + { + x1 = 0; + x2 = (p1->x - p2->y) * bitmap_granularity; + } + else + { + x1 = (p2->x - p1->x) * bitmap_granularity; + x2 = 0; + } + + int max_iter_x = min2(v1->width-1-x1, v2->width-1-x2); + + int y1, y2; + if (p1->y > p2->y) + { + y1 = 0; + y2 = (p1->y - p2->y) * bitmap_granularity; + } + else + { + y1 = (p2->y - p1->y) * bitmap_granularity; + y2 = 0; + } + + int max_iter_y = min2(v1->width-1-y1, v2->width-1-y2); int overlap = 0; - for (int y=max2(0, max2(p1y, p2y)); yheight, p2y+v2->height)); y++) - for (int x=max2(0, max2(p1x, p2x)); xwidth, p2x+v2->width)); x++) - { - if (v1->bitmap[(y-p1y)*v1->width + (x-p1x)] && - v2->bitmap[(y-p2y)*v2->width + (x-p2x)]) + for (int j=0; jbitmap[y1*v1->width + x1] && v2->bitmap[y2*v2->width + x2]) overlap++; } + } return overlap; } @@ -410,13 +447,13 @@ int get_overlap(struct placement *p, int **planned_ptr, int iteration) //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->x < 0) overlap += (0 - p->x) * bitmap_granularity; + if (p->x + p->request->variants[p->variant_used].width * bitmap_granularity > page_width) + overlap += p->x + p->request->variants[p->variant_used].width * bitmap_granularity - page_width; - 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; + if (p->y < 0) overlap += (0 - p->y) * bitmap_granularity; + if (p->y + p->request->variants[p->variant_used].height * bitmap_granularity > page_height) + overlap += p->y + p->request->variants[p->variant_used].height * bitmap_granularity - page_height; return overlap; } diff --git a/lab-bitmaps.h b/lab-bitmaps.h index 229e028..b178272 100644 --- a/lab-bitmaps.h +++ b/lab-bitmaps.h @@ -14,4 +14,7 @@ void dump_bitmaps(struct individual *individual); void dump_label(struct symbol *sym); void dump_graph(void); +extern int page_width_gran, page_height_gran; +extern double bitmap_granularity; + #endif diff --git a/lab-lines.c b/lab-lines.c index 1ec7a3f..e33fd0a 100644 --- a/lab-lines.c +++ b/lab-lines.c @@ -3,7 +3,6 @@ #include #include -#include #include #include @@ -85,20 +84,7 @@ static int dbg_num_hits = 0; static struct graph_edge **bfs_queue; -static double conf_max_section_length = 80, conf_max_section_overlay = 10; - -static struct cf_section lines_cf = { - CF_ITEMS { - CF_DOUBLE("MaxSectionLenght", &conf_max_section_length), - CF_DOUBLE("MaxSectionOverlay", &conf_max_section_overlay), - CF_END - } -}; - -void lines_conf(void) -{ - cf_declare_section("Labelling", &lines_cf, 0); -} +double conf_max_section_length = 80, conf_max_section_overlay = 10; static struct request_line *make_new_line(void) { diff --git a/lab-lines.h b/lab-lines.h index a796037..5f096c9 100644 --- a/lab-lines.h +++ b/lab-lines.h @@ -8,4 +8,6 @@ void segment_lines(void); void dump_longlines(void); +extern double conf_max_section_length, conf_max_section_overlay; + #endif diff --git a/labeller.c b/labeller.c index 71c0f55..c386574 100644 --- a/labeller.c +++ b/labeller.c @@ -1,6 +1,7 @@ #include #include #include +#include #include "leo.h" #include "sym.h" @@ -47,6 +48,15 @@ uns num_map_parts_row = 0; uns num_map_parts_col = 0; uns num_map_parts = 0; +static struct cf_section labelling_cf = { + CF_ITEMS { + CF_DOUBLE("MaxSectionLenght", &conf_max_section_length), + CF_DOUBLE("MaxSectionOverlay", &conf_max_section_overlay), + CF_DOUBLE("BitmapGranularity", &bitmap_granularity), + CF_END + } +}; + static void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex); static void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex); @@ -57,6 +67,9 @@ static void compute_sizes(void) page_width_int = floor(page_width); page_height_int = floor(page_height); + page_width_gran = page_width * bitmap_granularity; + page_height_gran = page_height * bitmap_granularity; + num_map_parts_row = (page_width_int + conf_map_part_width) / conf_map_part_width; num_map_parts_col = (page_height_int + conf_map_part_height) / conf_map_part_height; num_map_parts = num_map_parts_row * num_map_parts_col; @@ -65,8 +78,8 @@ static void compute_sizes(void) void labeller_conf(void) { + cf_declare_section("Labelling", &labelling_cf, 0); evolution_conf(); - lines_conf(); } void labeller_init(void) diff --git a/map.cf b/map.cf index 0751960..ab93d5e 100644 --- a/map.cf +++ b/map.cf @@ -67,6 +67,15 @@ Debug { DumpSymbols 0 } +Labelling { + # Maximal length of line section in milimeters + MaxSectionLenght 80 + # Section's length may exceed limit by at most [mm] + MaxSectionOverlay 10 + # Bitmap granularity (bitmap points per milimeter) + BitmapGranularity 1 +} + Evolution { # Number of individuals in each generation PopSize 50 @@ -100,9 +109,4 @@ Evolution { MutateChvarBound 0.1 ElitePopSize 0.1 - - # Maximal length of line section in milimeters - MaxSectionLenght 80 - # Section's length may exceed limit by at most [mm] - MaxSectionOverlay 10 } -- 2.39.2