X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=c386574556d50d638816518ea330ed7fcb27852f;hb=refs%2Fheads%2Flabelling;hp=7f74bbf8efb6f579705999b3d9af4a56c84b1699;hpb=27a0c4be8375ad51adf0a55696f83859625b8d47;p=leo.git diff --git a/labeller.c b/labeller.c index 7f74bbf..c386574 100644 --- a/labeller.c +++ b/labeller.c @@ -1,678 +1,218 @@ +#include +#include #include -#include -#include -#include +#include #include "leo.h" #include "sym.h" +#include "map.h" #include "labeller.h" +#include "lab-bitmaps.h" +#include "lab-utils.h" +#include "lab-evolution.h" +#include "lab-lines.h" -#define HASH_NODE struct graph_node -#define HASH_PREFIX(x) hash_##x -#define HASH_KEY_ATOMIC id -#define HASH_WANT_FIND -#define HASH_WANT_NEW -#include - -#include -#include -#include - -#define BLOCK_SIZE 4096 - -//struct mempool *mpool_requests; +struct request_point *requests_point = NULL; +struct request_line *requests_line = NULL; +struct request_area *requests_area = NULL; -static struct request_point *requests_point; -static struct request_line *requests_line; -static struct request_area *requests_area; +struct longline *longlines = NULL; +struct buffer_line *buffer_line = NULL; +struct buffer_linelabel *buffer_linelabel = NULL; -static struct graph_edge *bfs_queue; -static struct longline *longlines; int num_longlines; -static struct buffer_line *buffer_line; -static struct buffer_linelabel *buffer_linelabel; +int dbg_segments = VERBOSITY_NONE; +int dbg_plan = VERBOSITY_NONE; +int dbg_requests = VERBOSITY_NONE; +int dbg_graph = VERBOSITY_NONE; +int dbg_bfs = VERBOSITY_NONE; +int dbg_map_parts = VERBOSITY_NONE; +int dbg_movement = VERBOSITY_NONE; +int dbg_init = VERBOSITY_NONE; +int dbg_overlaps = VERBOSITY_GENERAL; +int dbg_rank = VERBOSITY_NONE; +int dbg_evolution = VERBOSITY_POPULATION; +int dbg_mutation = VERBOSITY_NONE; +int dbg_breeding = VERBOSITY_NONE; -struct eltpool *ep_individuals; +int page_width_int = 0; +int page_height_int = 0; -struct individual **population1; -struct individual **population2; +int num_requests = 0; +int num_placements = 0; -int conf_pop_size = 50; +// In milimeters +int conf_map_part_width = 5; +int conf_map_part_height = 5; -int conf_penalty_bound = 0; -int conf_stagnation_bound = 0; -int conf_iteration_limit = 5; +uns num_map_parts_row = 0; +uns num_map_parts_col = 0; +uns num_map_parts = 0; -int conf_term_cond = TERM_COND_ITERATIONS; - -int conf_breed_rbest_perc = 80; -int conf_breed_pop_size_perc = 20; -int conf_breed_perc = 50; +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 + } +}; -bool conf_mutate_children = 1; -int conf_mutate_children_prob = 0.3; +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); -int conf_mutate_rbest_perc = 60; -int conf_mutate_pop_size_perc = 20; +static void compute_sizes(void); -int conf_mutate_move_bound = 0.2; -int conf_mutate_regen_bound = 0.1; -int conf_mutate_chvar_bound = 0.1; +static void compute_sizes(void) +{ + page_width_int = floor(page_width); + page_height_int = floor(page_height); -int conf_elite_perc = 5; + page_width_gran = page_width * bitmap_granularity; + page_height_gran = page_height * bitmap_granularity; -int old_best = 0; // FIXME: Shall be int max -int iteration = 0; -int pop2_ind; + 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; -int conf_part_size = 50; +} -int move_min = 0; -int move_max = 1; +void labeller_conf(void) +{ + cf_declare_section("Labelling", &labelling_cf, 0); + evolution_conf(); +} void labeller_init(void) { -// mpool_requests = mp_new(BLOCK_SIZE); + compute_sizes(); + GARY_INIT(requests_point, 0); + GARY_INIT(requests_line, 0); GARY_INIT(requests_area, 0); GARY_INIT(buffer_line, 0); GARY_INIT(buffer_linelabel, 0); - ep_individuals = ep_new(sizeof(struct individual), 1); -} - -void make_bitmap_icon(struct point_variant *v, struct sym_icon *si) -{ - v->width = si->sir.icon->width; - v->height = si->sir.icon->height; -} - -void make_bitmap_point(struct point_variant *v, struct sym_point *sp) -{ - v->width = v->height = sp->size; - v->bitmap = malloc(sp->size*sp->size * sizeof(bool)); - // FIXME: Okay, memset would be much nicer here - for (int i=0; isize*sp->size; i++) v->bitmap[i] = 1; -} - -void make_bitmap_label(struct point_variant *v UNUSED, struct sym_text *text UNUSED) -{ + evolution_init(); } void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex) { -/* FIXME - What does correct check look like? + DEBUG(dbg_requests, VERBOSITY_PLACEMENT, "Adding point\n"); if (object->type != OSM_TYPE_NODE) { - // FIXME + printf("Warning: Point label requested on non-point object\n"); return; } -*/ struct request_point *r = GARY_PUSH(requests_point); - r->sym = sym; - r->object = object; - r->zindex = zindex; - struct osm_node *n = (struct osm_node *) object; - r->x = n->x; - r->y = n->y; + r->request.type = REQUEST_POINT; + r->request.ind = num_requests++; - r->offset_x = 0; - r->offset_y = 0; + r->sym = sym; + r->zindex = zindex; - r->num_variants = 1; - GARY_INIT(r->variants, 0); + GARY_INIT(r->request.variants, 0); - struct point_variant *v = GARY_PUSH(r->variants); + struct variant *v = GARY_PUSH(r->request.variants); - if (sym->type == SYMBOLIZER_ICON) + struct osm_node *n = (struct osm_node *) object; // FIXME: Compiler warning + r->x = n->x; + r->y = n->y; + make_bitmap(v, sym); switch (sym->type) { case SYMBOLIZER_ICON: - make_bitmap_icon(v, (struct sym_icon *) sym); - break; - case SYMBOLIZER_POINT: - make_bitmap_point(v, (struct sym_point *) sym); + // FIXME: Really? + r->x = ((struct sym_icon *)sym)->sir.x; + r->y = ((struct sym_icon *)sym)->sir.y; break; default: - // Oops :) // FIXME return; } - sym_plan(sym, zindex); // TEMPORARY + DEBUG(dbg_requests, VERBOSITY_PLACEMENT, "Inited point to [%.2f; %.2f] on %u\n", r->x, r->y, r->zindex); } -void labeller_add_line(struct symbol *sym, z_index_t zindex) +void labeller_notify_line(struct symbol *sym, z_index_t zindex) { + DEBUG(dbg_requests, VERBOSITY_PLACEMENT, "Adding line on %u\n", zindex); struct buffer_line *b = GARY_PUSH(buffer_line); b->line = (struct sym_line *) sym; - b->zindex = zindex; - sym_plan(sym, zindex); -} - -void labeller_add_arealabel(struct symbol *sym UNUSED, struct osm_object *o, z_index_t zindex) -{ - struct request_area *r = GARY_PUSH(requests_area); - r->o = (struct osm_multipolygon *) o; - r->zindex = zindex; } -void make_graph(void) +void labeller_add_label(struct symbol *sym, struct osm_object *o, z_index_t zindex) { - hash_init(); - struct mempool *mp_edges = mp_new(BLOCK_SIZE); - - printf("Extracting nodes, will iterate over %lld ways\n", GARY_SIZE(buffer_line)); - for (uns i=0; is.o; - struct graph_node *prev = NULL; - struct osm_node *prev_node = NULL; - CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes) - { - // FIXME: Shall osm_object's type be checked here? - struct osm_node *node = (struct osm_node *) ref->o; - - struct graph_node *n = hash_find(ref->o->id); - if (!n) - { - n = hash_new(ref->o->id); - GARY_INIT(n->edges, 0); - } - - if (! prev) - { - prev = n; - prev_node = node; - continue; - } - - struct graph_edge *e = (struct graph_edge *) mp_alloc(mp_edges, sizeof(struct graph_edge)); - e->id = buffer_line[i].line->s.o->id; - e->color = buffer_line[i].line->color; - e->length = hypot(abs(prev_node->x - node->x), abs(prev_node->y - node->y)); - e->visited = 0; - e->prev = NULL; - e->next = NULL; - e->n1 = prev; - e->n2 = n; - e->longline = -1; - e->text = NULL; - e->sym = buffer_line[i].line; - - struct graph_edge **edge = GARY_PUSH(prev->edges); - *edge = e; - edge = GARY_PUSH(n->edges); - *edge = e; - } - } -} - -void label_graph(void) -{ - for (uns i=0; itype) { - CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes) - { - struct graph_node *n = hash_find(ref->o->id); - if (n == NULL) - { - // FIXME: What shall be done? - } + case OSM_TYPE_WAY: + if (osm_way_cyclic_p((struct osm_way *) o)) + labeller_add_arealabel(sym, o, zindex); else - { - for (uns j=0; jedges); j++) - { - if (n->edges[j]->id == ((struct osm_object *) buffer_linelabel[i].way)->id) - { - n->edges[j]->text = buffer_linelabel[i].text; - } - } - } - } + labeller_add_linelabel(sym, o, zindex); + break; + default: + ; } } -void join_edge(struct graph_edge *e, int dir) +static void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex) { - struct graph_node *other_node = NULL; - switch (dir) + if (o->type != OSM_TYPE_WAY) { - case 1: - other_node = e->n2; - break; - case 2: - other_node = e->n1; - break; - // FIXME: default? - } - - struct graph_edge *candidate = NULL; - for (uns i=0; iedges); i++) - { - struct graph_edge *other = other_node->edges[i]; - if (! other->visited) - { - printf("Trying to add %dth edge\n", GARY_SIZE(bfs_queue)+1); - struct graph_edge **new = GARY_PUSH(bfs_queue); - *new = other_node->edges[i]; - } - - //if (1) // FIXME: same labels but not the same edge - if ((!other->visited) && (e->text) && (other->text) && (e->text->text == other->text->text)) - { - if (e->color == other_node->edges[i]->color) - { - if ((!candidate) || (candidate->length < other->length)) - { - candidate = other; - } - } - else - { - // Beware: Name conflict here - } - } - } - - if (candidate) - { - candidate->longline = e->longline; - if (dir == 1) - { - if (candidate->n2 != e->n1) - { - candidate->n1 = candidate->n2; - candidate->n2 = e->n1; - } - e->prev = candidate; - candidate->next = e; - - longlines[e->longline].first = candidate; - } - else - { - if (candidate->n1 != e->n2) - { - candidate->n2 = candidate->n1; - candidate->n1 = e->n2; - } - e->next = candidate; - candidate->prev = e; - } + printf("Linelabel request on object which is not way\n"); + return; } -} -void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t zindex) -{ + DEBUG(dbg_requests, VERBOSITY_PLACEMENT, "Labelling way %ju on %u\n", o->id, zindex); struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel); ll->way = (struct osm_way *) o; - ll->text = (struct sym_text *) sym; + ll->label = sym; ll->zindex = zindex; } -void bfs(void) +static void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex) { - GARY_INIT(bfs_queue, 0); - GARY_INIT(longlines, 0); + DEBUG(dbg_requests, VERBOSITY_PLACEMENT, "Adding area on %u\n", zindex); + struct request_area *r = GARY_PUSH(requests_area); - HASH_FOR_ALL(hash, node) - { - for (uns i=0; iedges); i++) - { - struct graph_edge *e = node->edges[i]; - - if (e->visited) HASH_CONTINUE; - if (e->longline == (uns) -1) - { - GARY_PUSH(longlines); - e->longline = num_longlines++; - longlines[num_longlines].first = e; - } - - e->visited = 1; - - if (! e->prev) - { - join_edge(e, 1); - } - if (! e->next) - { - join_edge(e, 2); - } - } - } - HASH_END_FOR; + r->request.type = REQUEST_AREA; + r->request.ind = num_requests++; - GARY_FREE(bfs_queue); -} + r->o = (struct osm_multipolygon *) o; + r->zindex = zindex; + r->label = sym; -void make_segments(void) -{ - GARY_INIT(requests_line, 0); + osm_obj_center(o, &(r->cx), &(r->cy)); - for (uns i=0; isegments, 0); - struct graph_edge *e = longlines[i].first; - while (e) - { - struct request_segment *r = GARY_PUSH(request->segments); - request->num_segments++; - r->x1 = ((struct osm_node *) e->n1)->x; - r->y1 = ((struct osm_node *) e->n1)->y; - r->x2 = ((struct osm_node *) e->n2)->x; - r->y2 = ((struct osm_node *) e->n2)->y; - r->sym = e->sym; - r->k = abs(r->x2 - r->x1) / abs(r->y2 - r->y1); - r->variant = malloc(sizeof(struct point_variant)); // FIXME - make_bitmap_label(r->variant, e->text); - - e = e->next; - } - } + GARY_INIT(r->request.variants, 0); + struct variant *v = GARY_PUSH(r->request.variants); + make_bitmap(v, sym); } void labeller_label(void) { - make_graph(); - label_graph(); - bfs(); - make_segments(); + segment_lines(); + evolve(); - make_population(); - - while (! shall_terminate()) - { - // sort population by fitness - // alloc new population - breed(); - mutate(); - elite(); - rank_population(); - } + labeller_cleanup(); } -void make_population(void) +void labeller_cleanup(void) { - GARY_INIT(population1, 0); - for (int i=0; imap, 0); - GARY_INIT(individual->placements, 0); + lines_cleanup(); + GARY_FREE(longlines); - for (uns j=0; jplacements); - init_placement(p, (struct request *) &requests_point[i]); - } - for (uns j=0; jplacements); - init_placement(p, (struct request *) &requests_line[i]); - } - for (uns j=0; jplacements); - init_placement(p, (struct request *) &requests_area[i]); - } - } -} + GARY_FREE(requests_point); + GARY_FREE(requests_area); -bool shall_terminate(void) -{ - switch (conf_term_cond) + for (uns i=0; ipenalty < conf_penalty_bound); - case TERM_COND_STAGNATION: - return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound); - case TERM_COND_ITERATIONS: - return (iteration >= conf_iteration_limit); - default: - // FIXME: Warn the user that no condition is set - return 1; - } -} - -void breed(void) -{ - int acc = 0; - int i=0; - int conf_breed_pop_size = conf_breed_pop_size_perc * conf_pop_size; - struct individual **breed_buffer; - while (i < conf_breed_rbest_perc * conf_pop_size) - { - int parent1 = randint(1, conf_breed_pop_size); - int parent2 = randint(1, conf_breed_pop_size); - breed_buffer = perform_crossover(population1[parent1], population1[parent2]); - population2[2*i] = breed_buffer[0]; - population2[2*i+1] = breed_buffer[1]; - free(breed_buffer); - } - - acc += conf_breed_rbest_perc; - - int remaining = (1 - acc) * (conf_pop_size * conf_breed_perc); - int step = remaining / conf_pop_size; - for (; iplacements); i++) - { - if (! parent1->placements[i].processed) - { - struct placement **clos_symbols; - GARY_INIT(clos_symbols, 0); - get_closure(clos_symbols, &(parent1->placements[i]), parent1, parent2); - int x = randint(1, 2); - - if (x == 1) - { - copy_symbols(clos_symbols, parent1, child1); - copy_symbols(clos_symbols, parent2, child2); - } - else - { - copy_symbols(clos_symbols, parent2, child1); - copy_symbols(clos_symbols, parent1, child2); - } - GARY_FREE(clos_symbols); - } - - if (conf_mutate_children) - { - if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child1); - if (randint(1, 1000) < conf_mutate_children_prob * 1000) perform_mutation(child2); - } - } - - buffer[0] = child1; - buffer[1] = child2; - return buffer; -} - -void mutate(void) -{ - int i = 0; - int conf_mutate_pop_size = conf_mutate_pop_size_perc * conf_pop_size; - while (i < conf_mutate_rbest_perc * conf_pop_size) - { - int ind = randint(1, conf_mutate_pop_size); - population2[pop2_ind] = population1[ind]; - perform_mutation(population2[pop2_ind]); - } -} - -void perform_mutation(struct individual *individual) -{ - for (uns i=0; iplacements); i++) - { - int x = randint(1, 1000); - int acc = 0; - - if (x <= acc + conf_mutate_move_bound) - { - move_symbol(&(individual->placements[i])); - continue; - } - acc += conf_mutate_move_bound; - - if (x <= acc + conf_mutate_regen_bound) - { - gen_coords(&(individual->placements[i])); - continue; - } - acc += conf_mutate_regen_bound; - - if (x <= acc + conf_mutate_chvar_bound) - { - if (0) // if num_variants > 1 - { - // FIXME: assign new variant - } - } - } -} - -void elite(void) -{ - for (int i=0; irequest->type) - { - case REQUEST_POINT: - gen_coords_point(p); - } -} - -void gen_coords_point(struct placement *p UNUSED) -{ - // FIXME -} - -struct map_part **get_parts(struct placement *symbol, struct individual *individual) -{ - struct map_part **buffer; - GARY_INIT(buffer, 0); - int x_min = symbol->x / conf_part_size; - int x_max = (symbol->x /*+ symbol->bitmap->width*/ + conf_part_size - 1) / conf_part_size; - int y_min = symbol->y / conf_part_size; - int y_max = (symbol->y /*+ symbol->bitmap->height*/ + conf_part_size - 1) / conf_part_size; - - for (int x=x_min; x < x_max; x++) - for (int y=y_min; y < y_max; y++) + for (uns j=0; jmap[x][y]; + GARY_FREE(requests_line[i].sections[j].segments); } - - return buffer; -} - -int randint(int min, int max) -{ - int r = random(); - return (r * (max - min)); -} - -void get_closure(struct placement **closure UNUSED, struct placement *placement UNUSED, struct individual *parent1 UNUSED, struct individual *parent2 UNUSED) -{ - bool *chosen = malloc(GARY_SIZE(parent1->placements) * sizeof(bool)); - chosen[placement->request->ind] = 1; - - struct placement **p = GARY_PUSH(closure); *p = placement; - - uns first = 0; - while (first < GARY_SIZE(closure)) - { - struct placement **overlapping = get_overlapping(placement); - filter(overlapping, chosen); - for (uns j=0; jrequest->ind] = 1; - } - GARY_FREE(overlapping); - } -} - -void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child) -{ - for (uns i=0; irequest->ind; - child->placements[ind] = parent->placements[ind]; + GARY_FREE(requests_line[i].sections); } -} - -void move_symbol(struct placement *p) -{ - switch (p->request->type) - { - case REQUEST_POINT: - move_symbol_point(p); - } -} - -void move_symbol_point(struct placement *p) -{ - p->x += (double) (move_min + randdouble()) * flip(1, -1); - p->y += (double) (move_min + randdouble()) * flip(1, -1); -} - -void init_placement(struct placement *p UNUSED, struct request *r UNUSED) -{ - // FIXME -} - -struct placement **get_overlapping(struct placement *p UNUSED) -{ - struct placement **buffer; - GARY_INIT(buffer, 0); -return buffer; } - -void filter(struct placement **list UNUSED, bool *pred UNUSED) -{ - // FIXME -} - -int flip(int a, int b) -{ - return (random() % 2 ? a : b); -} - -double randdouble(void) -{ - // FIXME: How the hell shall double in range <0, 1> be generated? O:) - return 0.5; + GARY_FREE(requests_line); }