--- /dev/null
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+#include <ucw/lib.h>
+#include <ucw/conf.h>
+#include <ucw/gary.h>
+#include <ucw/mempool.h>
+
+#include "leo.h"
+#include "sym.h"
+#include "labeller.h"
+#include "lab-utils.h"
+#include "lab-bitmaps.h"
+#include "lab-lines.h"
+
+#define BLOCK_SIZE 4096
+
+enum edge_dir
+{
+ DIR_INVALID,
+ DIR_UNSET,
+ DIR_CENTER,
+ DIR_FWD,
+ DIR_BWD,
+};
+
+struct longline
+{
+ uns id;
+ struct graph_edge *first;
+};
+
+struct graph_node
+{
+ osm_id_t id;
+ struct osm_node *o;
+ struct graph_edge **edges;
+ int num;
+};
+
+struct graph_edge
+{
+ osm_id_t id;
+ double length;
+ color_t color;
+ int visited;
+ struct graph_edge *prev;
+ struct graph_edge *next;
+ struct graph_node *n1;
+ struct graph_node *n2;
+ uns longline;
+ struct symbol *label;
+ struct sym_line *line;
+ z_index_t zindex;
+ enum edge_dir dir;
+ struct graph_node *anode;
+ struct graph_node *bnode; // DEBUG PRINT
+ int num; // DEBUG
+};
+
+#define HASH_NODE struct graph_node
+#define HASH_PREFIX(x) hash_##x
+#define HASH_KEY_ATOMIC id
+#define HASH_WANT_FIND
+#define HASH_WANT_NEW
+#define HASH_WANT_CLEANUP
+#include <ucw/hashtable.h>
+
+static void bfs(uns longline);
+static void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir);
+
+static void make_graph(void);
+static void label_graph(void);
+static void make_segments(void);
+static void make_sections(void);
+
+static void cut_edge(struct graph_edge *e, double dist);
+static struct request_line *make_new_line(void);
+static struct request_section *make_new_section(struct request_line *rl);
+static struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym);
+
+static int num_nodes;
+static int num_edges = 0;
+static int dbg_num_hits = 0;
+
+static struct graph_edge **bfs_queue;
+
+static double conf_max_section_length = 80, conf_max_section_overlay = 10;
+
+static struct cf_section lines_cf = {
+ CF_ITEMS {
+ CF_DOUBLE("MaxSectionLenght", &conf_max_section_length),
+ CF_DOUBLE("MaxSectionOverlay", &conf_max_section_overlay),
+ CF_END
+ }
+};
+
+void lines_conf(void)
+{
+ cf_declare_section("Labelling", &lines_cf, 0);
+}
+
+static struct request_line *make_new_line(void)
+{
+ struct request_line *rl = GARY_PUSH(requests_line);
+ rl->request.ind = num_requests++;
+ rl->request.type = REQUEST_LINE;
+ GARY_INIT(rl->sections, 0);
+ GARY_INIT(rl->request.variants, 0);
+
+ return rl;
+}
+
+static struct request_section *make_new_section(struct request_line *rl)
+{
+ struct request_section *rls = GARY_PUSH(rl->sections);
+ rls->request.ind = num_requests++;
+ rls->request.type = REQUEST_SECTION;
+ rls->num_segments = 0;
+ GARY_INIT(rls->segments, 0);
+ GARY_INIT(rls->request.variants, 0);
+
+ return rls;
+}
+
+static struct request_segment *make_new_segment(struct request_section *rls, struct symbol *sym)
+{
+ struct request_segment *rs = GARY_PUSH(rls->segments);
+ rls->num_segments++;
+
+ rs->request.ind = num_requests++;
+ rs->request.type = REQUEST_SEGMENT;
+
+ GARY_INIT(rs->request.variants, 0);
+ if (sym)
+ {
+ struct variant *v = GARY_PUSH(rs->request.variants);
+ make_bitmap(v, sym);
+ }
+
+ return rs;
+}
+
+static void make_graph(void)
+{
+ hash_init();
+ struct mempool *mp_edges = mp_new(BLOCK_SIZE);
+
+ DEBUG(dbg_graph, VERBOSITY_GENERAL, "Extracting nodes, will iterate over %zu ways\n", GARY_SIZE(buffer_line));
+ for (uns i=0; i<GARY_SIZE(buffer_line); i++)
+ {
+ struct osm_way *way = (struct osm_way *) buffer_line[i].line->s.o;
+ struct graph_node *g_prev = NULL;
+ struct osm_node *o_prev = NULL;
+
+ CLIST_FOR_EACH(struct osm_ref *, ref, way->nodes)
+ {
+ // FIXME: Shall osm_object's type be checked here?
+ struct osm_node *o_node = (struct osm_node *) ref->o;
+
+ struct graph_node *g_node = hash_find(ref->o->id);
+ if (!g_node)
+ {
+ g_node = hash_new(ref->o->id);
+ GARY_INIT(g_node->edges, 0);
+ g_node->o = o_node;
+ g_node->id = ref->o->id;
+ g_node->num = num_nodes++;
+ }
+
+ if (! g_prev)
+ {
+ g_prev = g_node;
+ o_prev = o_node;
+ continue;
+ }
+
+ struct graph_edge *e = mp_alloc(mp_edges, sizeof(struct graph_edge));
+ e->num = num_edges++;
+ e->id = buffer_line[i].line->s.o->id;
+ e->color = buffer_line[i].line->color;
+ e->length = hypot(abs(o_prev->x - o_node->x), abs(o_prev->y - o_node->y));
+ e->visited = -1;
+ e->prev = NULL;
+ e->next = NULL;
+ e->n1 = g_prev;
+ e->n2 = g_node;
+ e->longline = (uns) -1;
+ e->line = buffer_line[i].line;
+ e->dir = DIR_UNSET;
+ e->label = NULL;
+
+ struct graph_edge **edge = GARY_PUSH(g_prev->edges);
+ *edge = e;
+ edge = GARY_PUSH(g_node->edges);
+ *edge = e;
+
+ g_prev = g_node;
+ o_prev = o_node;
+ }
+ }
+}
+
+void dump_graph(void)
+{
+ HASH_FOR_ALL(hash, node)
+ {
+ printf("* Node: (%d) #%ju [%.2f; %.2f]\n", node->num, node->id, node->o->x, node->o->y);
+ for (uns i=0; i<GARY_SIZE(node->edges); i++)
+ {
+ struct graph_edge *e = node->edges[i];
+ printf("\t edge (%d) #%ju to ", e->num, e->id);
+ if (node->edges[i]->n1->id == node->id)
+ printf("(%d) #%ju [%.2f; %.2f]\n", e->n2->num, e->n2->id, e->n2->o->x, e->n2->o->y);
+ else if (node->edges[i]->n2->id == node->id)
+ printf("(%d) #%ju [%.2f; %.2f]\n", e->n1->num, e->n1->id, e->n1->o->x, e->n1->o->y);
+ else
+ {
+ // This shouldn't ever happen
+ printf("BEWARE! Edge is associated with a node it doesn't belongs to!\n");
+ }
+
+ printf("\t\t");
+
+ 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));
+ else if ((node->edges[i]->label)) printf("Labelled\n");
+
+ printf(" colored %d;", node->edges[i]->color);
+ printf(" length %.2f", node->edges[i]->length);
+ printf("\n");
+ }
+ }
+ HASH_END_FOR;
+}
+
+static void label_graph(void)
+{
+ DEBUG(dbg_graph, VERBOSITY_GENERAL, "There are %zu line labels requested\n", GARY_SIZE(buffer_linelabel));
+ for (uns i=0; i<GARY_SIZE(buffer_linelabel); i++)
+ {
+ if (buffer_linelabel[i].label->type == SYMBOLIZER_TEXT)
+ DEBUG(dbg_graph, VERBOSITY_INDIVIDUAL, "Labelling nodes of way %s\n", osm_val_decode(((struct sym_text *) buffer_linelabel[i].label)->text));
+ CLIST_FOR_EACH(struct osm_ref *, ref, buffer_linelabel[i].way->nodes)
+ {
+ DEBUG(dbg_graph, VERBOSITY_PLACEMENT, "Looking for node %ju\n", ref->o->id);
+ struct graph_node *n = hash_find(ref->o->id);
+ if (n == NULL)
+ {
+ printf("BEWARE! Requested node couldn't be found.\n");
+ }
+ else
+ {
+ DEBUG(dbg_graph, VERBOSITY_ALL, "Searching among %zu edges\n", GARY_SIZE(n->edges));
+ for (uns j=0; j<GARY_SIZE(n->edges); j++)
+ {
+ if (n->edges[j]->id == buffer_linelabel[i].way->o.id)
+ {
+ DEBUG(dbg_graph, VERBOSITY_ALL, "Labelling node %ju\n", n->id);
+ n->edges[j]->label = buffer_linelabel[i].label;
+ n->edges[j]->zindex = buffer_linelabel[i].zindex;
+ }
+ }
+ }
+ }
+ }
+}
+
+static void bfs_edge(struct graph_edge *e, struct graph_node *node, struct graph_node *anode, enum edge_dir dir)
+{
+ DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "BFS edge called for edge %d (going %d) in direction %d\n", e->num, e->dir, dir);
+ struct graph_edge *candidate = NULL;
+
+ for (uns i=0; i<GARY_SIZE(node->edges); i++)
+ {
+ struct graph_edge *other = node->edges[i];
+ if ((other->longline != (uns) -1) && (other->longline != e->longline)) continue;
+
+ if ((uns) other->visited != e->longline) {
+ DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "Pushing new edge %d / %ju\n", other->num, other->id);
+ struct graph_edge **e_ptr = GARY_PUSH(bfs_queue);
+ *e_ptr = other;
+ other->visited = e->longline;
+ }
+
+ if (((other->n1->id == node->id) && (other->n2->id == anode->id)) ||
+ ((other->n2->id == node->id) && (other->n1->id == anode->id)))
+ continue;
+
+ if (((other->n1->id == node->id) || (other->n2->id == node->id)) &&
+ (e->label) && (other->label) &&
+ (e->label->type == SYMBOLIZER_TEXT) && (other->label->type == SYMBOLIZER_TEXT) &&
+ (((struct sym_text *) e->label)->text == ((struct sym_text *) other->label)->text))
+ {
+ if (! candidate || (other->length > candidate->length))
+ candidate = other;
+ }
+ }
+
+ if (candidate)
+ {
+ DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "New line in longline %u\n", e->longline);
+ struct graph_edge *other = candidate;
+ other->longline = e->longline;
+ other->dir = dir;
+ if (((dir == DIR_BWD) && (other->n1->id == node->id)) ||
+ ((dir == DIR_FWD) && (other->n2->id == node->id)))
+ {
+ struct graph_node *swp = other->n2;
+ other->n2 = other->n1;
+ other->n1 = swp;
+ }
+
+ switch (dir)
+ {
+ case DIR_BWD:
+ e->prev = other;
+ other->next = e;
+ longlines[other->longline].first = other;
+ break;
+ case DIR_FWD:
+ e->next = other;
+ other->prev = e;
+ break;
+ default:
+ printf("Oops\n");
+ ASSERT(0);
+ }
+ }
+}
+
+static void bfs(uns longline)
+{
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "BFS called for longline %u\n", longline);
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "%zu longlines exist\n", GARY_SIZE(longlines));
+
+ for (uns i=0; i<GARY_SIZE(bfs_queue); i++)
+ {
+ struct graph_edge *cur = bfs_queue[i];
+ DEBUG(dbg_bfs, VERBOSITY_PLACEMENT, "Exploring new edge %d; %zu remaining\n", cur->num, GARY_SIZE(bfs_queue));
+
+ cur->visited = longline;
+
+ if (cur->longline == (uns) -1)
+ continue;
+
+ if (cur->dir == DIR_UNSET)
+ {
+ cur->dir = DIR_CENTER;
+ bfs_edge(cur, cur->n1, cur->n2, DIR_BWD);
+ bfs_edge(cur, cur->n2, cur->n1, DIR_FWD);
+ }
+ else
+ {
+ switch (cur->dir)
+ {
+ case DIR_BWD:
+ bfs_edge(cur, cur->n1, cur->n2, cur->dir);
+ break;
+ case DIR_FWD:
+ bfs_edge(cur, cur->n2, cur->n1, cur->dir);
+ break;
+ default:
+ // FIXME
+ ;
+ }
+ }
+ }
+}
+
+static void make_sections(void)
+{
+ GARY_INIT(bfs_queue, 0);
+ GARY_INIT(longlines, 0);
+
+ HASH_FOR_ALL(hash, node)
+ {
+ for (uns i=0; i<GARY_SIZE(node->edges); i++)
+ {
+ if ((node->edges[i]->label) && (node->edges[i]->longline == (uns) -1))
+ {
+ GARY_PUSH(longlines);
+ longlines[GARY_SIZE(longlines)-1].first = node->edges[i];
+
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Running new BFS\n");
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Creating longline %zu\n", GARY_SIZE(longlines)-1);
+
+ GARY_RESIZE(bfs_queue, 0);
+ struct graph_edge **e = GARY_PUSH(bfs_queue);
+ *e = node->edges[i];
+ node->edges[i]->longline = GARY_SIZE(longlines)-1;
+ bfs(node->edges[i]->longline);
+
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Joined %d edges\n", dbg_num_hits); dbg_num_hits = 0;
+ DEBUG(dbg_bfs, VERBOSITY_INDIVIDUAL, "Planned %zu edges\n", GARY_SIZE(bfs_queue));
+ }
+ }
+ }
+ HASH_END_FOR;
+
+ GARY_FREE(bfs_queue);
+}
+
+static void cut_edge(struct graph_edge *e, double dist)
+{
+ 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);
+
+ struct graph_edge *new = xmalloc(sizeof(struct graph_edge));
+ *new = *e;
+ e->next = new;
+
+ switch (e->label->type)
+ {
+ case SYMBOLIZER_TEXT:
+ new->label = xmalloc(sizeof(struct sym_text));
+ *((struct sym_text *) new->label) = *((struct sym_text *) e->label);
+ break;
+ default:
+ ;
+ }
+
+ struct osm_node *n1 = e->n1->o;
+ struct osm_node *n2 = e->n2->o;
+
+ if ((n1->x == n2->x) && (n1->y == n2->y))
+ {
+ printf("[%.2f; %.2f] -- [%.2f; %.2f]\n", n1->x, n1->y, n2->x, n2->y);
+ DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Won't cut point\n");
+ return;
+ }
+
+ struct osm_node *n11 = xmalloc(sizeof(struct osm_node));
+ struct graph_node *gn = xmalloc(sizeof(struct graph_node));
+ gn->o = n11;
+ double vsize = hypot(n1->x - n2->x, n1->y - n2->y);
+ n11->x = n1->x + (n2->x - n1->x) / vsize * dist;
+ n11->y = n1->y + (n2->y - n1->y) / vsize * dist;
+
+ e->n2 = new->n1 = gn;
+
+ e->length = hypot(abs(n1->x - n11->x), abs(n1->y - n11->y));
+ new->length = hypot(abs(n11->x - n2->x), abs(n11->y - n2->y));
+ new->visited = 0;
+}
+
+static void make_segments(void)
+{
+ for (uns i=0; i<GARY_SIZE(longlines); i++)
+ {
+ // Skip lines which are not labelled
+ if (! (longlines[i].first && longlines[i].first->label))
+ continue;
+
+ struct request_line *request = make_new_line();
+ struct request_section *rls = make_new_section(request);
+ struct request_segment *rs = NULL;
+
+ struct graph_edge *e = longlines[i].first;
+ double cur_length = 0;
+
+ struct sym_text *st = NULL;
+ if (e->label->type == SYMBOLIZER_TEXT)
+ {
+ st = (struct sym_text *) e->label;
+ }
+ else
+ {
+ // FIXME: Should other label types be supported in future?
+ DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping line\n");
+ continue;
+ }
+
+ DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "New longline\n");
+
+ while (e)
+ {
+ if (e->visited < 0)
+ {
+ DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "BEWARE: Edge cycle\n");
+ break;
+ }
+ e->visited = -1;
+
+ 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);
+
+ if (st && (e->length < st->tw))
+ {
+ e = e->next;
+ DEBUG(dbg_segments, VERBOSITY_PLACEMENT, "Warning: Skipping segment\n");
+ continue;
+ }
+
+ if (cur_length + e->length > conf_max_section_length + conf_max_section_overlay)
+ {
+ 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);
+ // HACK to prevent cutting to 0 lenght
+ cut_edge(e, max2(conf_max_section_length - cur_length, 2));
+ }
+
+ rs = make_new_segment(rls, NULL);
+ rs->label = xmalloc(sizeof(struct sym_text));
+ *((struct sym_text *) rs->label) = *((struct sym_text *) e->label);
+
+ rs->x1 = e->n1->o->x;
+ rs->y1 = e->n1->o->y;
+ rs->x2 = e->n2->o->x;
+ rs->y2 = e->n2->o->y;
+
+ rs->slope = (rs->y2 - rs->y1) / (rs->x2 - rs->x1);
+ ((struct sym_text *) rs->label)->rotate = convert_to_deg(atan(rs->slope));
+ struct variant *v = GARY_PUSH(rs->request.variants);
+ make_bitmap(v, rs->label);
+
+ rs->zindex = e->zindex;
+
+ cur_length += e->length;
+ if (cur_length > conf_max_section_length)
+ {
+ 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);
+
+ rls = make_new_section(request);
+ cur_length = 0;
+ }
+
+ e = e->next;
+ }
+
+ if (request->sections[0].num_segments == 0)
+ {
+ DEBUG(dbg_segments, VERBOSITY_INDIVIDUAL, "WARNING: Longline without any segment, skipped\n");
+
+ struct request_section *rls = &request->sections[0];
+ GARY_FREE(rls->segments);
+ GARY_FREE(rls->request.variants);
+
+ struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
+ GARY_FREE(rl->sections);
+ GARY_FREE(rl->request.variants);
+
+ GARY_POP(requests_line);
+ num_requests -= 2;
+ }
+ }
+}
+
+void segment_lines(void)
+{
+ make_graph();
+ label_graph();
+ make_sections();
+ make_segments();
+}
+
+void lines_cleanup(void)
+{
+ hash_cleanup();
+}
+
+void dump_longlines(void)
+{
+ printf("*** Longlines dump\n");
+ for (uns i=0; i<GARY_SIZE(longlines); i++)
+ {
+ printf("Longline %u:", i);
+ struct graph_edge *e = longlines[i].first;
+ if ((e->label) && (e->label->type == SYMBOLIZER_TEXT))
+ printf(" labelled %s", osm_val_decode(((struct sym_text *) e->label)->text));
+ printf("\n");
+
+ while (e)
+ {
+ printf("\t#%ju (%d): [%.2f; %.2f] -- [%.2f; %.2f] (dir %d)\n",
+ e->id, e->num, e->n1->o->x, e->n1->o->y, e->n2->o->x, e->n2->o->y, e->dir);
+
+ e = e->next;
+ }
+ }
+}
projects / leo.git / blobdiff