]> mj.ucw.cz Git - leo.git/blob - map.c
An attempt at simple cartographic generalization
[leo.git] / map.c
1 /*
2  *      Hic Est Leo -- Global Map Operations
3  *
4  *      (c) 2014 Martin Mares <mj@ucw.cz>
5  */
6
7 #include <ucw/lib.h>
8 #include <ucw/conf.h>
9 #include <ucw/gary.h>
10 #include <ucw/mempool.h>
11 #include <ucw/simple-lists.h>
12
13 #include <stdio.h>
14 #include <math.h>
15
16 #include "leo.h"
17 #include "osm.h"
18 #include "shp.h"
19 #include "map.h"
20 #include "css.h"
21 #include "sym.h"
22 #include "fixed.h"
23
24 double map_min_x, map_min_y;
25 double map_max_x, map_max_y;
26 double page_width, page_height;
27 uns map_clip, map_rotate, map_draw_border;
28 char *map_xml_input;
29 char *map_projection;
30 char *map_style_sheet;
31 char *map_svg_output;
32 clist map_sources;
33
34 static struct cf_section map_style_cf = {
35 #define P(x) PTR_TO(struct data_source_style, x)
36   CF_TYPE(struct data_source_style),
37   CF_ITEMS {
38     CF_STRING("Name", P(name)),
39     CF_END
40   }
41 #undef P
42 };
43
44 static const char * const map_formats[] = {
45   "invalid",
46   "osmxml",
47   "fixed",
48   "shape",
49 };
50
51 static struct cf_section map_source_cf = {
52 #define P(x) PTR_TO(struct data_source, x)
53   CF_TYPE(struct data_source),
54   CF_ITEMS {
55     CF_STRING("File", P(file)),
56     CF_LOOKUP("Format", P(format), map_formats),
57     CF_LIST("StyleSheet", P(styles), &map_style_cf),
58     CF_END
59   }
60 #undef P
61 };
62
63 static struct cf_section map_cf = {
64   CF_ITEMS {
65     CF_DOUBLE("MinX", &map_min_x),
66     CF_DOUBLE("MinY", &map_min_y),
67     CF_DOUBLE("MaxX", &map_max_x),
68     CF_DOUBLE("MaxY", &map_max_y),
69     CF_DOUBLE("PageWidth", &page_width),
70     CF_DOUBLE("PageHeight", &page_height),
71     CF_UNS("Clip", &map_clip),
72     CF_UNS("Rotate", &map_rotate),
73     CF_UNS("DrawBorder", &map_draw_border),
74     CF_LIST("Source", &map_sources, &map_source_cf),
75     CF_STRING("Projection", &map_projection),
76     CF_STRING("SVGOutput", &map_svg_output),
77     CF_END
78   }
79 };
80
81 static void CONSTRUCTOR map_preinit(void)
82 {
83   cf_declare_section("Map", &map_cf, 0);
84 }
85
86 // Calculated
87 double map_scale;
88 double page_offset_x, page_offset_y;
89 double page_map_width, page_map_height;
90
91 void map_set_scale(void)
92 {
93   double x_range = map_max_x - map_min_x;
94   double y_range = map_max_y - map_min_y;
95   double x_scale = page_width / x_range;
96   double y_scale = page_height / y_range;
97   map_scale = MIN(x_scale, y_scale);
98   page_map_width = x_range * map_scale;
99   page_map_height = y_range * map_scale;
100   page_offset_x = (page_width - page_map_width) / 2;
101   page_offset_y = (page_height - page_map_height) / 2;
102
103   msg(L_INFO, "Setting scale %.3g (orig window [%.6g,%.6g], page window [%.6g,%.6g]+[%.6g,%.6g] on [%.6g,%.6g])",
104     map_scale,
105     x_range, y_range,
106     page_map_width, page_map_height,
107     page_offset_x, page_offset_y,
108     page_width, page_height);
109
110   double pmin_x = INFINITY, pmax_x = -INFINITY;
111   double pmin_y = INFINITY, pmax_y = -INFINITY;
112   double rmin_x = INFINITY, rmax_x = -INFINITY;
113   double rmin_y = INFINITY, rmax_y = -INFINITY;
114   CLIST_FOR_EACH(struct data_source *, ds, map_sources)
115     {
116       CLIST_FOR_EACH(struct osm_node *, n, ds->osm->obj_list[OSM_TYPE_NODE])
117         {
118           pmin_x = MIN(pmin_x, n->x);
119           pmax_x = MAX(pmax_x, n->x);
120           pmin_y = MIN(pmin_y, n->y);
121           pmax_y = MAX(pmax_y, n->y);
122           n->x = (n->x - map_min_x) * map_scale + page_offset_x;
123           n->y = page_height - page_offset_y - (n->y - map_min_y) * map_scale;
124           rmin_x = MIN(rmin_x, n->x);
125           rmax_x = MAX(rmax_x, n->x);
126           rmin_y = MIN(rmin_y, n->y);
127           rmax_y = MAX(rmax_y, n->y);
128         }
129     }
130   msg(L_INFO, "Bounds before scaling: [%.10g,%.10g] x [%.10g,%.10g]", pmin_x, pmax_x, pmin_y, pmax_y);
131   msg(L_INFO, "Bounds after scaling: [%.10g,%.10g] x [%.10g,%.10g]", rmin_x, rmax_x, rmin_y, rmax_y);
132
133   if (debug_dump_after_scaling)
134     {
135       puts("=== Map after scaling ===");
136       CLIST_FOR_EACH(struct data_source *, ds, map_sources)
137         {
138           osm_this = ds->osm;
139           osm_dump();
140         }
141     }
142 }
143
144 bool map_object_visible_p(struct osm_object *o)
145 {
146   double margin = 10;
147
148   switch (o->type)
149     {
150     case OSM_TYPE_NODE:
151       {
152         struct osm_node *n = (struct osm_node *) o;
153         return (n->x >= page_offset_x - margin && n->x <= page_offset_x + page_map_width + margin &&
154                 n->y >= page_offset_y - margin && n->y <= page_offset_y + page_map_height + margin);
155       }
156     case OSM_TYPE_WAY:
157       {
158         struct osm_way *w = (struct osm_way *) o;
159         bool ok = 0;
160         OSM_FOR_EACH_BEGIN(struct osm_object *, n, w->nodes)
161           {
162             ok |= map_object_visible_p(n);
163           }
164         OSM_FOR_EACH_END;
165         return ok;
166       }
167     case OSM_TYPE_RELATION:
168       {
169         struct osm_relation *r = (struct osm_relation *) o;
170         bool ok = 0;
171         OSM_FOR_EACH_BEGIN(struct osm_object *, n, r->members)
172           {
173             ok |= map_object_visible_p(n);
174           }
175         OSM_FOR_EACH_END;
176         return ok;
177       }
178     case OSM_TYPE_MULTIPOLYGON:
179       return map_object_visible_p(&((struct osm_multipolygon *) o)->rel->o);
180     default:
181       ASSERT(0);
182     }
183 }
184
185 void map_load_styles(void)
186 {
187   clist style_cache;
188   clist_init(&style_cache);
189
190   CLIST_FOR_EACH(struct data_source *, ds, map_sources)
191     {
192       CLIST_FOR_EACH(struct data_source_style *, ss, ds->styles)
193         {
194           CLIST_FOR_EACH(struct simp_node *, n, style_cache)
195             {
196               struct data_source_style *x = n->p;
197               if (!strcmp(x->name, ss->name))
198                 {
199                   ss->css = x->css;
200                   break;
201                 }
202             }
203           if (!ss->css)
204             {
205               msg(L_DEBUG, "Loading style sheet %s", ss->name);
206               ss->css = css_load(ss->name);
207
208               if (debug_dump_css)
209                 {
210                   printf("=== Stylesheet %s ===", ss->name);
211                   css_dump(ss->css);
212                 }
213
214               simp_append(cf_get_pool(), &style_cache)->p = ss;
215             }
216         }
217     }
218 }
219
220 static void map_load_source(struct data_source *ds)
221 {
222   ds->osm = osm_init();
223
224   bool need_mp = 0;
225   bool need_proj = 0;
226
227   switch (ds->format)
228     {
229     case DATA_SOURCE_OSMXML:
230       msg(L_INFO, "Parsing %s as OSM XML", ds->file);
231       if (!ds->file)
232         die("OSM XML data sources must have a file name");
233       osm_xml_parse(ds->file);
234       need_mp = 1;
235       need_proj = 1;
236       break;
237     case DATA_SOURCE_FIXED:
238       msg(L_INFO, "Adding fixed objects");
239       if (!ds->file)
240         ds->file = "fixed";
241       fixed_add();
242       break;
243     case DATA_SOURCE_SHAPE:
244       msg(L_INFO, "Parsing %s as shape file", ds->file);
245       if (!ds->file)
246         die("Shape data sources must have a file name");
247       shp_parse(ds->file);
248       need_proj = 1;
249       break;
250     default:
251       die("Invalid data source format");
252     }
253
254   osm_stats();
255   if (debug_dump_source)
256     {
257       puts("=== Source data ===");
258       osm_dump();
259     }
260   if (need_mp)
261     osm_make_multipolygons();
262
263   if (need_proj)
264     {
265       msg(L_INFO, "Projecting");
266       osm_project(map_projection);
267       if (debug_dump_after_proj)
268         {
269           puts("=== Map after projection ===");
270           osm_dump();
271         }
272     }
273 }
274
275 void map_load_sources(void)
276 {
277   CLIST_FOR_EACH(struct data_source *, ds, map_sources)
278     map_load_source(ds);
279 }
280
281 void map_apply_styles(struct svg *svg)
282 {
283   struct style_results r;
284   style_init(&r);
285
286   CLIST_FOR_EACH(struct data_source *, ds, map_sources)
287     {
288       msg(L_INFO, "Applying stylesheet on %s", ds->file);
289       for (uns i = OSM_TYPE_NODE; i <= OSM_TYPE_MULTIPOLYGON; i++)
290         CLIST_FOR_EACH(struct osm_object *, o, ds->osm->obj_list[i])
291           {
292             if (debug_dump_styling)
293               {
294                 puts("===============================");
295                 osm_obj_dump(o);
296               }
297             if (!map_object_visible_p(o))
298               {
299                 if (debug_dump_styling)
300                   printf("--> invisible\n");
301                 continue;
302               }
303             style_begin(&r, o);
304             CLIST_FOR_EACH(struct data_source_style *, ss, ds->styles)
305               css_apply(ss->css, &r);
306             if (debug_dump_styling)
307               style_dump(&r);
308             sym_from_style(o, &r, svg);
309             style_end(&r);
310           }
311     }
312
313   // FIXME: Ought to destroy the style_results
314 }
315
316 struct gen_context {
317   struct osm_way *w;
318   struct osm_ref **refs;
319   uint in_nodes;
320   uint out_nodes;
321 };
322
323 static void generalize_recursively(struct gen_context *gc, int first, int last)
324 {
325   if (last - first <= 1)
326     return;
327
328   double max_err = 0;
329   struct osm_node *f = (struct osm_node *) gc->refs[first]->o, *l = (struct osm_node *) gc->refs[last]->o;
330   double fx = f->x;
331   double fy = f->y;
332   double dx = l->x - fx;
333   double dy = l->y - fy;
334   double dd = dx*dx + dy*dy;
335
336   for (int i = first + 1; i < last; i++)
337     {
338       struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
339       double nx = n->x - f->x;
340       double ny = n->y - f->y;
341       double p = dx*nx + dy*ny;         // (px,py) = projection of (nx,ny) onto (dx,dy)
342       double px = dx*p / dd;
343       double py = dy*p / dd;
344       double ex = px - nx;              // (ex,ey) is the error vector: (nx,ny) minus its projection
345       double ey = py - ny;
346       double e = ex*ex + ey*ey;
347       max_err = MAX(max_err, e);
348     }
349
350   double close = 5;
351   if (max_err > close*close)
352     {
353       int mid = (first + last) / 2;
354       ASSERT(first < mid && mid < last);
355       generalize_recursively(gc, first, mid);
356       clist_add_tail(&gc->w->nodes, &gc->refs[mid]->n);
357       generalize_recursively(gc, mid, last);
358     }
359 }
360
361 static void generalize_way(struct gen_context *gc, struct osm_way *w)
362 {
363   gc->w = w;
364   GARY_RESIZE(gc->refs, 0);
365
366   CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
367     *GARY_PUSH(gc->refs) = r;
368
369   int N = GARY_SIZE(gc->refs);
370   if (N <= 2)
371     return;
372
373   gc->in_nodes += N;
374
375 #if 0
376   for (int i=0; i<N; i++)
377     {
378       struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
379       msg(L_DEBUG, "Generalize: @%d #%jd [%f,%f]", i, (intmax_t) n->o.id, n->x, n->y);
380     }
381 #endif
382
383   clist_init(&w->nodes);
384   clist_add_tail(&w->nodes, &gc->refs[0]->n);
385   generalize_recursively(gc, 0, N-1);
386   clist_add_tail(&w->nodes, &gc->refs[N-1]->n);
387
388   CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
389     gc->out_nodes++;
390 }
391
392 void map_generalize(void)
393 {
394   msg(L_INFO, "Generalizing ways");
395   struct gen_context gc = { };
396   GARY_INIT(gc.refs, 0);
397
398   CLIST_FOR_EACH(struct data_source *, ds, map_sources)
399     CLIST_FOR_EACH(struct osm_way *, w, ds->osm->obj_list[OSM_TYPE_WAY])
400       generalize_way(&gc, w);
401
402   GARY_FREE(gc.refs);
403
404   msg(L_INFO, "Generalization: %u nodes in, %u nodes out", gc.in_nodes, gc.out_nodes);
405 }