Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2021 James Westman <james@jwestman.net>
3 : : *
4 : : * This library is free software; you can redistribute it and/or
5 : : * modify it under the terms of the GNU Lesser General Public
6 : : * License as published by the Free Software Foundation; either
7 : : * version 2.1 of the License, or (at your option) any later version.
8 : : *
9 : : * This library is distributed in the hope that it will be useful,
10 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : : * Lesser General Public License for more details.
13 : : *
14 : : * You should have received a copy of the GNU Lesser General Public
15 : : * License along with this library; if not, see <https://www.gnu.org/licenses/>.
16 : : */
17 : :
18 : : #include "shumate-vector-renderer.h"
19 : : #include "shumate-vector-utils-private.h"
20 : :
21 : : gboolean
22 : 90 : shumate_vector_json_get_object (JsonNode *node, JsonObject **dest, GError **error)
23 : : {
24 [ + - ]: 90 : g_assert (node != NULL);
25 [ - + ]: 90 : g_assert (dest != NULL);
26 : :
27 [ - + ]: 90 : if (!JSON_NODE_HOLDS_OBJECT (node))
28 : : {
29 : 0 : g_set_error (error,
30 : : SHUMATE_STYLE_ERROR,
31 : : SHUMATE_STYLE_ERROR_MALFORMED_STYLE,
32 : : "Expected object, got %s",
33 : : json_node_type_name (node));
34 : 0 : return FALSE;
35 : : }
36 : :
37 : 90 : *dest = json_node_get_object (node);
38 : 90 : return TRUE;
39 : : }
40 : :
41 : :
42 : : gboolean
43 : 57 : shumate_vector_json_get_array (JsonNode *node, JsonArray **dest, GError **error)
44 : : {
45 [ + - ]: 57 : g_assert (node != NULL);
46 [ - + ]: 57 : g_assert (dest != NULL);
47 : :
48 [ - + ]: 57 : if (!JSON_NODE_HOLDS_ARRAY (node))
49 : : {
50 : 0 : g_set_error (error,
51 : : SHUMATE_STYLE_ERROR,
52 : : SHUMATE_STYLE_ERROR_MALFORMED_STYLE,
53 : : "Expected array, got %s",
54 : : json_node_type_name (node));
55 : 0 : return FALSE;
56 : : }
57 : :
58 : 57 : *dest = json_node_get_array (node);
59 : 57 : return TRUE;
60 : : }
61 : :
62 : : gboolean
63 : 42 : shumate_vector_json_get_string (JsonNode *node,
64 : : const char **dest,
65 : : GError **error)
66 : : {
67 [ + - ]: 42 : g_assert (node != NULL);
68 [ - + ]: 42 : g_assert (dest != NULL);
69 : :
70 [ + - - + ]: 42 : if (!JSON_NODE_HOLDS_VALUE (node) || json_node_get_value_type (node) != G_TYPE_STRING)
71 : : {
72 : 0 : g_set_error (error,
73 : : SHUMATE_STYLE_ERROR,
74 : : SHUMATE_STYLE_ERROR_MALFORMED_STYLE,
75 : : "Expected string, got %s",
76 : : json_node_type_name (node));
77 : 0 : return FALSE;
78 : : }
79 : :
80 : 42 : *dest = json_node_get_string (node);
81 : 42 : return TRUE;
82 : : }
83 : :
84 : :
85 : : JsonNode *
86 : 54 : get_member (JsonObject *object,
87 : : const char *name)
88 : : {
89 [ + - ]: 54 : if (object == NULL)
90 : : return FALSE;
91 : 54 : return json_object_get_member (object, name);
92 : : }
93 : :
94 : :
95 : : gboolean
96 : 0 : shumate_vector_json_get_object_member (JsonObject *object,
97 : : const char *name,
98 : : JsonObject **dest,
99 : : GError **error)
100 : : {
101 : 0 : JsonNode *node;
102 : :
103 [ # # ]: 0 : g_assert (dest != NULL);
104 : :
105 : 0 : node = get_member (object, name);
106 [ # # ]: 0 : if (node == NULL)
107 : : {
108 : 0 : *dest = NULL;
109 : 0 : return TRUE;
110 : : }
111 : :
112 : 0 : return shumate_vector_json_get_object (node, dest, error);
113 : : }
114 : :
115 : :
116 : : gboolean
117 : 12 : shumate_vector_json_get_array_member (JsonObject *object,
118 : : const char *name,
119 : : JsonArray **dest,
120 : : GError **error)
121 : : {
122 : 12 : JsonNode *node;
123 : :
124 [ + - ]: 12 : g_assert (dest != NULL);
125 : :
126 : 12 : node = get_member (object, name);
127 [ + + ]: 12 : if (node == NULL)
128 : : {
129 : 6 : *dest = NULL;
130 : 6 : return TRUE;
131 : : }
132 : :
133 : 6 : return shumate_vector_json_get_array (node, dest, error);
134 : : }
135 : :
136 : :
137 : : gboolean
138 : 42 : shumate_vector_json_get_string_member (JsonObject *object,
139 : : const char *name,
140 : : const char **dest,
141 : : GError **error)
142 : : {
143 : 42 : JsonNode *node;
144 : :
145 [ + - ]: 42 : g_assert (dest != NULL);
146 : :
147 : 42 : node = get_member (object, name);
148 [ + + ]: 42 : if (node == NULL)
149 : : {
150 : 12 : *dest = NULL;
151 : 12 : return TRUE;
152 : : }
153 : :
154 : 30 : return shumate_vector_json_get_string (node, dest, error);
155 : : }
156 : :
157 : :
158 : : void
159 : 0 : shumate_vector_point_iter_init (ShumateVectorPointIter *iter,
160 : : ShumateVectorLineString *linestring)
161 : : {
162 : 0 : *iter = (ShumateVectorPointIter) {
163 : 0 : .num_points = linestring->n_points,
164 : 0 : .points = linestring->points,
165 : : .current_point = 0,
166 : : .distance = 0,
167 : : .reversed = FALSE,
168 : : };
169 : 0 : }
170 : :
171 : :
172 : : gboolean
173 : 0 : shumate_vector_point_iter_is_at_end (ShumateVectorPointIter *iter)
174 : : {
175 [ # # ]: 0 : if (iter->reversed)
176 : 0 : return iter->current_point == 0;
177 : : else
178 : 0 : return iter->current_point >= iter->num_points - 1;
179 : : }
180 : :
181 : :
182 : : double
183 : 0 : shumate_vector_point_iter_next_segment (ShumateVectorPointIter *iter)
184 : : {
185 : 0 : double res;
186 : :
187 [ # # ]: 0 : if (shumate_vector_point_iter_is_at_end (iter))
188 : : return 0;
189 : :
190 : 0 : res = shumate_vector_point_iter_get_segment_length (iter) - iter->distance;
191 : 0 : iter->distance = 0;
192 : :
193 [ # # ]: 0 : if (iter->reversed)
194 : 0 : iter->current_point --;
195 : : else
196 : 0 : iter->current_point ++;
197 : :
198 : : return res;
199 : : }
200 : :
201 : :
202 : : static double
203 : 0 : point_distance_sq (ShumateVectorPoint *a,
204 : : ShumateVectorPoint *b)
205 : : {
206 : 0 : double x = a->x - b->x;
207 : 0 : double y = a->y - b->y;
208 : 0 : return x * x + y * y;
209 : : }
210 : :
211 : : static double
212 : 0 : point_distance (ShumateVectorPoint *a,
213 : : ShumateVectorPoint *b)
214 : : {
215 : 0 : return sqrt (point_distance_sq (a, b));
216 : : }
217 : :
218 : : static ShumateVectorPoint *
219 : 0 : get_prev_point (ShumateVectorPointIter *iter)
220 : : {
221 [ # # ]: 0 : g_assert (iter->current_point < iter->num_points);
222 : 0 : return &iter->points[iter->current_point];
223 : : }
224 : :
225 : : static ShumateVectorPoint *
226 : 0 : get_next_point (ShumateVectorPointIter *iter)
227 : : {
228 [ # # ]: 0 : g_assert (iter->current_point < iter->num_points);
229 : :
230 [ # # ]: 0 : if (iter->reversed)
231 : : {
232 [ # # ]: 0 : if (iter->current_point == 0)
233 : 0 : return &iter->points[0];
234 : : else
235 : 0 : return &iter->points[iter->current_point - 1];
236 : : }
237 : : else
238 : : {
239 [ # # ]: 0 : if (iter->current_point >= iter->num_points - 1)
240 : 0 : return &iter->points[iter->num_points - 1];
241 : : else
242 : 0 : return &iter->points[iter->current_point + 1];
243 : : }
244 : : }
245 : :
246 : : static void
247 : 0 : normalize (ShumateVectorPoint *point)
248 : : {
249 : 0 : double len = sqrt (point->x*point->x + point->y*point->y);
250 [ # # ]: 0 : if (len == 0)
251 : : {
252 : 0 : point->x = 0;
253 : 0 : point->y = 0;
254 : : }
255 : : else
256 : : {
257 : 0 : point->x /= len;
258 : 0 : point->y /= len;
259 : : }
260 : 0 : }
261 : :
262 : :
263 : : double
264 : 0 : shumate_vector_point_iter_get_segment_length (ShumateVectorPointIter *iter)
265 : : {
266 : 0 : ShumateVectorPoint *prev = get_prev_point (iter), *next = get_next_point (iter);
267 : 0 : return point_distance (prev, next);
268 : : }
269 : :
270 : :
271 : : void
272 : 0 : shumate_vector_point_iter_get_segment_center (ShumateVectorPointIter *iter,
273 : : double remaining_distance,
274 : : ShumateVectorPoint *result)
275 : : {
276 : : /* Gets the center point of the rest of the current segment, up to the given remaining distance. */
277 : :
278 : 0 : ShumateVectorPoint *prev = get_prev_point (iter), *next = get_next_point (iter);
279 [ # # ]: 0 : float distance = MIN (remaining_distance, point_distance (prev, next) - iter->distance) / 2 + iter->distance;
280 : :
281 : 0 : result->x = next->x - prev->x;
282 : 0 : result->y = next->y - prev->y;
283 : 0 : normalize (result);
284 : :
285 : 0 : result->x *= distance;
286 : 0 : result->y *= distance;
287 : 0 : result->x += prev->x;
288 : 0 : result->y += prev->y;
289 : 0 : }
290 : :
291 : :
292 : : void
293 : 0 : shumate_vector_point_iter_get_current_point (ShumateVectorPointIter *iter,
294 : : ShumateVectorPoint *result)
295 : : {
296 : 0 : ShumateVectorPoint *prev = get_prev_point (iter), *next = get_next_point (iter);
297 : :
298 : 0 : result->x = next->x - prev->x;
299 : 0 : result->y = next->y - prev->y;
300 : 0 : normalize (result);
301 : :
302 : 0 : result->x *= iter->distance;
303 : 0 : result->y *= iter->distance;
304 : 0 : result->x += prev->x;
305 : 0 : result->y += prev->y;
306 : 0 : }
307 : :
308 : :
309 : : void
310 : 0 : shumate_vector_point_iter_advance (ShumateVectorPointIter *iter,
311 : : double distance)
312 : : {
313 [ # # # # ]: 0 : while (distance > 0 && !shumate_vector_point_iter_is_at_end (iter))
314 : : {
315 [ # # ]: 0 : if (iter->distance + distance > shumate_vector_point_iter_get_segment_length (iter))
316 : 0 : distance -= shumate_vector_point_iter_next_segment (iter);
317 : : else
318 : : {
319 : 0 : iter->distance += distance;
320 : 0 : return;
321 : : }
322 : : }
323 : : }
324 : :
325 : :
326 : : double
327 : 0 : shumate_vector_point_iter_get_current_angle (ShumateVectorPointIter *iter)
328 : : {
329 : 0 : ShumateVectorPoint *prev = get_prev_point (iter), *next = get_next_point (iter);
330 : 0 : return atan2 (next->y - prev->y, next->x - prev->x);
331 : : }
332 : :
333 : :
334 : : double
335 : 0 : shumate_vector_point_iter_get_average_angle (ShumateVectorPointIter *iter,
336 : : double remaining_distance)
337 : : {
338 : 0 : ShumateVectorPointIter iter2 = *iter;
339 : 0 : double sum_x = 0.0, sum_y = 0.0;
340 : :
341 [ # # # # ]: 0 : while (remaining_distance > 0 && !shumate_vector_point_iter_is_at_end (&iter2))
342 : : {
343 : 0 : double len = shumate_vector_point_iter_get_segment_length (&iter2);
344 : 0 : double scale;
345 : :
346 [ # # ]: 0 : if (len != 0)
347 : : {
348 [ # # ]: 0 : scale = MIN (remaining_distance, len - iter2.distance) / len;
349 : 0 : sum_x += (get_next_point (&iter2)->x - get_prev_point (&iter2)->x) * scale;
350 : 0 : sum_y += (get_next_point (&iter2)->y - get_prev_point (&iter2)->y) * scale;
351 : : }
352 : :
353 : 0 : remaining_distance -= shumate_vector_point_iter_next_segment (&iter2);
354 : : }
355 : :
356 : 0 : return atan2 (sum_y, sum_x);
357 : : }
358 : :
359 : :
360 : : ShumateVectorLineString *
361 : 0 : shumate_vector_line_string_copy (ShumateVectorLineString *linestring)
362 : : {
363 : 0 : ShumateVectorLineString *copy = g_new0 (ShumateVectorLineString, 1);
364 : 0 : copy->n_points = linestring->n_points;
365 : 0 : copy->points = g_memdup2 (linestring->points, linestring->n_points * sizeof (ShumateVectorPoint));
366 : 0 : return copy;
367 : : }
368 : :
369 : : void
370 : 15 : shumate_vector_line_string_free (ShumateVectorLineString *linestring)
371 : : {
372 [ + - ]: 15 : g_clear_pointer (&linestring->points, g_free);
373 : 15 : g_free (linestring);
374 : 15 : }
375 : :
376 : :
377 : : double
378 : 0 : shumate_vector_line_string_length (ShumateVectorLineString *linestring)
379 : : {
380 : 0 : ShumateVectorPointIter iter;
381 : 0 : double len, sum = 0;
382 : :
383 : 0 : shumate_vector_point_iter_init (&iter, linestring);
384 : :
385 [ # # ]: 0 : while ((len = shumate_vector_point_iter_next_segment (&iter)))
386 : 0 : sum += len;
387 : :
388 : 0 : return sum;
389 : : }
390 : :
391 : :
392 : : void
393 : 0 : shumate_vector_line_string_bounds (ShumateVectorLineString *linestring,
394 : : ShumateVectorPoint *radius_out,
395 : : ShumateVectorPoint *center_out)
396 : : {
397 : 0 : guint i;
398 : 0 : float min_x, max_x, min_y, max_y;
399 : :
400 [ # # ]: 0 : g_return_if_fail (linestring->n_points > 0);
401 : :
402 : 0 : min_x = max_x = linestring->points[0].x;
403 : 0 : min_y = max_y = linestring->points[0].y;
404 : :
405 [ # # ]: 0 : for (i = 1; i < linestring->n_points; i ++)
406 : : {
407 [ # # ]: 0 : min_x = MIN (min_x, linestring->points[i].x);
408 [ # # ]: 0 : max_x = MAX (max_x, linestring->points[i].x);
409 [ # # ]: 0 : min_y = MIN (min_y, linestring->points[i].y);
410 [ # # ]: 0 : max_y = MAX (max_y, linestring->points[i].y);
411 : : }
412 : :
413 : 0 : radius_out->x = (max_x - min_x) / 2.0;
414 : 0 : radius_out->y = (max_y - min_y) / 2.0;
415 : 0 : center_out->x = (max_x + min_x) / 2.0;
416 : 0 : center_out->y = (max_y + min_y) / 2.0;
417 : : }
418 : :
419 : :
420 : : GPtrArray *
421 : 0 : shumate_vector_line_string_simplify (ShumateVectorLineString *linestring)
422 : : {
423 : 0 : gsize i;
424 : 0 : GPtrArray *result = g_ptr_array_new ();
425 : :
426 : 0 : g_ptr_array_add (result, linestring);
427 : :
428 [ # # ]: 0 : if (linestring->n_points <= 2)
429 : : return result;
430 : :
431 : : /* The glyph layout algorithm for line symbols does not handle high detail
432 : : * very well. Lots of short segments with different angles cause it to place
433 : : * glyphs too close together and with "random" rotations, which makes text
434 : : * illegible.
435 : : *
436 : : * I tried several solutions. Simplification (such as the Visvalingam-Whyatt
437 : : * algorithm) creates too many sharp angles, which produces poor results.
438 : : * I also tried a smoothing algorithm which averages each point with its
439 : : * neighbors, and while that produced good results with natural lines like
440 : : * rivers, it deformed street labels that already looked fine, causing them
441 : : * not to line up with the street anymore.
442 : : *
443 : : * The following algorithm reduces detail only where it exists. It works by
444 : : * repeatedly merging the closest pair of neighboring points until no two
445 : : * points in the line are closer than a threshold.
446 : : * */
447 : :
448 : 0 : while (TRUE)
449 : : {
450 : 0 : gint min_idx = -1;
451 : :
452 : : /* Square the threshold because we compare it to the square of the
453 : : * distance (saving a sqrt() call). The unit is the size of a tile. */
454 : 0 : float min_distance = 0.025 * 0.025;
455 : :
456 : : /* Find the closest pair of points, excepting the first and last pair
457 : : * because we don't want to change the endpoints */
458 [ # # ]: 0 : for (i = 1; i < linestring->n_points - 2; i ++)
459 : : {
460 : 0 : float distance = point_distance_sq (&linestring->points[i], &linestring->points[i + 1]);
461 [ # # ]: 0 : if (distance < min_distance)
462 : : {
463 : 0 : min_idx = i;
464 : 0 : min_distance = distance;
465 : : }
466 : : }
467 : :
468 [ # # # # ]: 0 : if (min_idx == -1 || linestring->n_points <= 2)
469 : : break;
470 : :
471 : : /* Set the first point in the pair to the average of the two */
472 : 0 : linestring->points[min_idx] = (ShumateVectorPoint) {
473 : 0 : (linestring->points[min_idx].x + linestring->points[min_idx + 1].x) / 2.0,
474 : 0 : (linestring->points[min_idx].y + linestring->points[min_idx + 1].y) / 2.0,
475 : : };
476 : :
477 : : /* Remove the second point by shifting everything after it */
478 : 0 : linestring->n_points --;
479 [ # # ]: 0 : for (i = min_idx + 1; i < linestring->n_points; i ++)
480 : 0 : linestring->points[i] = linestring->points[i + 1];
481 : : }
482 : :
483 : : /* Line labels also don't look good if there's sharp angles. To fix that, we
484 : : * split the line wherever one occurs. */
485 : :
486 [ # # ]: 0 : for (i = linestring->n_points - 2; i >= 1; i --)
487 : : {
488 : : /* Angle between three points. See https://math.stackexchange.com/a/3427603 */
489 : :
490 : : /* Dot product of points[i] to points[i - 1], and points[i] to points[i + 1] */
491 : 0 : float dot = (linestring->points[i].x - linestring->points[i + 1].x)
492 : 0 : * (linestring->points[i].x - linestring->points[i - 1].x)
493 : 0 : + ((linestring->points[i].y - linestring->points[i + 1].y)
494 : 0 : * (linestring->points[i].y - linestring->points[i - 1].y));
495 : :
496 : 0 : float len = sqrt (point_distance_sq (&linestring->points[i], &linestring->points[i + 1])
497 : 0 : * point_distance_sq (&linestring->points[i], &linestring->points[i - 1]));
498 : :
499 : 0 : float angle = fabs (acos (dot / len));
500 : :
501 [ # # ]: 0 : if (angle < 120 * G_PI / 180)
502 : : {
503 : 0 : ShumateVectorLineString *new_line = g_new (ShumateVectorLineString, 1);
504 : :
505 : : /* Copy from the current point until the end of the line */
506 : 0 : new_line->n_points = linestring->n_points - i;
507 : 0 : new_line->points = g_memdup2 (&linestring->points[i], new_line->n_points * sizeof (ShumateVectorPoint));
508 : :
509 : 0 : linestring->n_points = i + 1;
510 : :
511 : 0 : g_ptr_array_add (result, new_line);
512 : : }
513 : : }
514 : :
515 : : return result;
516 : : }
517 : :
518 : : static int
519 : 645 : zigzag (guint value)
520 : : {
521 : 645 : return (value >> 1) ^ (-(value & 1));
522 : : }
523 : :
524 : : gboolean
525 : 855 : shumate_vector_geometry_iter (ShumateVectorGeometryIter *iter)
526 : : {
527 : 855 : int cmd;
528 : :
529 [ + + ]: 855 : if (iter->j >= iter->repeat)
530 : : {
531 : 537 : iter->j = 0;
532 : :
533 [ + + ]: 537 : if (iter->i >= iter->feature->n_geometry)
534 : : return FALSE;
535 : :
536 : 477 : cmd = iter->feature->geometry[iter->i];
537 : 477 : iter->i ++;
538 : :
539 : 477 : iter->op = cmd & 0x7;
540 : 477 : iter->repeat = cmd >> 3;
541 : : }
542 : :
543 [ + + - ]: 795 : switch (iter->op)
544 : : {
545 : 645 : case SHUMATE_VECTOR_GEOMETRY_OP_MOVE_TO:
546 : : case SHUMATE_VECTOR_GEOMETRY_OP_LINE_TO:
547 [ - + ]: 645 : if (iter->i + 1 >= iter->feature->n_geometry)
548 : : return FALSE;
549 : :
550 : 645 : iter->dx = zigzag (iter->feature->geometry[iter->i]);
551 : 645 : iter->dy = zigzag (iter->feature->geometry[iter->i + 1]);
552 : 645 : iter->cursor_x += iter->dx;
553 : 645 : iter->cursor_y += iter->dy;
554 : 645 : iter->x = iter->cursor_x;
555 : 645 : iter->y = iter->cursor_y;
556 : :
557 [ + + ]: 645 : if (iter->op == SHUMATE_VECTOR_GEOMETRY_OP_MOVE_TO)
558 : : {
559 : 165 : iter->start_x = iter->x;
560 : 165 : iter->start_y = iter->y;
561 : : }
562 : :
563 : 645 : iter->i += 2;
564 : 645 : break;
565 : :
566 : 150 : case SHUMATE_VECTOR_GEOMETRY_OP_CLOSE_PATH:
567 : 150 : iter->dx = iter->start_x - iter->x;
568 : 150 : iter->dy = iter->start_y - iter->y;
569 : 150 : iter->x = iter->start_x;
570 : 150 : iter->y = iter->start_y;
571 : 150 : break;
572 : : }
573 : :
574 : 795 : iter->j ++;
575 : 795 : return TRUE;
576 : : }
|
