mp3splt-gtk
douglas_peucker.c
Go to the documentation of this file.
1 /**********************************************************
2  *
3  * for mp3/ogg splitting without decoding
4  * mp3splt-gtk -- utility based on mp3splt,
5  *
6  * Copyright: (C) 2005-2012 Alexandru Munteanu
7  * Contact: m@ioalex.net
8  *
9  * http://mp3splt.sourceforge.net/
10  *
11  *********************************************************/
12 
13 /**********************************************************
14  *
15  * This program is free software; you can redistribute it and/or
16  * modify it under the terms of the GNU General Public License
17  * as published by the Free Software Foundation; either version 2
18  * of the License, or (at your option) any later version.
19  *
20  * This program is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, write to the Free Software
27  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
28  * USA.
29  *
30  *********************************************************/
31 
32 /*!********************************************************
33  * \file
34  * The Douglas Peucker algorithm used to reduce the number of points of the amplitude
35  * wave curve
36  *
37  **********************************************************/
38 
39 #include "douglas_peucker.h"
40 #include "utilities.h"
41 
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);
52 
53 //returns an array of arrays of ints
54 //for each threshold, an [arrays of int] set to 1 if the point has been chosen, 0 otherwise
55 GPtrArray *splt_douglas_peucker(GArray *gdk_points, void (*callback)(ui_state *ui), ui_state *ui,
56  gdouble threshold_to_discard_points, ...)
57 {
58  GArray *input_douglas_points = build_input_douglas_points(gdk_points);
59  guint length = input_douglas_points->len;
60 
61  GPtrArray *presence_points_by_threshold = g_ptr_array_new();
62 
63  va_list ap;
64  va_start(ap, threshold_to_discard_points);
65  while (threshold_to_discard_points > 0)
66  {
67  GArray *output_douglas_points =
68  splt_douglas_peucker_for_one_threshold(input_douglas_points, callback, ui,
69  threshold_to_discard_points);
70 
71  GArray *presence_array = build_presence_array(output_douglas_points, length);
72  g_array_free(output_douglas_points, TRUE);
73 
74  g_ptr_array_add(presence_points_by_threshold, (gpointer) presence_array);
75 
76  threshold_to_discard_points = va_arg(ap, gdouble);
77  }
78  va_end(ap);
79 
80  g_array_free(input_douglas_points, TRUE);
81 
82  return presence_points_by_threshold;
83 }
84 
85 void splt_douglas_peucker_free(GPtrArray *douglas_peucker_ptr_array)
86 {
87  if (douglas_peucker_ptr_array == NULL)
88  {
89  return;
90  }
91 
92  gint i = 0;
93  for (i = 0;i < douglas_peucker_ptr_array->len; i++)
94  {
95  g_array_free(g_ptr_array_index(douglas_peucker_ptr_array, i), TRUE);
96  }
97 
98  g_ptr_array_free(douglas_peucker_ptr_array, TRUE);
99 }
100 
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)
103 {
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);
107 
108  return output_douglas_points;
109 }
110 
111 static gint douglas_points_sort(gconstpointer first, gconstpointer second)
112 {
113  const douglas_point *first_douglas_point = (douglas_point *)first;
114  const douglas_point *second_douglas_point = (douglas_point *)second;
115 
116  return first_douglas_point->index - second_douglas_point->index;
117 }
118 
119 static GArray *build_presence_array(GArray *output_douglas_points, guint length)
120 {
121  g_array_sort(output_douglas_points, douglas_points_sort);
122 
123  GArray *presence_array = g_array_new(TRUE, TRUE, sizeof(gint));
124 
125  gint current_point_index = -1;
126  gint output_douglas_points_index = 0;
127 
128  if (output_douglas_points->len > 0)
129  {
130  douglas_point current_point =
131  g_array_index(output_douglas_points, douglas_point, output_douglas_points_index);
132  current_point_index = current_point.index;
133  }
134 
135  gint false_value = 0;
136  gint true_value = 1;
137 
138  gint i = 0;
139  for (i = 0;i < length; i++)
140  {
141  if (current_point_index == i)
142  {
143  output_douglas_points_index++;
144  douglas_point point =
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);
148  continue;
149  }
150 
151  g_array_append_val(presence_array, false_value);
152  }
153 
154  return presence_array;
155 }
156 
157 static GArray *build_input_douglas_points(GArray *gdk_points)
158 {
159  GArray *input_douglas_points = g_array_new(TRUE, TRUE, sizeof(douglas_point));
160 
161  gint i = 0;
162  for (i = 0; i < gdk_points->len; i++)
163  {
164  GdkPoint point = g_array_index(gdk_points, GdkPoint, i);
165 
166  douglas_point douglas;
167  douglas.point = point;
168  douglas.index = i;
169 
170  g_array_append_val(input_douglas_points, douglas);
171  }
172 
173  return input_douglas_points;
174 }
175 
176 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points, void (*callback)(ui_state *ui),
177  ui_state *ui, gdouble threshold_to_discard_point)
178 {
179  GArray *new_points = NULL;
180 
181  if (douglas_points->len <= 2)
182  {
183  new_points = splt_copy_as_new_array(douglas_points);
184  g_array_free(douglas_points, TRUE);
185  return new_points;
186  }
187 
188  if (callback != NULL)
189  {
190  callback(ui);
191  }
192 
193  douglas_point first_point = g_array_index(douglas_points, douglas_point, 0);
194  douglas_point last_point = g_array_index(douglas_points, douglas_point, douglas_points->len - 1);
195 
196  distance_and_index *max_distance_point =
197  splt_find_point_with_maximum_distance(douglas_points, first_point.point, last_point.point);
198 
199  if (max_distance_point == NULL || double_equals(max_distance_point->distance, 0))
200  {
201  new_points = splt_copy_as_new_array(douglas_points);
202  g_array_free(douglas_points, TRUE);
203 
204  if (max_distance_point != NULL) { g_free(max_distance_point); }
205 
206  return new_points;
207  }
208 
209  if (max_distance_point->distance >= threshold_to_discard_point)
210  {
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);
215 
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);
220 
221  new_points =
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);
224 
225  g_array_free(first_half_filtered_points, TRUE);
226  g_array_free(second_half_filtered_points, TRUE);
227  }
228  else
229  {
230  new_points = g_array_new(TRUE, TRUE, sizeof(douglas_point));
231  g_array_append_val(new_points, first_point);
232  g_array_append_val(new_points, last_point);
233  }
234 
235  g_free(max_distance_point);
236  g_array_free(douglas_points, TRUE);
237 
238  return new_points;
239 }
240 
241 distance_and_index *splt_find_point_with_maximum_distance(GArray *douglas_points,
242  GdkPoint first_point, GdkPoint last_point)
243 {
244  distance_and_index *max_distance_point = malloc(sizeof(*max_distance_point));
245  if (max_distance_point == NULL)
246  {
247  return NULL;
248  }
249 
250  max_distance_point->index = 0;
251  max_distance_point->distance = 0;
252 
253  gint i = 0;
254  for (i = 1; i < douglas_points->len - 1; i++)
255  {
256  douglas_point point = g_array_index(douglas_points, douglas_point, i);
257 
258  gdouble perpendicular_distance =
259  splt_find_perpendicular_distance(point.point, first_point, last_point);
260  if (perpendicular_distance <= max_distance_point->distance)
261  {
262  continue;
263  }
264 
265  max_distance_point->index = i;
266  max_distance_point->distance = perpendicular_distance;
267  }
268 
269  return max_distance_point;
270 }
271 
272 gdouble splt_find_distance(GdkPoint first, GdkPoint second)
273 {
274  return sqrt(pow(second.x - first.x, 2) + pow(second.y - first.y, 2));
275 }
276 
277 gdouble splt_find_perpendicular_distance(GdkPoint point,
278  GdkPoint segment_begin_point, GdkPoint segment_end_point)
279 {
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);
283 
284  gdouble semiperimeter = (distance_A + distance_B + distance_C) / 2.0;
285 
286  gdouble perpendicular_distance =
287  2.0 * sqrt(semiperimeter *
288  (semiperimeter - distance_A) *
289  (semiperimeter - distance_B) *
290  (semiperimeter - distance_C)) / distance_C;
291 
292  return perpendicular_distance;
293 }
294 
295 static void splt_append_array_with_bounds(GArray *source, GArray *target,
296  gint start_index, gint end_index)
297 {
298  gint i = 0;
299  for (i = start_index;i <= end_index;i++)
300  {
301  douglas_point point = g_array_index(source, douglas_point, i);
302  g_array_append_val(target, point);
303  }
304 }
305 
306 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index)
307 {
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);
310  return new_array;
311 }
312 
313 static void splt_append_array(GArray *source, GArray *target)
314 {
315  splt_append_array_with_bounds(source, target, 0, source->len - 1);
316 }
317 
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);
321  return new_array;
322 }
323 
324 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
325  GArray *second, gint second_end_bound)
326 {
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);
329  return new_array;
330 }
331