8 #include <ucw/mempool.h>
13 #include "lab-utils.h"
14 #include "lab-bitmaps.h"
15 #include "lab-lines.h"
17 #define BLOCK_SIZE 4096
28 // List of lines (osm_ways) making up a logical line
32 struct graph_edge *first;
39 struct graph_edge **edges;
40 int num; // Used for debug, mostly debug prints
45 osm_id_t id; // Actual line (osm_way) ID
46 struct sym_line *line;
49 z_index_t zindex; // z-index of label
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
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
66 #define HASH_WANT_CLEANUP
67 #include <ucw/hashtable.h>
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);
72 static void make_graph(void);
73 static void label_graph(void);
74 static void make_segments(void);
75 static void make_sections(void);
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);
83 static int num_edges = 0;
84 static int dbg_num_hits = 0;
86 static struct graph_edge **bfs_queue;
88 static double conf_max_section_length = 80, conf_max_section_overlay = 10;
90 static struct cf_section lines_cf = {
92 CF_DOUBLE("MaxSectionLenght", &conf_max_section_length),
93 CF_DOUBLE("MaxSectionOverlay", &conf_max_section_overlay),
100 cf_declare_section("Labelling", &lines_cf, 0);
103 static struct request_line *make_new_line(void)
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);
114 static struct request_section *make_new_section(struct request_line *rl)
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);
125 static struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
127 struct request_segment *rs = GARY_PUSH(rls->segments);
129 rs->request.ind = num_requests++;
130 rs->request.type = REQUEST_SEGMENT;
132 GARY_INIT(rs->request.variants, 0);
135 struct variant *v = GARY_PUSH(rs->request.variants);
142 static void make_graph(void)
145 struct mempool *mp_edges = mp_new(BLOCK_SIZE);
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++)
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;
154 CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
156 // FIXME: Shall osm_object's type be checked here?
157 struct osm_node *o_node = (struct osm_node *) ref->o;
159 struct graph_node *g_node = hash_find(ref->o->id);
162 g_node = hash_new(ref->o->id);
163 GARY_INIT(g_node->edges, 0);
165 g_node->id = ref->o->id;
166 g_node->num = num_nodes++;
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));
186 e->longline = (uns) -1;
187 e->line = buffer_line[i].line;
191 struct graph_edge **edge = GARY_PUSH(g_prev->edges);
193 edge = GARY_PUSH(g_node->edges);
202 void dump_graph(void)
204 HASH_FOR_ALL(hash, node)
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++)
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);
217 // This shouldn't ever happen
218 printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
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");
226 printf(" colored %d;", node->edges[i]->color);
227 printf(" length %.2f", node->edges[i]->length);
234 static void label_graph(void)
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++)
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)
243 DEBUG(dbg_graph, VERBOSITY_PLACEMENT, "Looking for node %ju\n", ref->o->id);
244 struct graph_node *n = hash_find(ref->o->id);
247 printf("BEWARE! Requested node couldn't be found.\n");
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++)
254 if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
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;
266 static void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
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;
271 for (uns i=0; i<GARY_SIZE(node->edges); i++)
273 struct graph_edge *other = node->edges[i];
274 if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
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);
280 other->visited = e->longline;
283 if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
284 ((other->n2->id == node->id) && (other->n1->id == anode->id)))
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))
292 if (! candidate || (other->length > candidate->length))
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;
303 if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
304 ((dir == DIR_FWD) && (other->n2->id == node->id)))
306 struct graph_node *swp = other->n2;
307 other->n2 = other->n1;
316 longlines[other->longline].first = other;
329 static void bfs(uns longline)
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));
334 for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
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));
339 cur->visited = longline;
341 if (cur->longline == (uns) -1)
344 if (cur->dir == DIR_UNSET)
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);
355 bfs_edge(cur, cur->n1, cur->n2, cur->dir);
358 bfs_edge(cur, cur->n2, cur->n1, cur->dir);
368 static void make_sections(void)
370 GARY_INIT(bfs_queue, 0);
371 GARY_INIT(longlines, 0);
373 HASH_FOR_ALL(hash, node)
375 for (uns i=0; i<GARY_SIZE(node->edges); i++)
377 if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
379 GARY_PUSH(longlines);
380 longlines[GARY_SIZE(longlines)-1].first = node->edges[i];
382 DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Running new BFS\n");
383 DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Creating longline %zu\n", GARY_SIZE(longlines)-1);
385 GARY_RESIZE(bfs_queue, 0);
386 struct graph_edge **e = GARY_PUSH(bfs_queue);
388 node->edges[i]->longline = GARY_SIZE(longlines)-1;
389 bfs(node->edges[i]->longline);
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));
398 GARY_FREE(bfs_queue);
401 static void cut_edge(struct graph_edge *e, double dist)
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);
405 struct graph_edge *new = xmalloc(sizeof(struct graph_edge));
409 switch (e->label->type)
411 case SYMBOLIZER_TEXT:
412 new->label = xmalloc(sizeof(struct sym_text));
413 *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
419 struct osm_node *n1 = e->n1->o;
420 struct osm_node *n2 = e->n2->o;
422 if ((n1->x == n2->x) && (n1->y == n2->y))
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");
429 struct osm_node *n11 = xmalloc(sizeof(struct osm_node));
430 struct graph_node *gn = xmalloc(sizeof(struct graph_node));
432 double vsize = hypot(n1->x - n2->x, n1->y - n2->y);
433 n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
434 n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
436 e->n2 = new->n1 = gn;
438 e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
439 new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
443 static void make_segments(void)
445 for (uns i=0; i<GARY_SIZE(longlines); i++)
447 // Skip lines which are not labelled
448 if (! (longlines[i].first && longlines[i].first->label))
451 struct request_line *request = make_new_line();
452 struct request_section *rls = make_new_section(request);
453 struct request_segment *rs = NULL;
455 struct graph_edge *e = longlines[i].first;
456 double cur_length = 0;
458 struct sym_text *st = NULL;
459 if (e->label->type == SYMBOLIZER_TEXT)
461 st = (struct sym_text *) e->label;
465 // FIXME: Should other label types be supported in future?
466 DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping line\n");
470 DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "New longline\n");
476 DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "BEWARE: Edge cycle\n");
481 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);
483 if (st && (e->length < st->tw))
486 DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping segment\n");
490 if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
492 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);
493 // HACK to prevent cutting to 0 lenght
494 cut_edge(e, max2(conf_max_section_length - cur_length, 2));
497 rs = make_new_segment(rls, NULL);
498 rs->label = xmalloc(sizeof(struct sym_text));
499 *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
501 rs->x1 = e->n1->o->x;
502 rs->y1 = e->n1->o->y;
503 rs->x2 = e->n2->o->x;
504 rs->y2 = e->n2->o->y;
506 rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
507 ((struct sym_text *) rs->label)->rotate = convert_to_deg(atan(rs->slope));
508 struct variant *v = GARY_PUSH(rs->request.variants);
509 make_bitmap(v, rs->label);
511 rs->zindex = e->zindex;
513 cur_length += e->length;
514 if (cur_length > conf_max_section_length)
516 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);
518 rls = make_new_section(request);
525 if (GARY_SIZE(request->sections[0].segments) == 0)
527 DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "WARNING: Longline without any segment, skipped\n");
529 struct request_section *rls = &request->sections[0];
530 GARY_FREE(rls->segments);
531 GARY_FREE(rls->request.variants);
533 struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
534 GARY_FREE(rl->sections);
535 GARY_FREE(rl->request.variants);
537 GARY_POP(requests_line);
543 void segment_lines(void)
551 void lines_cleanup(void)
556 void dump_longlines(void)
558 printf("*** Longlines dump\n");
559 for (uns i=0; i<GARY_SIZE(longlines); i++)
561 printf("Longline %u:", i);
562 struct graph_edge *e = longlines[i].first;
563 if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
564 printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
569 printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
570 e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);