File indexing completed on 2024-05-12 03:47:52
0001 /* 0002 File : nsl_geom_linesim.h 0003 Project : LabPlot 0004 Description : NSL geometry line simplification functions 0005 -------------------------------------------------------------------- 0006 SPDX-FileCopyrightText: 2016 Stefan Gerlach <stefan.gerlach@uni.kn> 0007 SPDX-License-Identifier: GPL-2.0-or-later 0008 */ 0009 0010 /* 0011 TODO: 0012 * accelerate Visvalingam-Whyatt 0013 * calculate error statistics 0014 * more algorithms: Jenks, Zhao-Saalfeld 0015 * non-parametric version of Visvalingam-Whyatt, Opheim and Lang 0016 */ 0017 0018 #ifndef NSL_GEOM_LINESIM_H 0019 #define NSL_GEOM_LINESIM_H 0020 0021 #include <stdlib.h> 0022 0023 #define NSL_GEOM_LINESIM_TYPE_COUNT 10 0024 typedef enum { 0025 nsl_geom_linesim_type_douglas_peucker_variant, 0026 nsl_geom_linesim_type_douglas_peucker, 0027 nsl_geom_linesim_type_visvalingam_whyatt, 0028 nsl_geom_linesim_type_reumann_witkam, 0029 nsl_geom_linesim_type_perpdist, 0030 nsl_geom_linesim_type_nthpoint, 0031 nsl_geom_linesim_type_raddist, 0032 nsl_geom_linesim_type_interp, 0033 nsl_geom_linesim_type_opheim, 0034 nsl_geom_linesim_type_lang 0035 } nsl_geom_linesim_type; 0036 extern const char* nsl_geom_linesim_type_name[]; 0037 0038 /*********** error calculation functions *********/ 0039 0040 /* calculates positional error (sum of perpendicular distance per point) 0041 of simplified set (given by index[]) 0042 */ 0043 double nsl_geom_linesim_positional_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0044 /* calculates positional error (sum of squared perpendicular distance per point) 0045 of simplified set (given by index[]) 0046 */ 0047 double nsl_geom_linesim_positional_squared_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0048 0049 /* calculates area error (area between original and simplified data per point) 0050 of simplified set (given by index[]) 0051 */ 0052 double nsl_geom_linesim_area_error(const double xdata[], const double ydata[], const size_t n, const size_t index[]); 0053 0054 /* calculates tolerance by using diagonal distance of all data point clip area 0055 divided by n */ 0056 double nsl_geom_linesim_clip_diag_perpoint(const double xdata[], const double ydata[], const size_t n); 0057 0058 /* calculates tolerance from clip area 0059 divided by n */ 0060 double nsl_geom_linesim_clip_area_perpoint(const double xdata[], const double ydata[], const size_t n); 0061 0062 /* calculates tolerance from average distance of following point 0063 divided by n */ 0064 double nsl_geom_linesim_avg_dist_perpoint(const double xdata[], const double ydata[], const size_t n); 0065 0066 /*********** simplification algorithms *********/ 0067 0068 /* Douglas-Peucker line simplification 0069 xdata, ydata: data points 0070 n: number of points 0071 tol: minimum tolerance (perpendicular distance) 0072 index: index of reduced points 0073 -> returns final number of points 0074 */ 0075 size_t nsl_geom_linesim_douglas_peucker(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0076 size_t nsl_geom_linesim_douglas_peucker_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0077 /* Douglas-Peucker variant resulting in a given number of points 0078 xdata, ydata: data points 0079 n: number of points 0080 nout: number of output points 0081 index: index of reduced points 0082 -> returns perpendicular distance of last added point (upper limit for all remaining points) 0083 */ 0084 double nsl_geom_linesim_douglas_peucker_variant(const double xdata[], const double ydata[], const size_t n, const size_t nout, size_t index[]); 0085 0086 /* simple n-th point line simplification 0087 n: number of points 0088 step: step size 0089 index: index of reduced points 0090 -> returns final number of points 0091 */ 0092 size_t nsl_geom_linesim_nthpoint(const size_t n, const int step, size_t index[]); 0093 0094 /* radial distance line simplification 0095 xdata, ydata: data points 0096 n: number of points 0097 tol: tolerance (radius) 0098 index: index of reduced points 0099 -> returns final number of points 0100 */ 0101 size_t nsl_geom_linesim_raddist(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0102 size_t nsl_geom_linesim_raddist_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0103 0104 /* perpendicular distance line simplification 0105 xdata, ydata: data points 0106 n: number of points 0107 tol: tolerance (perp. distance) 0108 index: index of reduced points 0109 -> returns final number of points 0110 */ 0111 size_t nsl_geom_linesim_perpdist(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0112 size_t nsl_geom_linesim_perpdist_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0113 /* repeat perpendicular distance line simplification 0114 repeat: number of repeats 0115 */ 0116 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[]); 0117 0118 /* line simplification by nearest neigbor interpolation (idea from xmgrace) 0119 xdata, ydata: data points 0120 n: number of points 0121 tol: tolerance (perp. distance) 0122 index: index of reduced points 0123 -> returns final number of points 0124 */ 0125 size_t nsl_geom_linesim_interp(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0126 size_t nsl_geom_linesim_interp_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0127 0128 /* Visvalingam-Whyatt line simplification 0129 xdata, ydata: data points 0130 n: number of points 0131 tol: tolerance (area) 0132 index: index of reduced points 0133 -> returns final number of points 0134 */ 0135 size_t nsl_geom_linesim_visvalingam_whyatt(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0136 size_t nsl_geom_linesim_visvalingam_whyatt_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0137 0138 /* Reumann-Witkam line simplification 0139 xdata, ydata: data points 0140 n: number of points 0141 tol: tolerance (perp. distance) 0142 index: index of reduced points 0143 -> returns final number of points 0144 */ 0145 size_t nsl_geom_linesim_reumann_witkam(const double xdata[], const double ydata[], const size_t n, const double tol, size_t index[]); 0146 size_t nsl_geom_linesim_reumann_witkam_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0147 0148 /* Opheim line simplification 0149 xdata, ydata: data points 0150 n: number of points 0151 mintol: minimum tolerance (to define ray) 0152 maxtol: maximum tolerance (to define next key) 0153 index: index of reduced points 0154 -> returns final number of points 0155 */ 0156 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[]); 0157 size_t nsl_geom_linesim_opheim_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0158 0159 /* Lang line simplification 0160 xdata, ydata: data points 0161 n: number of points 0162 tol: minimum tolerance (perpendicular distance) 0163 region: search region (number of points) 0164 index: index of reduced points 0165 -> returns final number of points 0166 */ 0167 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[]); 0168 size_t nsl_geom_linesim_lang_auto(const double xdata[], const double ydata[], const size_t n, size_t index[]); 0169 0170 #endif /* NSL_GEOM_LINESIM_H */