GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 31.5% 74 / 0 / 235
Functions: 30.8% 8 / 0 / 26
Branches: 25.2% 28 / 0 / 111

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