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: io_fx@yahoo.fr
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., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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 
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);
51 
52 //returns an array of arrays of ints
53 //for each threshold, an [arrays of int] set to 1 if the point has been chosen, 0 otherwise
54 GPtrArray *splt_douglas_peucker(GArray *gdk_points, void (*callback)(ui_state *ui), ui_state *ui,
55  gdouble threshold_to_discard_points, ...)
56 {
57  GArray *input_douglas_points = build_input_douglas_points(gdk_points);
58  guint length = input_douglas_points->len;
59 
60  GPtrArray *presence_points_by_threshold = g_ptr_array_new();
61 
62  va_list ap;
63  va_start(ap, threshold_to_discard_points);
64  while (threshold_to_discard_points > 0)
65  {
66  GArray *output_douglas_points =
67  splt_douglas_peucker_for_one_threshold(input_douglas_points, callback, ui,
68  threshold_to_discard_points);
69 
70  GArray *presence_array = build_presence_array(output_douglas_points, length);
71  g_array_free(output_douglas_points, TRUE);
72 
73  g_ptr_array_add(presence_points_by_threshold, (gpointer) presence_array);
74 
75  threshold_to_discard_points = va_arg(ap, gdouble);
76  }
77  va_end(ap);
78 
79  g_array_free(input_douglas_points, TRUE);
80 
81  return presence_points_by_threshold;
82 }
83 
84 void splt_douglas_peucker_free(GPtrArray *douglas_peucker_ptr_array)
85 {
86  if (douglas_peucker_ptr_array == NULL)
87  {
88  return;
89  }
90 
91  gint i = 0;
92  for (i = 0;i < douglas_peucker_ptr_array->len; i++)
93  {
94  g_array_free(g_ptr_array_index(douglas_peucker_ptr_array, i), TRUE);
95  }
96 
97  g_ptr_array_free(douglas_peucker_ptr_array, TRUE);
98 }
99 
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)
102 {
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);
106 
107  return output_douglas_points;
108 }
109 
110 static gint douglas_points_sort(gconstpointer first, gconstpointer second)
111 {
112  const douglas_point *first_douglas_point = (douglas_point *)first;
113  const douglas_point *second_douglas_point = (douglas_point *)second;
114 
115  return first_douglas_point->index - second_douglas_point->index;
116 }
117 
118 static GArray *build_presence_array(GArray *output_douglas_points, guint length)
119 {
120  g_array_sort(output_douglas_points, douglas_points_sort);
121 
122  GArray *presence_array = g_array_new(TRUE, TRUE, sizeof(gint));
123 
124  gint current_point_index = -1;
125  gint output_douglas_points_index = 0;
126 
127  if (output_douglas_points->len > 0)
128  {
129  douglas_point current_point =
130  g_array_index(output_douglas_points, douglas_point, output_douglas_points_index);
131  current_point_index = current_point.index;
132  }
133 
134  gint false_value = 0;
135  gint true_value = 1;
136 
137  gint i = 0;
138  for (i = 0;i < length; i++)
139  {
140  if (current_point_index == i)
141  {
142  output_douglas_points_index++;
143  douglas_point point =
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);
147  continue;
148  }
149 
150  g_array_append_val(presence_array, false_value);
151  }
152 
153  return presence_array;
154 }
155 
156 static GArray *build_input_douglas_points(GArray *gdk_points)
157 {
158  GArray *input_douglas_points = g_array_new(TRUE, TRUE, sizeof(douglas_point));
159 
160  gint i = 0;
161  for (i = 0; i < gdk_points->len; i++)
162  {
163  GdkPoint point = g_array_index(gdk_points, GdkPoint, i);
164 
165  douglas_point douglas;
166  douglas.point = point;
167  douglas.index = i;
168 
169  g_array_append_val(input_douglas_points, douglas);
170  }
171 
172  return input_douglas_points;
173 }
174 
175 static GArray *splt_recursive_douglas_peucker(GArray *douglas_points, void (*callback)(ui_state *ui),
176  ui_state *ui, gdouble threshold_to_discard_point)
177 {
178  GArray *new_points = NULL;
179 
180  if (douglas_points->len <= 2)
181  {
182  new_points = splt_copy_as_new_array(douglas_points);
183  g_array_free(douglas_points, TRUE);
184  return new_points;
185  }
186 
187  if (callback != NULL)
188  {
189  callback(ui);
190  }
191 
192  douglas_point first_point = g_array_index(douglas_points, douglas_point, 0);
193  douglas_point last_point = g_array_index(douglas_points, douglas_point, douglas_points->len - 1);
194 
195  distance_and_index *max_distance_point =
196  splt_find_point_with_maximum_distance(douglas_points, first_point.point, last_point.point);
197 
198  if (max_distance_point == NULL || double_equals(max_distance_point->distance, 0))
199  {
200  new_points = splt_copy_as_new_array(douglas_points);
201  g_array_free(douglas_points, TRUE);
202 
203  if (max_distance_point != NULL) { g_free(max_distance_point); }
204 
205  return new_points;
206  }
207 
208  if (max_distance_point->distance >= threshold_to_discard_point)
209  {
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);
214 
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);
219 
220  new_points =
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);
223 
224  g_array_free(first_half_filtered_points, TRUE);
225  g_array_free(second_half_filtered_points, TRUE);
226  }
227  else
228  {
229  new_points = g_array_new(TRUE, TRUE, sizeof(douglas_point));
230  g_array_append_val(new_points, first_point);
231  g_array_append_val(new_points, last_point);
232  }
233 
234  g_free(max_distance_point);
235  g_array_free(douglas_points, TRUE);
236 
237  return new_points;
238 }
239 
240 distance_and_index *splt_find_point_with_maximum_distance(GArray *douglas_points,
241  GdkPoint first_point, GdkPoint last_point)
242 {
243  distance_and_index *max_distance_point = malloc(sizeof(*max_distance_point));
244  if (max_distance_point == NULL)
245  {
246  return NULL;
247  }
248 
249  max_distance_point->index = 0;
250  max_distance_point->distance = 0;
251 
252  gint i = 0;
253  for (i = 1; i < douglas_points->len - 1; i++)
254  {
255  douglas_point point = g_array_index(douglas_points, douglas_point, i);
256 
257  gdouble perpendicular_distance =
258  splt_find_perpendicular_distance(point.point, first_point, last_point);
259  if (perpendicular_distance <= max_distance_point->distance)
260  {
261  continue;
262  }
263 
264  max_distance_point->index = i;
265  max_distance_point->distance = perpendicular_distance;
266  }
267 
268  return max_distance_point;
269 }
270 
271 gdouble splt_find_distance(GdkPoint first, GdkPoint second)
272 {
273  return sqrt(pow(second.x - first.x, 2) + pow(second.y - first.y, 2));
274 }
275 
276 gdouble splt_find_perpendicular_distance(GdkPoint point,
277  GdkPoint segment_begin_point, GdkPoint segment_end_point)
278 {
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);
282 
283  gdouble semiperimeter = (distance_A + distance_B + distance_C) / 2.0;
284 
285  gdouble perpendicular_distance =
286  2.0 * sqrt(semiperimeter *
287  (semiperimeter - distance_A) *
288  (semiperimeter - distance_B) *
289  (semiperimeter - distance_C)) / distance_C;
290 
291  return perpendicular_distance;
292 }
293 
294 static void splt_append_array_with_bounds(GArray *source, GArray *target,
295  gint start_index, gint end_index)
296 {
297  gint i = 0;
298  for (i = start_index;i <= end_index;i++)
299  {
300  douglas_point point = g_array_index(source, douglas_point, i);
301  g_array_append_val(target, point);
302  }
303 }
304 
305 static GArray *splt_split_as_new_array(GArray *array, gint start_index, gint end_index)
306 {
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);
309  return new_array;
310 }
311 
312 static void splt_append_array(GArray *source, GArray *target)
313 {
314  splt_append_array_with_bounds(source, target, 0, source->len - 1);
315 }
316 
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);
320  return new_array;
321 }
322 
323 static GArray *splt_merge_arrays_with_bounds(GArray *first, gint first_end_bound,
324  GArray *second, gint second_end_bound)
325 {
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);
328  return new_array;
329 }
330