lab-lines.c

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