File indexing completed on 2024-05-12 15:27:08
0001 /*************************************************************************** 0002 File : nsl_geom_linesim.h 0003 Project : LabPlot 0004 Description : NSL geometry line simplification functions 0005 -------------------------------------------------------------------- 0006 Copyright : (C) 2016 by Stefan Gerlach (stefan.gerlach@uni.kn) 0007 0008 ***************************************************************************/ 0009 0010 /*************************************************************************** 0011 * * 0012 * This program is free software; you can redistribute it and/or modify * 0013 * it under the terms of the GNU General Public License as published by * 0014 * the Free Software Foundation; either version 2 of the License, or * 0015 * (at your option) any later version. * 0016 * * 0017 * This program is distributed in the hope that it will be useful, * 0018 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0020 * GNU General Public License for more details. * 0021 * * 0022 * You should have received a copy of the GNU General Public License * 0023 * along with this program; if not, write to the Free Software * 0024 * Foundation, Inc., 51 Franklin Street, Fifth Floor, * 0025 * Boston, MA 02110-1301 USA * 0026 * * 0027 ***************************************************************************/ 0028 0029 /* 0030 TODO: 0031 * accelerate Visvalingam-Whyatt 0032 * calculate error statistics 0033 * more algorithms: Jenks, Zhao-Saalfeld 0034 * non-parametric version of Visvalingam-Whyatt, Opheim and Lang 0035 */ 0036 0037 #ifndef NSL_GEOM_LINESIM_H 0038 #define NSL_GEOM_LINESIM_H 0039 0040 #include <stdlib.h> 0041 0042 #define NSL_GEOM_LINESIM_TYPE_COUNT 10 0043 typedef enum {nsl_geom_linesim_type_douglas_peucker_variant, nsl_geom_linesim_type_douglas_peucker, nsl_geom_linesim_type_visvalingam_whyatt, 0044 nsl_geom_linesim_type_reumann_witkam, nsl_geom_linesim_type_perpdist, nsl_geom_linesim_type_nthpoint, nsl_geom_linesim_type_raddist, 0045 nsl_geom_linesim_type_interp, nsl_geom_linesim_type_opheim, nsl_geom_linesim_type_lang} nsl_geom_linesim_type; 0046 extern const char* nsl_geom_linesim_type_name[]; 0047 0048 /*********** error calculation functions *********/ 0049 0050 /* calculates positional error (sum of perpendicular distance per point) 0051 of simplified set (given by index[]) 0052 */ 0053 double nsl_geom_linesim_positional_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0054 /* calculates positional error (sum of squared perpendicular distance per point) 0055 of simplified set (given by index[]) 0056 */ 0057 double nsl_geom_linesim_positional_squared_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0058 0059 /* calculates area error (area between original and simplified data per point) 0060 of simplified set (given by index[]) 0061 */ 0062 double nsl_geom_linesim_area_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0063 0064 /* calculates tolerance by using diagonal distance of all data point clip area 0065 divided by n */ 0066 double nsl_geom_linesim_clip_diag_perpoint(const double xdata[], const double ydata[], const size_t n); 0067 0068 /* calculates tolerance from clip area 0069 divided by n */ 0070 double nsl_geom_linesim_clip_area_perpoint(const double xdata[], const double ydata[], const size_t n); 0071 0072 /* calculates tolerance from average distance of following point 0073 divided by n */ 0074 double nsl_geom_linesim_avg_dist_perpoint(const double xdata[], const double ydata[], const size_t n); 0075 0076 /*********** simplification algorithms *********/ 0077 0078 /* Douglas-Peucker line simplification 0079 xdata, ydata: data points 0080 n: number of points 0081 tol: minimum tolerance (perpendicular distance) 0082 index: index of reduced points 0083 -> returns final number of points 0084 */ 0085 size_t nsl_geom_linesim_douglas_peucker(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0086 size_t nsl_geom_linesim_douglas_peucker_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0087 /* Douglas-Peucker variant resulting in a given number of points 0088 xdata, ydata: data points 0089 n: number of points 0090 nout: number of output points 0091 index: index of reduced points 0092 -> returns perpendicular distance of last added point (upper limit for all remaining points) 0093 */ 0094 double nsl_geom_linesim_douglas_peucker_variant(const double xdata[], const double ydata[], const size_t n, const size_t nout, size_t index[]); 0095 0096 /* simple n-th point line simplification 0097 n: number of points 0098 step: step size 0099 index: index of reduced points 0100 -> returns final number of points 0101 */ 0102 size_t nsl_geom_linesim_nthpoint(const size_t n, const int step, size_t index[]); 0103 0104 /* radial distance line simplification 0105 xdata, ydata: data points 0106 n: number of points 0107 tol: tolerance (radius) 0108 index: index of reduced points 0109 -> returns final number of points 0110 */ 0111 size_t nsl_geom_linesim_raddist(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0112 size_t nsl_geom_linesim_raddist_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0113 0114 /* perpendicular distance line simplification 0115 xdata, ydata: data points 0116 n: number of points 0117 tol: tolerance (perp. distance) 0118 index: index of reduced points 0119 -> returns final number of points 0120 */ 0121 size_t nsl_geom_linesim_perpdist(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0122 size_t nsl_geom_linesim_perpdist_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0123 /* repeat perpendicular distance line simplification 0124 repeat: number of repeats 0125 */ 0126 size_t nsl_geom_linesim_perpdist_repeat(const double xdata[], const double ydata[], const size_t n, const double tol, const size_t repeat, size_t index[]); 0127 0128 /* line simplification by nearest neigbor interpolation (idea from xmgrace) 0129 xdata, ydata: data points 0130 n: number of points 0131 tol: tolerance (perp. distance) 0132 index: index of reduced points 0133 -> returns final number of points 0134 */ 0135 size_t nsl_geom_linesim_interp(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0136 size_t nsl_geom_linesim_interp_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0137 0138 /* Visvalingam-Whyatt line simplification 0139 xdata, ydata: data points 0140 n: number of points 0141 tol: tolerance (area) 0142 index: index of reduced points 0143 -> returns final number of points 0144 */ 0145 size_t nsl_geom_linesim_visvalingam_whyatt(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0146 size_t nsl_geom_linesim_visvalingam_whyatt_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0147 0148 /* Reumann-Witkam line simplification 0149 xdata, ydata: data points 0150 n: number of points 0151 tol: tolerance (perp. distance) 0152 index: index of reduced points 0153 -> returns final number of points 0154 */ 0155 size_t nsl_geom_linesim_reumann_witkam(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0156 size_t nsl_geom_linesim_reumann_witkam_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0157 0158 /* Opheim line simplification 0159 xdata, ydata: data points 0160 n: number of points 0161 mintol: minimum tolerance (to define ray) 0162 maxtol: maximum tolerance (to define next key) 0163 index: index of reduced points 0164 -> returns final number of points 0165 */ 0166 size_t nsl_geom_linesim_opheim(const double xdata[], const double ydata[], const size_t n, const double mintol, const double maxtol, size_t index[]); 0167 size_t nsl_geom_linesim_opheim_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0168 0169 /* Lang line simplification 0170 xdata, ydata: data points 0171 n: number of points 0172 tol: minimum tolerance (perpendicular distance) 0173 region: search region (number of points) 0174 index: index of reduced points 0175 -> returns final number of points 0176 */ 0177 size_t nsl_geom_linesim_lang(const double xdata[], const double ydata[], const size_t n, const double tol, const size_t region, size_t index[]); 0178 size_t nsl_geom_linesim_lang_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0179 0180 #endif /* NSL_GEOM_LINESIM_H */