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