39 #include "douglas_peucker.h"
41 static GArray *splt_copy_as_new_array(GArray *array);
42 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
43 GArray *second, gint second_end_bound);
44 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points,
45 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point);
46 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index);
47 static GArray *build_input_douglas_points(GArray *gdk_points);
48 static GArray *build_presence_array(GArray *output_douglas_points, guint length);
49 static GArray *splt_douglas_peucker_for_one_threshold(GArray *input_douglas_points,
50 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point);
54 GPtrArray *splt_douglas_peucker(GArray *gdk_points,
void (*callback)(
ui_state *ui),
ui_state *ui,
55 gdouble threshold_to_discard_points, ...)
57 GArray *input_douglas_points = build_input_douglas_points(gdk_points);
58 guint length = input_douglas_points->len;
60 GPtrArray *presence_points_by_threshold = g_ptr_array_new();
63 va_start(ap, threshold_to_discard_points);
64 while (threshold_to_discard_points > 0)
66 GArray *output_douglas_points =
67 splt_douglas_peucker_for_one_threshold(input_douglas_points, callback, ui,
68 threshold_to_discard_points);
70 GArray *presence_array = build_presence_array(output_douglas_points, length);
71 g_array_free(output_douglas_points, TRUE);
73 g_ptr_array_add(presence_points_by_threshold, (gpointer) presence_array);
75 threshold_to_discard_points = va_arg(ap, gdouble);
79 g_array_free(input_douglas_points, TRUE);
81 return presence_points_by_threshold;
84 void splt_douglas_peucker_free(GPtrArray *douglas_peucker_ptr_array)
86 if (douglas_peucker_ptr_array == NULL)
92 for (i = 0;i < douglas_peucker_ptr_array->len; i++)
94 g_array_free(g_ptr_array_index(douglas_peucker_ptr_array, i), TRUE);
97 g_ptr_array_free(douglas_peucker_ptr_array, TRUE);
100 static GArray *splt_douglas_peucker_for_one_threshold(GArray *input_douglas_points,
101 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point)
103 GArray *output_douglas_points =
104 splt_recursive_douglas_peucker(splt_copy_as_new_array(input_douglas_points), callback, ui,
105 threshold_to_discard_point);
107 return output_douglas_points;
110 static gint douglas_points_sort(gconstpointer first, gconstpointer second)
115 return first_douglas_point->index - second_douglas_point->index;
118 static GArray *build_presence_array(GArray *output_douglas_points, guint length)
120 g_array_sort(output_douglas_points, douglas_points_sort);
122 GArray *presence_array = g_array_new(TRUE, TRUE,
sizeof(gint));
124 gint current_point_index = -1;
125 gint output_douglas_points_index = 0;
127 if (output_douglas_points->len > 0)
130 g_array_index(output_douglas_points,
douglas_point, output_douglas_points_index);
131 current_point_index = current_point.index;
134 gint false_value = 0;
138 for (i = 0;i < length; i++)
140 if (current_point_index == i)
142 output_douglas_points_index++;
144 g_array_index(output_douglas_points,
douglas_point, output_douglas_points_index);
145 current_point_index = point.index;
146 g_array_append_val(presence_array, true_value);
150 g_array_append_val(presence_array, false_value);
153 return presence_array;
156 static GArray *build_input_douglas_points(GArray *gdk_points)
158 GArray *input_douglas_points = g_array_new(TRUE, TRUE,
sizeof(
douglas_point));
161 for (i = 0; i < gdk_points->len; i++)
163 GdkPoint point = g_array_index(gdk_points, GdkPoint, i);
166 douglas.point = point;
169 g_array_append_val(input_douglas_points, douglas);
172 return input_douglas_points;
175 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points,
void (*callback)(
ui_state *ui),
176 ui_state *ui, gdouble threshold_to_discard_point)
178 GArray *new_points = NULL;
180 if (douglas_points->len <= 2)
182 new_points = splt_copy_as_new_array(douglas_points);
183 g_array_free(douglas_points, TRUE);
187 if (callback != NULL)
196 splt_find_point_with_maximum_distance(douglas_points, first_point.point, last_point.point);
198 if (max_distance_point == NULL || double_equals(max_distance_point->distance, 0))
200 new_points = splt_copy_as_new_array(douglas_points);
201 g_array_free(douglas_points, TRUE);
203 if (max_distance_point != NULL) { g_free(max_distance_point); }
208 if (max_distance_point->distance >= threshold_to_discard_point)
210 GArray *first_half_points =
211 splt_split_as_new_array(douglas_points, 0, max_distance_point->index);
212 GArray *first_half_filtered_points =
213 splt_recursive_douglas_peucker(first_half_points, callback, ui, threshold_to_discard_point);
215 GArray *second_half_points =
216 splt_split_as_new_array(douglas_points, max_distance_point->index, douglas_points->len - 1);
217 GArray *second_half_filtered_points =
218 splt_recursive_douglas_peucker(second_half_points, callback, ui, threshold_to_discard_point);
221 splt_merge_arrays_with_bounds(first_half_filtered_points, first_half_filtered_points->len - 2,
222 second_half_filtered_points, second_half_filtered_points->len - 1);
224 g_array_free(first_half_filtered_points, TRUE);
225 g_array_free(second_half_filtered_points, TRUE);
230 g_array_append_val(new_points, first_point);
231 g_array_append_val(new_points, last_point);
234 g_free(max_distance_point);
235 g_array_free(douglas_points, TRUE);
241 GdkPoint first_point, GdkPoint last_point)
244 if (max_distance_point == NULL)
249 max_distance_point->index = 0;
250 max_distance_point->distance = 0;
253 for (i = 1; i < douglas_points->len - 1; i++)
257 gdouble perpendicular_distance =
258 splt_find_perpendicular_distance(point.point, first_point, last_point);
259 if (perpendicular_distance <= max_distance_point->distance)
264 max_distance_point->index = i;
265 max_distance_point->distance = perpendicular_distance;
268 return max_distance_point;
271 gdouble splt_find_distance(GdkPoint first, GdkPoint second)
273 return sqrt(pow(second.x - first.x, 2) + pow(second.y - first.y, 2));
276 gdouble splt_find_perpendicular_distance(GdkPoint point,
277 GdkPoint segment_begin_point, GdkPoint segment_end_point)
279 gdouble distance_A = splt_find_distance(segment_begin_point, point);
280 gdouble distance_B = splt_find_distance(point, segment_end_point);
281 gdouble distance_C = splt_find_distance(segment_begin_point, segment_end_point);
283 gdouble semiperimeter = (distance_A + distance_B + distance_C) / 2.0;
285 gdouble perpendicular_distance =
286 2.0 * sqrt(semiperimeter *
287 (semiperimeter - distance_A) *
288 (semiperimeter - distance_B) *
289 (semiperimeter - distance_C)) / distance_C;
291 return perpendicular_distance;
294 static void splt_append_array_with_bounds(GArray *source, GArray *target,
295 gint start_index, gint end_index)
298 for (i = start_index;i <= end_index;i++)
301 g_array_append_val(target, point);
305 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index)
307 GArray *new_array = g_array_new(TRUE, TRUE, g_array_get_element_size(array));
308 splt_append_array_with_bounds(array, new_array, start_index, end_index);
312 static void splt_append_array(GArray *source, GArray *target)
314 splt_append_array_with_bounds(source, target, 0, source->len - 1);
317 static GArray *splt_copy_as_new_array(GArray *array) {
318 GArray *new_array = g_array_new(TRUE, TRUE, g_array_get_element_size(array));
319 splt_append_array(array, new_array);
323 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
324 GArray *second, gint second_end_bound)
326 GArray *new_array = splt_split_as_new_array(first, 0, first_end_bound);
327 splt_append_array_with_bounds(second, new_array, 0, second_end_bound);