]> mj.ucw.cz Git - leo.git/blob - lab-lines.c
Labelling: Support for better bitmaps granularity
[leo.git] / 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 }