39 #include "douglas_peucker.h"
40 #include "utilities.h"
42 static GArray *splt_copy_as_new_array(GArray *array);
43 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
44 GArray *second, gint second_end_bound);
45 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points,
46 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point);
47 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index);
48 static GArray *build_input_douglas_points(GArray *gdk_points);
49 static GArray *build_presence_array(GArray *output_douglas_points, guint length);
50 static GArray *splt_douglas_peucker_for_one_threshold(GArray *input_douglas_points,
51 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point);
55 GPtrArray *splt_douglas_peucker(GArray *gdk_points,
void (*callback)(
ui_state *ui),
ui_state *ui,
56 gdouble threshold_to_discard_points, ...)
58 GArray *input_douglas_points = build_input_douglas_points(gdk_points);
59 guint length = input_douglas_points->len;
61 GPtrArray *presence_points_by_threshold = g_ptr_array_new();
64 va_start(ap, threshold_to_discard_points);
65 while (threshold_to_discard_points > 0)
67 GArray *output_douglas_points =
68 splt_douglas_peucker_for_one_threshold(input_douglas_points, callback, ui,
69 threshold_to_discard_points);
71 GArray *presence_array = build_presence_array(output_douglas_points, length);
72 g_array_free(output_douglas_points, TRUE);
74 g_ptr_array_add(presence_points_by_threshold, (gpointer) presence_array);
76 threshold_to_discard_points = va_arg(ap, gdouble);
80 g_array_free(input_douglas_points, TRUE);
82 return presence_points_by_threshold;
85 void splt_douglas_peucker_free(GPtrArray *douglas_peucker_ptr_array)
87 if (douglas_peucker_ptr_array == NULL)
93 for (i = 0;i < douglas_peucker_ptr_array->len; i++)
95 g_array_free(g_ptr_array_index(douglas_peucker_ptr_array, i), TRUE);
98 g_ptr_array_free(douglas_peucker_ptr_array, TRUE);
101 static GArray *splt_douglas_peucker_for_one_threshold(GArray *input_douglas_points,
102 void (*callback)(
ui_state *ui),
ui_state *ui, gdouble threshold_to_discard_point)
104 GArray *output_douglas_points =
105 splt_recursive_douglas_peucker(splt_copy_as_new_array(input_douglas_points), callback, ui,
106 threshold_to_discard_point);
108 return output_douglas_points;
111 static gint douglas_points_sort(gconstpointer first, gconstpointer second)
116 return first_douglas_point->index - second_douglas_point->index;
119 static GArray *build_presence_array(GArray *output_douglas_points, guint length)
121 g_array_sort(output_douglas_points, douglas_points_sort);
123 GArray *presence_array = g_array_new(TRUE, TRUE,
sizeof(gint));
125 gint current_point_index = -1;
126 gint output_douglas_points_index = 0;
128 if (output_douglas_points->len > 0)
131 g_array_index(output_douglas_points,
douglas_point, output_douglas_points_index);
132 current_point_index = current_point.index;
135 gint false_value = 0;
139 for (i = 0;i < length; i++)
141 if (current_point_index == i)
143 output_douglas_points_index++;
145 g_array_index(output_douglas_points,
douglas_point, output_douglas_points_index);
146 current_point_index = point.index;
147 g_array_append_val(presence_array, true_value);
151 g_array_append_val(presence_array, false_value);
154 return presence_array;
157 static GArray *build_input_douglas_points(GArray *gdk_points)
159 GArray *input_douglas_points = g_array_new(TRUE, TRUE,
sizeof(
douglas_point));
162 for (i = 0; i < gdk_points->len; i++)
164 GdkPoint point = g_array_index(gdk_points, GdkPoint, i);
167 douglas.point = point;
170 g_array_append_val(input_douglas_points, douglas);
173 return input_douglas_points;
176 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points,
void (*callback)(
ui_state *ui),
177 ui_state *ui, gdouble threshold_to_discard_point)
179 GArray *new_points = NULL;
181 if (douglas_points->len <= 2)
183 new_points = splt_copy_as_new_array(douglas_points);
184 g_array_free(douglas_points, TRUE);
188 if (callback != NULL)
197 splt_find_point_with_maximum_distance(douglas_points, first_point.point, last_point.point);
199 if (max_distance_point == NULL || double_equals(max_distance_point->distance, 0))
201 new_points = splt_copy_as_new_array(douglas_points);
202 g_array_free(douglas_points, TRUE);
204 if (max_distance_point != NULL) { g_free(max_distance_point); }
209 if (max_distance_point->distance >= threshold_to_discard_point)
211 GArray *first_half_points =
212 splt_split_as_new_array(douglas_points, 0, max_distance_point->index);
213 GArray *first_half_filtered_points =
214 splt_recursive_douglas_peucker(first_half_points, callback, ui, threshold_to_discard_point);
216 GArray *second_half_points =
217 splt_split_as_new_array(douglas_points, max_distance_point->index, douglas_points->len - 1);
218 GArray *second_half_filtered_points =
219 splt_recursive_douglas_peucker(second_half_points, callback, ui, threshold_to_discard_point);
222 splt_merge_arrays_with_bounds(first_half_filtered_points, first_half_filtered_points->len - 2,
223 second_half_filtered_points, second_half_filtered_points->len - 1);
225 g_array_free(first_half_filtered_points, TRUE);
226 g_array_free(second_half_filtered_points, TRUE);
231 g_array_append_val(new_points, first_point);
232 g_array_append_val(new_points, last_point);
235 g_free(max_distance_point);
236 g_array_free(douglas_points, TRUE);
242 GdkPoint first_point, GdkPoint last_point)
245 if (max_distance_point == NULL)
250 max_distance_point->index = 0;
251 max_distance_point->distance = 0;
254 for (i = 1; i < douglas_points->len - 1; i++)
258 gdouble perpendicular_distance =
259 splt_find_perpendicular_distance(point.point, first_point, last_point);
260 if (perpendicular_distance <= max_distance_point->distance)
265 max_distance_point->index = i;
266 max_distance_point->distance = perpendicular_distance;
269 return max_distance_point;
272 gdouble splt_find_distance(GdkPoint first, GdkPoint second)
274 return sqrt(pow(second.x - first.x, 2) + pow(second.y - first.y, 2));
277 gdouble splt_find_perpendicular_distance(GdkPoint point,
278 GdkPoint segment_begin_point, GdkPoint segment_end_point)
280 gdouble distance_A = splt_find_distance(segment_begin_point, point);
281 gdouble distance_B = splt_find_distance(point, segment_end_point);
282 gdouble distance_C = splt_find_distance(segment_begin_point, segment_end_point);
284 gdouble semiperimeter = (distance_A + distance_B + distance_C) / 2.0;
286 gdouble perpendicular_distance =
287 2.0 * sqrt(semiperimeter *
288 (semiperimeter - distance_A) *
289 (semiperimeter - distance_B) *
290 (semiperimeter - distance_C)) / distance_C;
292 return perpendicular_distance;
295 static void splt_append_array_with_bounds(GArray *source, GArray *target,
296 gint start_index, gint end_index)
299 for (i = start_index;i <= end_index;i++)
302 g_array_append_val(target, point);
306 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index)
308 GArray *new_array = g_array_new(TRUE, TRUE, g_array_get_element_size(array));
309 splt_append_array_with_bounds(array, new_array, start_index, end_index);
313 static void splt_append_array(GArray *source, GArray *target)
315 splt_append_array_with_bounds(source, target, 0, source->len - 1);
318 static GArray *splt_copy_as_new_array(GArray *array) {
319 GArray *new_array = g_array_new(TRUE, TRUE, g_array_get_element_size(array));
320 splt_append_array(array, new_array);
324 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
325 GArray *second, gint second_end_bound)
327 GArray *new_array = splt_split_as_new_array(first, 0, first_end_bound);
328 splt_append_array_with_bounds(second, new_array, 0, second_end_bound);