lab-lines.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4
   5 #include <ucw/lib.h>
   6 #include <ucw/conf.h>
   7 #include <ucw/gary.h>
   8 #include <ucw/mempool.h>
   9
  10 #include "leo.h"
  11 #include "sym.h"
  12 #include "labeller.h"
  13 #include "lab-utils.h"
  14 #include "lab-bitmaps.h"
  15 #include "lab-lines.h"
  16
  17 #define BLOCK_SIZE 4096
  18
  19 enum edge_dir
  20 {
  21   DIR_INVALID,
  22   DIR_UNSET,
  23   DIR_CENTER,
  24   DIR_FWD,
  25   DIR_BWD,
  26 };
  27
  28 // List of lines (osm_ways) making up a logical line
  29 struct longline
  30 {
  31   uns id;
  32   struct graph_edge *first;
  33 };
  34
  35 struct graph_node
  36 {
  37   osm_id_t id;
  38   struct osm_node *o;
  39   struct graph_edge **edges;
  40   int num;      // Used for debug, mostly debug prints
  41 };
  42
  43 struct graph_edge
  44 {
  45   osm_id_t id;                  // Actual line (osm_way) ID
  46   struct sym_line *line;
  47   color_t color;
  48   struct symbol *label;
  49   z_index_t zindex;             // z-index of label
  50   double length;
  51   int visited;                  // Iteration when line was last visited with BFS
  52   uns longline;                 // Logical line this line was made part of
  53   enum edge_dir dir;            // Direction with respect to logical line, used by BFS
  54   struct graph_node *n1;        // Actual line endpoints
  55   struct graph_node *n2;
  56   struct graph_edge *prev;      // Neighbouring lines in logical line
  57   struct graph_edge *next;
  58   int num;                      // Used for debug
  59 };
  60
  61 #define HASH_NODE struct graph_node
  62 #define HASH_PREFIX(x) hash_##x
  63 #define HASH_KEY_ATOMIC id
  64 #define HASH_WANT_FIND
  65 #define HASH_WANT_NEW
  66 #define HASH_WANT_CLEANUP
  67 #include <ucw/hashtable.h>
  68
  69 static void bfs(uns longline);
  70 static void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
  71
  72 static void make_graph(void);
  73 static void label_graph(void);
  74 static void make_segments(void);
  75 static void make_sections(void);
  76
  77 static void cut_edge(struct graph_edge *e, double dist);
  78 static struct request_line *make_new_line(void);
  79 static struct request_section *make_new_section(struct request_line *rl);
  80 static struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
  81
  82 static int num_nodes;
  83 static int num_edges = 0;
  84 static int dbg_num_hits = 0;
  85
  86 static struct graph_edge **bfs_queue;
  87
  88 static double conf_max_section_length = 80, conf_max_section_overlay = 10;
  89
  90 static struct cf_section lines_cf = {
  91   CF_ITEMS {
  92     CF_DOUBLE("MaxSectionLenght", &conf_max_section_length),
  93     CF_DOUBLE("MaxSectionOverlay", &conf_max_section_overlay),
  94     CF_END
  95   }
  96 };
  97
  98 void lines_conf(void)
  99 {
 100   cf_declare_section("Labelling", &lines_cf, 0);
 101 }
 102
 103 static struct request_line *make_new_line(void)
 104 {
 105   struct request_line *rl = GARY_PUSH(requests_line);
 106   rl->request.ind = num_requests++;
 107   rl->request.type = REQUEST_LINE;
 108   GARY_INIT(rl->sections, 0);
 109   GARY_INIT(rl->request.variants, 0);
 110
 111   return rl;
 112 }
 113
 114 static struct request_section *make_new_section(struct request_line *rl)
 115 {
 116   struct request_section *rls = GARY_PUSH(rl->sections);
 117   rls->request.ind = num_requests++;
 118   rls->request.type = REQUEST_SECTION;
 119   GARY_INIT(rls->segments, 0);
 120   GARY_INIT(rls->request.variants, 0);
 121
 122   return rls;
 123 }
 124
 125 static struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
 126 {
 127   struct request_segment *rs = GARY_PUSH(rls->segments);
 128
 129   rs->request.ind = num_requests++;
 130   rs->request.type = REQUEST_SEGMENT;
 131
 132   GARY_INIT(rs->request.variants, 0);
 133   if (sym)
 134   {
 135     struct variant *v = GARY_PUSH(rs->request.variants);
 136     make_bitmap(v, sym);
 137   }
 138
 139   return rs;
 140 }
 141
 142 static void make_graph(void)
 143 {
 144   hash_init();
 145   struct mempool *mp_edges = mp_new(BLOCK_SIZE);
 146
 147   DEBUG(dbg_graph, VERBOSITY_GENERAL, "Extracting nodes, will iterate over %zu ways\n", GARY_SIZE(buffer_line));
 148   for (uns i=0; i<GARY_SIZE(buffer_line); i++)
 149   {
 150     struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
 151     struct graph_node *g_prev = NULL;
 152     struct osm_node *o_prev = NULL;
 153
 154     CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
 155     {
 156       // FIXME: Shall osm_object's type be checked here?
 157       struct osm_node *o_node = (struct osm_node *) ref->o;
 158
 159       struct graph_node *g_node = hash_find(ref->o->id);
 160       if (!g_node)
 161       {
 162         g_node = hash_new(ref->o->id);
 163         GARY_INIT(g_node->edges, 0);
 164         g_node->o = o_node;
 165         g_node->id = ref->o->id;
 166         g_node->num = num_nodes++;
 167       }
 168
 169       if (! g_prev)
 170       {
 171         g_prev = g_node;
 172         o_prev = o_node;
 173         continue;
 174       }
 175
 176       struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
 177       e->num = num_edges++;
 178       e->id = buffer_line[i].line->s.o->id;
 179       e->color = buffer_line[i].line->color;
 180       e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
 181       e->visited = -1;
 182       e->prev = NULL;
 183       e->next = NULL;
 184       e->n1 = g_prev;
 185       e->n2 = g_node;
 186       e->longline = (uns) -1;
 187       e->line = buffer_line[i].line;
 188       e->dir = DIR_UNSET;
 189       e->label = NULL;
 190
 191       struct graph_edge **edge = GARY_PUSH(g_prev->edges);
 192       *edge = e;
 193       edge = GARY_PUSH(g_node->edges);
 194       *edge = e;
 195
 196       g_prev = g_node;
 197       o_prev = o_node;
 198     }
 199   }
 200 }
 201
 202 void dump_graph(void)
 203 {
 204   HASH_FOR_ALL(hash, node)
 205   {
 206     printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
 207     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 208     {
 209       struct graph_edge *e = node->edges[i];
 210       printf("\t edge (%d) #%ju to ", e->num, e->id);
 211       if (node->edges[i]->n1->id == node->id)
 212         printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
 213       else if (node->edges[i]->n2->id == node->id)
 214         printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
 215       else
 216       {
 217         // This shouldn't ever happen
 218         printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
 219       }
 220
 221       printf("\t\t");
 222
 223       if ((node->edges[i]->label) && (node->edges[i]->label->type == SYMBOLIZER_TEXT)) printf(" labelled %s;", osm_val_decode(((struct sym_text *) node->edges[i]->label)->text));
 224       else if ((node->edges[i]->label)) printf("Labelled\n");
 225
 226       printf(" colored %d;", node->edges[i]->color);
 227       printf("   length %.2f", node->edges[i]->length);
 228       printf("\n");
 229     }
 230   }
 231   HASH_END_FOR;
 232 }
 233
 234 static void label_graph(void)
 235 {
 236   DEBUG(dbg_graph, VERBOSITY_GENERAL, "There are %zu line labels requested\n", GARY_SIZE(buffer_linelabel));
 237   for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
 238   {
 239     if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
 240     DEBUG(dbg_graph, VERBOSITY_INDIVIDUAL, "Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
 241     CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
 242     {
 243       DEBUG(dbg_graph, VERBOSITY_PLACEMENT, "Looking for node %ju\n", ref->o->id);
 244       struct graph_node *n = hash_find(ref->o->id);
 245       if (n == NULL)
 246       {
 247         printf("BEWARE! Requested node couldn't be found.\n");
 248       }
 249       else
 250       {
 251         DEBUG(dbg_graph, VERBOSITY_ALL, "Searching among %zu edges\n", GARY_SIZE(n->edges));
 252         for (uns j=0; j<GARY_SIZE(n->edges); j++)
 253         {
 254           if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
 255           {
 256             DEBUG(dbg_graph, VERBOSITY_ALL, "Labelling node %ju\n", n->id);
 257             n->edges[j]->label = buffer_linelabel[i].label;
 258             n->edges[j]->zindex = buffer_linelabel[i].zindex;
 259           }
 260         }
 261       }
 262     }
 263   }
 264 }
 265
 266 static void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
 267 {
 268   DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
 269   struct graph_edge *candidate = NULL;
 270
 271   for (uns i=0; i<GARY_SIZE(node->edges); i++)
 272   {
 273     struct graph_edge *other = node->edges[i];
 274     if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
 275
 276     if ((uns) other->visited != e->longline) {
 277     DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "Pushing new edge %d / %ju\n", other->num, other->id);
 278     struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
 279     *e_ptr = other;
 280     other->visited = e->longline;
 281     }
 282
 283     if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
 284         ((other->n2->id == node->id) && (other->n1->id == anode->id)))
 285         continue;
 286
 287     if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
 288         (e->label) && (other->label) &&
 289         (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
 290         (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
 291     {
 292       if (! candidate || (other->length > candidate->length))
 293       candidate = other;
 294     }
 295   }
 296
 297   if (candidate)
 298   {
 299     DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "New line in longline %u\n", e->longline);
 300     struct graph_edge *other = candidate;
 301       other->longline = e->longline;
 302       other->dir = dir;
 303       if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
 304           ((dir == DIR_FWD) && (other->n2->id == node->id)))
 305       {
 306         struct graph_node *swp = other->n2;
 307         other->n2 = other->n1;
 308         other->n1 = swp;
 309       }
 310
 311       switch (dir)
 312       {
 313         case DIR_BWD:
 314           e->prev = other;
 315           other->next = e;
 316           longlines[other->longline].first = other;
 317           break;
 318         case DIR_FWD:
 319           e->next = other;
 320           other->prev = e;
 321           break;
 322         default:
 323           printf("Oops\n");
 324           ASSERT(0);
 325       }
 326   }
 327 }
 328
 329 static void bfs(uns longline)
 330 {
 331   DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "BFS called for longline %u\n", longline);
 332   DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "%zu longlines exist\n", GARY_SIZE(longlines));
 333
 334   for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
 335   {
 336     struct graph_edge *cur = bfs_queue[i];
 337     DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "Exploring new edge %d; %zu remaining\n", cur->num, GARY_SIZE(bfs_queue));
 338
 339     cur->visited = longline;
 340
 341     if (cur->longline == (uns) -1)
 342       continue;
 343
 344     if (cur->dir == DIR_UNSET)
 345     {
 346       cur->dir = DIR_CENTER;
 347       bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
 348       bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
 349     }
 350     else
 351     {
 352       switch (cur->dir)
 353       {
 354         case DIR_BWD:
 355           bfs_edge(cur, cur->n1, cur->n2, cur->dir);
 356           break;
 357         case DIR_FWD:
 358           bfs_edge(cur, cur->n2, cur->n1, cur->dir);
 359           break;
 360         default:
 361           // FIXME
 362           ;
 363       }
 364     }
 365   }
 366 }
 367
 368 static void make_sections(void)
 369 {
 370   GARY_INIT(bfs_queue, 0);
 371   GARY_INIT(longlines, 0);
 372
 373   HASH_FOR_ALL(hash, node)
 374   {
 375     for (uns i=0; i<GARY_SIZE(node->edges); i++)
 376     {
 377       if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
 378       {
 379         GARY_PUSH(longlines);
 380         longlines[GARY_SIZE(longlines)-1].first = node->edges[i];
 381
 382         DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Running new BFS\n");
 383         DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Creating longline %zu\n", GARY_SIZE(longlines)-1);
 384
 385         GARY_RESIZE(bfs_queue, 0);
 386         struct graph_edge **e = GARY_PUSH(bfs_queue);
 387         *e = node->edges[i];
 388         node->edges[i]->longline = GARY_SIZE(longlines)-1;
 389         bfs(node->edges[i]->longline);
 390
 391         DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
 392         DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Planned %zu edges\n", GARY_SIZE(bfs_queue));
 393       }
 394     }
 395   }
 396   HASH_END_FOR;
 397
 398   GARY_FREE(bfs_queue);
 399 }
 400
 401 static void cut_edge(struct graph_edge *e, double dist)
 402 {
 403   DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "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);
 404
 405   struct graph_edge *new = xmalloc(sizeof(struct graph_edge));
 406   *new = *e;
 407   e->next = new;
 408
 409   switch (e->label->type)
 410   {
 411     case SYMBOLIZER_TEXT:
 412       new->label = xmalloc(sizeof(struct sym_text));
 413       *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
 414       break;
 415     default:
 416       ;
 417   }
 418
 419   struct osm_node *n1 = e->n1->o;
 420   struct osm_node *n2 = e->n2->o;
 421
 422   if ((n1->x == n2->x) && (n1->y == n2->y))
 423   {
 424     printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
 425     DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Won't cut point\n");
 426     return;
 427   }
 428
 429   // BEWARE: This creates new OSM object and modifies original data
 430   // FIXME: Though this doesn't crash anything now, it could become deathly curse one day
 431   struct osm_node *n11 = xmalloc(sizeof(struct osm_node));
 432   struct graph_node *gn = xmalloc(sizeof(struct graph_node));
 433   gn->o = n11;
 434   double vsize = hypot(n1->x - n2->x, n1->y - n2->y);
 435   n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
 436   n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
 437
 438   e->n2 = new->n1 = gn;
 439
 440   e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
 441   new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
 442   new->visited = 0;
 443 }
 444
 445 static void make_segments(void)
 446 {
 447   for (uns i=0; i<GARY_SIZE(longlines); i++)
 448   {
 449     // Skip lines which are not labelled
 450     if (! (longlines[i].first && longlines[i].first->label))
 451       continue;
 452
 453     struct request_line *request = make_new_line();
 454     struct request_section *rls = make_new_section(request);
 455     struct request_segment *rs = NULL;
 456
 457     struct graph_edge *e = longlines[i].first;
 458     double cur_length = 0;
 459
 460     struct sym_text *st = NULL;
 461     if (e->label->type == SYMBOLIZER_TEXT)
 462     {
 463       st = (struct sym_text *) e->label;
 464     }
 465     else
 466     {
 467       // FIXME: Should other label types be supported in future?
 468       DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping line\n");
 469       continue;
 470     }
 471
 472     DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "New longline\n");
 473
 474     while (e)
 475     {
 476       if (e->visited < 0)
 477       {
 478         DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "BEWARE: Edge cycle\n");
 479         break;
 480       }
 481       e->visited = -1;
 482
 483       DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Taking edge from [%.2f; %.2f] to [%.2f; %.2f] of length %.2f\n", e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->length);
 484
 485       if (st && (e->length < st->tw))
 486       {
 487         e = e->next;
 488         DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping segment\n");
 489         continue;
 490       }
 491
 492       if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
 493       {
 494         DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Edge too long, length is %.2f; %.2f - %.2f = %.2f\n", e->length, conf_max_section_length, cur_length, conf_max_section_length - cur_length);
 495         // HACK to prevent cutting to 0 lenght
 496         cut_edge(e, max2(conf_max_section_length - cur_length, 2));
 497       }
 498
 499       rs = make_new_segment(rls, NULL);
 500       rs->label = xmalloc(sizeof(struct sym_text));
 501       *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
 502
 503       rs->x1 = e->n1->o->x;
 504       rs->y1 = e->n1->o->y;
 505       rs->x2 = e->n2->o->x;
 506       rs->y2 = e->n2->o->y;
 507
 508       rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
 509       ((struct sym_text *) rs->label)->rotate = convert_to_deg(atan(rs->slope));
 510       struct variant *v = GARY_PUSH(rs->request.variants);
 511       make_bitmap(v, rs->label);
 512
 513       rs->zindex = e->zindex;
 514
 515       cur_length += e->length;
 516       if (cur_length > conf_max_section_length)
 517       {
 518         DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "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);
 519
 520         rls = make_new_section(request);
 521         cur_length = 0;
 522       }
 523
 524       e = e->next;
 525     }
 526
 527     if (GARY_SIZE(request->sections[0].segments) == 0)
 528     {
 529       DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "WARNING: Longline without any segment, skipped\n");
 530
 531       struct request_section *rls = &request->sections[0];
 532       GARY_FREE(rls->segments);
 533       GARY_FREE(rls->request.variants);
 534
 535       struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
 536       GARY_FREE(rl->sections);
 537       GARY_FREE(rl->request.variants);
 538
 539       GARY_POP(requests_line);
 540       num_requests -= 2;
 541     }
 542   }
 543 }
 544
 545 void segment_lines(void)
 546 {
 547   make_graph();
 548   label_graph();
 549   make_sections();
 550   make_segments();
 551 }
 552
 553 void lines_cleanup(void)
 554 {
 555   hash_cleanup();
 556 }
 557
 558 void dump_longlines(void)
 559 {
 560   printf("*** Longlines dump\n");
 561   for (uns i=0; i<GARY_SIZE(longlines); i++)
 562   {
 563     printf("Longline %u:", i);
 564     struct graph_edge *e = longlines[i].first;
 565     if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
 566       printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
 567     printf("\n");
 568
 569     while (e)
 570     {
 571       printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
 572              e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);
 573
 574       e = e->next;
 575     }
 576   }
 577 }