X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=labeller.c;h=1db25fca59721a57be2199c4e79154de98772460;hb=3232a51a5fed20b6d3f0d6b9df0b8c66fdc75ca4;hp=a3b681838480563f84d68265f90dbec3fb6b7806;hpb=2ca3cf1910c2e7448d008cd77a7832971d067922;p=leo.git

diff --git a/labeller.c b/labeller.c
index a3b6818..1db25fc 100644
--- a/labeller.c
+++ b/labeller.c
@@ -48,6 +48,9 @@ int dbg_graph = 0;
 int dbg_bfs = 0;
 int dbg_map_parts = 0;
 int dbg_movement = 0;
+int dbg_init = 0;
+int dbg_overlaps = 0;
+int dbg_rank = 0;
 
 int page_width_int;
 int page_height_int;
@@ -107,6 +110,10 @@ void join_edge(struct graph_edge *e, int dir);
 void bfs(uns longline);
 void make_segments(void);
 
+int overlaps(struct placement *p1, struct placement *p2);
+int get_overlap(struct placement *p);
+int individual_overlap(struct individual *individual);
+
 void make_population(void);
 bool shall_terminate(void);
 void breed(void);
@@ -115,6 +122,8 @@ void elite(void);
 void rank_population(void);
 void plan_individual(struct individual *individual);
 
+int cmp_individual(const void *a, const void *b);
+
 void make_bitmap(struct variant *v, struct symbol *sym);
 void make_bitmap_icon(struct variant *v, struct sym_icon *si);
 void make_bitmap_point(struct variant *v, struct sym_point *sp);
@@ -251,16 +260,16 @@ void make_bitmap(struct variant *v, struct symbol *sym)
 
 void make_bitmap_icon(struct variant *v, struct sym_icon *si)
 {
-  v->width = si->sir.icon->width;
-  v->height = si->sir.icon->height;
-  v->bitmap = malloc((int) ceil(v->width * v->height * sizeof(bool)));
+  v->width = si->sir.width + 1;
+  v->height = si->sir.height + 1;
+  v->bitmap = malloc(v->width * v->height * sizeof(bool));
   for (int i=0; i<v->width*v->height; i++) v->bitmap[i] = 1;
 }
 
 void make_bitmap_point(struct variant *v, struct sym_point *sp)
 {
-  v->width = v->height = sp->size;
-  v->bitmap = malloc(sp->size*sp->size * sizeof(bool));
+  v->width = v->height = sp->size + 1;
+  v->bitmap = malloc(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;
 }
@@ -279,7 +288,8 @@ void make_bitmap_label(struct variant *v, struct sym_text *text)
 
 void labeller_add_point(struct symbol *sym, struct osm_object *object, z_index_t zindex)
 {
-printf("Adding point\n");
+  if (dbg_requests)
+    printf("Adding point\n");
   if (object->type != OSM_TYPE_NODE)
   {
     printf("Warning: Point label requested on non-point object\n");
@@ -345,7 +355,8 @@ void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t
     return;
   }
 
-  printf("[LAB] Labelling way %ju on %u\n", o->id, zindex);
+  if (dbg_requests)
+    printf("[LAB] Labelling way %ju on %u\n", o->id, zindex);
   struct buffer_linelabel *ll = GARY_PUSH(buffer_linelabel);
   ll->way = (struct osm_way *) o;
   ll->label = sym;
@@ -354,7 +365,8 @@ void labeller_add_linelabel(struct symbol *sym, struct osm_object *o, z_index_t
 
 void labeller_add_arealabel(struct symbol *sym, struct osm_object *o, z_index_t zindex)
 {
-printf("Adding area on %u\n", zindex);
+  if (dbg_requests)
+    printf("Adding area on %u\n", zindex);
   struct request_area *r = GARY_PUSH(requests_area);
 
   r->request.type = REQUEST_AREA;
@@ -371,11 +383,13 @@ printf("Adding area on %u\n", zindex);
   switch (sym->type)
   {
     case SYMBOLIZER_ICON:
-      printf("DEBUG: Icon label\n");
+      if (dbg_requests)
+        printf("DEBUG: Icon label\n");
       make_bitmap_icon(v, (struct sym_icon *) sym);
       break;
     case SYMBOLIZER_TEXT:
-      printf("DEBUG: Text label\n");
+      if (dbg_requests)
+        printf("DEBUG: Text label\n");
       make_bitmap_label(v, (struct sym_text *) sym);
     default:
       // FIXME
@@ -719,6 +733,8 @@ void cut_edge(struct graph_edge *e, double dist)
   *new = *e;
   e->next = new;
 
+  // FIXME? Create new label for new edge, don't only copy pointer?
+
   struct osm_node *n1 = e->n1->o;
   struct osm_node *n2 = e->n2->o;
 
@@ -871,7 +887,8 @@ void dump_bitmaps(struct individual *individual)
 
   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
   {
-fprintf(stderr, "%d-th placement\n", i);
+    if (individual->placements[i].variant_used == -1) continue;
+
     struct placement *p = &(individual->placements[i]);
     struct variant *v = NULL;
 
@@ -883,19 +900,14 @@ fprintf(stderr, "%d-th placement\n", i);
         v = &(p->request->variants[p->variant_used]);
         break;
       default:
-        printf("Testing request type (dump_bitmaps): %d\n", p->request->type);
         ASSERT(p->request->type != REQUEST_INVALID);
         continue;
     }
 
-    printf("Got after with %d-th placement of request type %d\n", i, p->request->type);
-
-    printf("Rendering %d-th label %d x %d (w x h)\n", i, v->width, v->height);
     for (int row = max2(p->y, 0); row < min2(p->y + v->height, page_height_int); row++)
     {
       for (int col = max2(p->x, 0); col < min2(p->x + v->width, page_width_int); col++)
       {
-        printf("Writing to %d\n", row*page_width_int + col);
         bitmap[row * page_width_int + col] = 1;
       }
     }
@@ -1062,7 +1074,12 @@ void make_population(void)
 {
   for (int i=0; i<conf_pop_size; i++)
   {
-    printf("Making individual %d\n", i);
+    struct individual *i2 = ep_alloc(ep_individuals);
+    init_individual(i2);
+    population2[i] = i2;
+
+    if (dbg_init)
+      printf("Making individual %d\n", i);
     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
     population1[i] = individual;
 
@@ -1245,9 +1262,121 @@ void elite(void)
   }
 }
 
+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]);
+
+  int p1x = p1->x; int p1y = p1->y;
+  int p2x = p2->x; int p2y = p2->y;
+
+  int overlap = 0;
+  for (int y=max2(p1y, p2y); y<=min2(p1y+v1->height, p2y+v2->height); y++)
+    for (int x=max2(p1x, p2x); x<=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)
+{
+  struct map_part **parts = get_map_parts(p);
+  if (! parts)
+  {
+    if (dbg_overlaps)
+      printf("Placement of request %d seems not to be placed\n", p->request->ind);
+    return 0;
+  }
+
+  struct placement **others;
+  bool *planned;
+
+  GARY_INIT_ZERO(planned, num_requests);
+  planned[p->request->ind] = 1;
+  GARY_INIT(others, 0);
+
+  for (uns i=0; i<GARY_SIZE(parts); i++)
+  {
+    struct map_placement *mp = parts[i]->placement->next;
+    while (mp)
+    {
+      if (! planned[mp->placement->request->ind])
+      {
+        struct placement **p = GARY_PUSH(others);
+        *p = mp->placement;
+        planned[mp->placement->request->ind] = true;
+      }
+      mp = mp->next;
+    }
+  }
+
+  int overlap = 0;
+  for (uns i=0; i<GARY_SIZE(others); i++)
+  {
+    overlap += overlaps(p, others[i]);
+  }
+
+  GARY_FREE(planned);
+  GARY_FREE(parts);
+  GARY_FREE(others);
+
+  return overlap;
+}
+
+int individual_overlap(struct individual *individual)
+{
+  int overlap = 0;
+
+  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+  {
+    overlap += get_overlap(&individual->placements[i]);
+  }
+
+  return overlap;
+}
+
+int cmp_individual(const void *a, const void *b)
+{
+  struct individual **ia = (struct individual **) a;
+  struct individual **ib = (struct individual **) b;
+
+  return (*ia)->penalty - (*ib)->penalty;
+}
+
 void rank_population(void)
 {
-  // FIXME
+  int penalty;
+
+  for (int i=0; i<conf_pop_size; i++)
+  {
+    if (dbg_rank)
+      printf("Individual %d\n", i);
+    population1[i]->penalty = 0;
+
+    penalty = individual_overlap(population1[i]);
+    if (dbg_rank)
+      printf("Increasing penalty by %d for overlap\n", penalty);
+    population1[i]->penalty += penalty;
+  }
 }
 
 struct map_part **get_map_parts(struct placement *p)
@@ -1384,7 +1513,8 @@ void gen_coords_area(struct placement *p)
   p->x = p->x + gen_movement();
   p->y = p->y + gen_movement();
 
-  printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
+  if (dbg_movement)
+    printf("Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
 }
 
 struct map_part **get_parts(struct placement *symbol, struct individual *individual)
@@ -1542,7 +1672,8 @@ void init_placement(struct placement *p, struct individual *individual, struct r
   }
 
   gen_coords(p);
-//  printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
+  if (dbg_init)
+    printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
 }
 
 void init_individual(struct individual *i)
@@ -1559,6 +1690,9 @@ void init_individual(struct individual *i)
     mp->next = mp->prev = NULL;
   }
   i->penalty = 0; // FIXME
+
+  if (dbg_init)
+    printf("Individual inited, has %u map parts\n", GARY_SIZE(i->map));
 }
 
 struct placement **get_overlapping(struct placement *p UNUSED)
@@ -1580,8 +1714,7 @@ int flip(int a, int b)
 
 double randdouble(void)
 {
-  // FIXME: How the hell shall double in range <0, 1> be generated? O:)
-  return 0.5;
+  return ((double) rand() / (double) RAND_MAX);
 }
 
 void cleanup(void)
@@ -1594,10 +1727,19 @@ void cleanup(void)
 
 void copy_individual(struct individual *src, struct individual *dest)
 {
-  src->penalty = dest->penalty;
+  dest->penalty = src->penalty;
   GARY_INIT(dest->placements, GARY_SIZE(src->placements));
   for (uns i=0; i<GARY_SIZE(src->placements); i++)
   {
     dest->placements[i] = src->placements[i];
+    dest->placements[i].map_links = NULL;
+  }
+  for (uns j=0; j<num_map_parts; j++)
+  {
+    struct map_part *part = GARY_PUSH(dest->map);
+    GARY_INIT(part->placement, 0);
+    struct map_placement *mp = GARY_PUSH(part->placement);
+    mp->placement = &dummy_placement;
+    mp->next = mp->prev = NULL;
   }
 }