X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=0bd3d4afc74c5dbaaed2e4120ffde467ee57daeb;hb=66a1b5b64bdbbc42cca5333dfe26abcadb652f7e;hp=e8e423b0c0b6de0c81148609f478c41ace62e6b3;hpb=4e51953df82e9ed1797912c2ecb17098a3253452;p=leo.git

diff --git a/labeller.c b/labeller.c
index e8e423b..0bd3d4a 100644
--- a/labeller.c
+++ b/labeller.c
@@ -41,6 +41,9 @@ struct eltpool *ep_individuals;
 struct individual **population1;
 struct individual **population2;
 
+int dbg_segments = 0;
+int dbg_plan = 0;
+
 int page_width_int;
 int page_height_int;
 
@@ -87,6 +90,31 @@ int move_max = 1;
 
 int num_requests = 0;
 
+void make_graph(void);
+void label_graph(void);
+void join_edge(struct graph_edge *e, int dir);
+void bfs(uns longline);
+void make_segments(void);
+
+void make_population(void);
+bool shall_terminate(void);
+void breed(void);
+void mutate(void);
+void elite(void);
+void rank_population(void);
+void plan_individual(struct individual *individual);
+
+void make_bitmap(struct point_variant *v, struct symbol *sym);
+void make_bitmap_icon(struct point_variant *v, struct sym_icon *si);
+void make_bitmap_point(struct point_variant *v, struct sym_point *sp);
+void make_bitmap_label(struct point_variant *v, struct sym_text *text);
+
+void cut_edge(struct graph_edge *e, double dist);
+struct request_line *make_new_line(void);
+struct request_section *make_new_section(struct request_line *rl);
+struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
+
+void dump_bitmaps(struct individual *individual);
 void dump_graph(void);
 void bfs2(void);
 void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
@@ -105,6 +133,32 @@ void gen_coords_area(struct placement *p);
 
 void make_segments_old(void);
 
+void labeller_cleanup(void);
+
+struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
+void perform_mutation(struct individual *individual);
+
+void init_placement(struct placement *p, struct request *r);
+void init_individual(struct individual *i);
+struct map_part **get_parts(struct placement *symbol, struct individual *individual);
+
+int randint(int min, int max);
+
+struct placement **get_closure(struct placement *placement, struct individual *parent1, struct individual *parent2);
+void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child);
+void move_symbol(struct placement *p);
+void move_symbol_point(struct placement *p);
+
+struct placement **get_overlapping(struct placement *p);
+void filter(struct placement **list, bool *pred);
+
+int flip(int a, int b);
+double randdouble(void);
+
+void cleanup(void);
+
+void copy_individual(struct individual *src, struct individual *dest);
+
 int max2(int a, int b);
 int min2(int a, int b);
 int max4(int a, int b, int c, int d);
@@ -156,6 +210,24 @@ void labeller_init(void)
   page_height_int = floor(page_height);
 }
 
+void make_bitmap(struct point_variant *v, struct symbol *sym)
+{
+  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);
+  }
+}
+
 void make_bitmap_icon(struct point_variant *v, struct sym_icon *si)
 {
   v->width = si->sir.icon->width;
@@ -583,6 +655,75 @@ printf("\n");
   }
 }
 
+struct request_line *make_new_line(void)
+{
+  struct request_line *rl = GARY_PUSH(requests_line);
+  rl->request.ind = num_requests++;
+  rl->request.type = REQUEST_LINE;
+  GARY_INIT(rl->sections, 0);
+
+  return rl;
+}
+
+struct request_section *make_new_section(struct request_line *rl)
+{
+  struct request_section *rls = GARY_PUSH(rl->sections);
+  rls->request.ind = num_requests++;
+  rls->request.type = REQUEST_SECTION;
+  rls->num_segments = 0;
+  GARY_INIT(rls->segments, 0);
+
+  return rls;
+}
+
+struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
+{
+  struct request_segment *rs = GARY_PUSH(rls->segments);
+  rls->num_segments++;
+
+  rs->request.ind = num_requests++;
+  rs->request.type = REQUEST_SEGMENT;
+
+  struct point_variant *v = malloc(sizeof(struct point_variant));
+  make_bitmap(v, sym);
+  rs->variant = v;
+
+  return rs;
+}
+
+void cut_edge(struct graph_edge *e, double dist)
+{
+  if (dbg_segments)
+    printf("Cutting [%.2f; %.2f] -- [%.2f; %.2f] to dist %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, dist);
+
+  struct graph_edge *new = malloc(sizeof(struct graph_edge));
+  *new = *e;
+  e->next = new;
+
+  struct osm_node *n1 = e->n1->o;
+  struct osm_node *n2 = e->n2->o;
+
+  // FIXME
+  if ((n1->x == n2->x) && (n1->y == n2->y))
+  {
+    printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
+    printf("Won't cut point\n");
+    return;
+  }
+
+  struct osm_node *n11 = malloc(sizeof(struct osm_node));
+  struct graph_node *gn = malloc(sizeof(struct graph_node));
+  gn->o = n11;
+  double vsize = sqrt(pow(n1->x - n2->x, 2) + pow(n1->y - n2->y, 2));
+  n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
+  n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
+
+  e->n2 = new->n1 = gn;
+
+  e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
+  new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
+}
+
 void make_segments(void)
 {
   for (uns i=0; i<GARY_SIZE(longlines); i++)
@@ -591,23 +732,12 @@ void make_segments(void)
     if (! (longlines[i].first && longlines[i].first->label))
       continue;
 
-    printf("New longline\n");
-
-    struct request_line *request = GARY_PUSH(requests_line);
-    request->request.ind = num_requests++;
-    request->request.type = REQUEST_LINE;
-
-    GARY_INIT(request->sections, 0);
-
-    int cur_length = 0;
-    struct request_section *rls = GARY_PUSH(request->sections);
-    rls->request.ind = num_requests++;
-    rls->request.type = REQUEST_SECTION;
-    rls->num_segments = 0;
-    GARY_INIT(rls->segments, 0);
+    struct request_line *request = make_new_line();
+    struct request_section *rls = make_new_section(request);
+    struct request_segment *rs = NULL;
 
     struct graph_edge *e = longlines[i].first;
-    struct request_segment *rs = NULL;
+    double cur_length = 0;
 
     struct sym_text *st = NULL;
     if (e->label->type == SYMBOLIZER_TEXT)
@@ -621,56 +751,34 @@ void make_segments(void)
       // FIXME;
     }
 
-int dbg_e = 1;
+    printf("New longline\n");
     while (e)
     {
-      printf("Edge %d\n", dbg_e);
-      dbg_e++;
-if (e < (void *) 100)
-{
-  exit(42);
-}
-      if ((cur_length + e->length > conf_max_section_length) &&
-          !(cur_length + e->length < conf_max_section_overlay))
+      if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
       {
-        printf("Making new section, new length would be %f, allowed is %.2f / %.2f\n", cur_length + e->length, conf_max_section_length, conf_max_section_overlay);
-        struct osm_node *n = e->n1->o;
-
-        rs = GARY_PUSH(rls->segments);
-        rs->request.type = REQUEST_SEGMENT;
-        rs->request.ind = num_requests++;
-        rls->num_segments++;
-        rs->x1 = n->x;
-        rs->y1 = n->y;
-        // FIXME: Truly compute x2, y2
-        rs->x2 = n->x;
-        rs->y2 = n->y;
-        rs->zindex = e->zindex;
-        rs->label = e->label;
+        if (dbg_segments)
+          printf("Edge too long, length is %.2f; %.2f - %.2f = %.2f\n", e->length, conf_max_section_length, cur_length, conf_max_section_length - cur_length);
+        cut_edge(e, conf_max_section_length - cur_length);
+      }
 
-        rls = GARY_PUSH(request->sections);
-        rls->request.ind = num_requests++;
-        rls->request.type = REQUEST_SECTION;
-        rls->num_segments = 0;
+      if (cur_length + e->length > conf_max_section_length)
+      {
+        if (dbg_segments)
+          printf("Making new section, new length would be %f, allowed is %.2f / %.2f\n", cur_length + e->length, conf_max_section_length, conf_max_section_overlay);
+
+        struct osm_node *n1 = e->n1->o;
+        struct osm_node *n2 = e->n2->o;
+        rs = make_new_segment(rls, e->label);
+        rs->x1 = n1->x;
+        rs->y1 = n1->y;
+        rs->x2 = n2->x;
+        rs->y2 = n2->y;
+        rs->zindex = e->zindex;
 
-        struct point_variant *v = malloc(sizeof(struct point_variant));
-        switch (e->label->type)
-        {
-          case SYMBOLIZER_POINT:
-            make_bitmap_point(v, (struct sym_point *) e->label);
-            break;
-          case SYMBOLIZER_ICON:
-            make_bitmap_icon(v, (struct sym_icon *) e->label);
-            break;
-          case SYMBOLIZER_TEXT:
-            make_bitmap_label(v, (struct sym_text *) e->label);
-            break;
-          default:
-            // FIXME
-            ;
-        }
-        rs->variant = v;
-        GARY_INIT(rls->segments, 0);
+        rs->label = malloc(sizeof(struct sym_text));
+        *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
+        rls = make_new_section(request);
+        cur_length = 0;
       }
 
       if (st && (e->length < st->tw))
@@ -680,41 +788,20 @@ if (e < (void *) 100)
         continue;
       }
 
-      rs = GARY_PUSH(rls->segments);
-      rls->num_segments++;
-      rs->request.type = REQUEST_SEGMENT;
-      rs->request.ind = num_requests++;
-      rs->label = e->label;
-
-        struct point_variant *v = malloc(sizeof(struct point_variant));
-        switch (e->label->type)
-        {
-          case SYMBOLIZER_POINT:
-            make_bitmap_point(v, (struct sym_point *) e->label);
-            break;
-          case SYMBOLIZER_ICON:
-            make_bitmap_icon(v, (struct sym_icon *) e->label);
-            break;
-          case SYMBOLIZER_TEXT:
-            make_bitmap_label(v, (struct sym_text *) e->label);
-            break;
-          default:
-            // FIXME
-            ;
-        }
-        rs->variant = v;
+      rs = make_new_segment(rls, e->label);
+      rs->label = malloc(sizeof(struct sym_text));
+      *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
 
       rs->x1 = e->n1->o->x;
       rs->y1 = e->n1->o->y;
       rs->x2 = e->n2->o->x;
       rs->y2 = e->n2->o->y;
 
+      // FIXME: Set text rotation
       rs->angle = atan2(rs->x2 - rs->x1, rs->y2 - rs->y1);
-
       rs->zindex = e->zindex;
 
       cur_length += e->length;
-
       e = e->next;
     }
 
@@ -856,110 +943,113 @@ printf("(There are %d requests)\n", num_requests);
   printf("\nTotal penalty: %d\n", individual->penalty);
 }
 
-void labeller_label(void)
+void plan_individual(struct individual *individual)
 {
-  make_graph();
-  label_graph();
-//dump_graph();
-  bfs_wrapper();
-//dump_longlines();
-  make_segments();
-dump_linelabel_requests();
-
-printf("Having %u point requests, %u line requests and %u area requests\n", GARY_SIZE(requests_point), GARY_SIZE(requests_line), GARY_SIZE(requests_area));
-
-  GARY_INIT(population1, conf_pop_size);
-  GARY_INIT(population2, conf_pop_size);
-  make_population();
-
-  printf("Dealing with %d requests\n", num_requests);
-
-/*
-  while (! shall_terminate())
-  {
-    iteration++;
-
-    struct individual **swp = population1;
-    population1 = population2;
-    population2 = swp;
-    pop2_ind = 0;
-  }
-*/
-
-  dump_individual(population1[0]);
-//dump_bitmaps(population1[0]);
-
-  for (uns i=0; i<GARY_SIZE(population1[0]->placements); i++)
+  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
   {
-//printf("(%d) Coping with %d\n", i, population1[0]->placements[i].request->type);
-
     struct symbol *s = NULL;
     z_index_t zindex = 0;
-    switch (population1[0]->placements[i].request->type)
+    if (individual->placements[i].variant_used < 0) continue;
+    switch (individual->placements[i].request->type)
     {
       case REQUEST_POINT: ;
-        struct request_point *rp = (struct request_point *) population1[0]->placements[i].request;
+        struct request_point *rp = (struct request_point *) individual->placements[i].request;
         s = rp->sym;
         zindex = rp->zindex;
-//        printf("%u\n", zindex);
         break;
       case REQUEST_SEGMENT: ;
-        struct request_segment *rs = (struct request_segment *) population1[0]->placements[i].request;
+        struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
         s = rs->label;
-//        printf("Assigned label to s\n");
-//        print_label(s);
         zindex = rs->zindex;
-//        printf("%u\n", zindex);
         break;
       case REQUEST_LINE: ;
-//        printf("*** Line detected ***\n");
         break;
       case REQUEST_AREA: ;
-        struct request_area *ra = (struct request_area *) population1[0]->placements[i].request;
+        struct request_area *ra = (struct request_area *) individual->placements[i].request;
         s = ra->label;
         zindex = ra->zindex;
-//        printf("%u\n", zindex);
         break;
       default:
-//        printf("Testing request type (flushing final placements)\n");
-        ASSERT(population1[0]->placements[i].request != REQUEST_INVALID);
-//        printf("Yep, in default, continuing\n");
+        ASSERT(individual->placements[i].request != REQUEST_INVALID);
         continue;
     }
 
-printf("Will plan symbol at [%.2f; %.2f] on %u\n", population1[0]->placements[i].x, population1[0]->placements[i].y, zindex);
+if (dbg_plan)
+  printf("Will plan symbol at [%.2f; %.2f] on %u\n", individual->placements[i].x, individual->placements[i].y, zindex);
 
     if (s) switch (s->type)
     {
       case SYMBOLIZER_POINT: ;
         struct sym_point *sp = (struct sym_point *) s;
-        sp->x = population1[0]->placements[i].x;
-        sp->y = population1[0]->placements[i].y;
+        sp->x = individual->placements[i].x;
+        sp->y = individual->placements[i].y;
         sym_plan((struct symbol *) sp, zindex);
         break;
       case SYMBOLIZER_ICON: ;
 	struct sym_icon *si = (struct sym_icon *) s;
-	si->sir.x = population1[0]->placements[i].x;
-	si->sir.y = population1[0]->placements[i].y;
+	si->sir.x = individual->placements[i].x;
+	si->sir.y = individual->placements[i].y;
         sym_plan((struct symbol *) si, zindex);
 	break;
       case SYMBOLIZER_TEXT: ;
         struct sym_text *st = (struct sym_text *) s;
-        st->x = population1[0]->placements[i].x;
-        st->y = population1[0]->placements[i].y;
+        st->x = individual->placements[i].x;
+        st->y = individual->placements[i].y;
         st->next_duplicate = NULL;
-        printf("Planning text %s at [%.2f; %.2f] on %u\n", osm_val_decode(st->text), st->x, st->y, zindex);
+        if (dbg_plan) printf("Planning text %s at [%.2f; %.2f] on %u, with rotation %.2f\n", osm_val_decode(st->text), st->x, st->y, zindex, st->rotate);
         sym_plan((struct symbol *) st, zindex);
         break;
       default:
-//        printf("Testing symbolizer type\n");
         ASSERT(s->type != SYMBOLIZER_INVALID);
     }
   }
 
+}
+
+void labeller_label(void)
+{
+  make_graph();
+  label_graph();
+//dump_graph();
+  bfs_wrapper();
+//dump_longlines();
+  make_segments();
+dump_linelabel_requests();
+
+printf("Having %u point requests, %u line requests and %u area requests\n", GARY_SIZE(requests_point), GARY_SIZE(requests_line), GARY_SIZE(requests_area));
+
+  GARY_INIT(population1, conf_pop_size);
+  GARY_INIT(population2, conf_pop_size);
+  make_population();
+
+  printf("Dealing with %d requests\n", num_requests);
+
+/*
+  while (! shall_terminate())
+  {
+    iteration++;
+
+    struct individual **swp = population1;
+    population1 = population2;
+    population2 = swp;
+    pop2_ind = 0;
+  }
+*/
+
+  dump_individual(population1[0]);
+//dump_bitmaps(population1[0]);
+
+  plan_individual(population1[0]);
+
+  labeller_cleanup();
+
   return;
 }
 
+void labeller_cleanup(void)
+{
+}
+
 void make_population(void)
 {
   for (int i=0; i<conf_pop_size; i++)