[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: [labplot] src/backend/nsl: added line simplification by interpolation
From: Stefan Gerlach <stefan.gerlach () uni-konstanz ! de>
Date: 2016-09-01 21:24:52
Message-ID: E1bfZTg-0001Al-OS () code ! kde ! org
[Download RAW message or body]
Git commit 4694fd1eeb4792675c1914178bd8d41f842e55fe by Stefan Gerlach.
Committed on 01/09/2016 at 21:24.
Pushed by sgerlach into branch 'master'.
added line simplification by interpolation
M +4 -0 src/backend/nsl/nsl_geom.c
M +6 -1 src/backend/nsl/nsl_geom.h
M +25 -12 src/backend/nsl/nsl_geom_linesim.c
M +30 -12 src/backend/nsl/nsl_geom_linesim.h
M +20 -12 src/backend/nsl/nsl_geom_linesim_test.c
http://commits.kde.org/labplot/4694fd1eeb4792675c1914178bd8d41f842e55fe
diff --git a/src/backend/nsl/nsl_geom.c b/src/backend/nsl/nsl_geom.c
index 6a30b94..0af4b66 100644
--- a/src/backend/nsl/nsl_geom.c
+++ b/src/backend/nsl/nsl_geom.c
@@ -36,3 +36,7 @@ double nsl_geom_point_point_dist(double x1, double y1, double x2, \
double y2) { double nsl_geom_point_line_dist(double x1, double y1, double x2, double \
y2, double xp, double yp) { return fabs( (xp-x1)*(y2-y1) - (x2-x1)*(yp-y1) ) / \
nsl_geom_point_point_dist(x1, y1, x2, y2); }
+
+double nsl_geom_point_line_dist_y(double x1, double y1, double x2, double y2, double \
xp, double yp) { + return fabs( yp - y1 - (y2-y1)*(xp-x1)/(x2-x1) );
+}
diff --git a/src/backend/nsl/nsl_geom.h b/src/backend/nsl/nsl_geom.h
index b5839e8..a2b9337 100644
--- a/src/backend/nsl/nsl_geom.h
+++ b/src/backend/nsl/nsl_geom.h
@@ -34,9 +34,14 @@
*/
double nsl_geom_point_point_dist(double x1, double y1, double x2, double y2);
-/* point-line distance
+/* point-line distance sqrt(dx^2+dy^2)
point (xp,yp) to line (x1,y1)-(x2,y2)
*/
double nsl_geom_point_line_dist(double x1, double y1, double x2, double y2, double \
xp, double yp);
+/* point-line distance |dy|
+ point (xp,yp) to line (x1,y1)-(x2,y2)
+ */
+double nsl_geom_point_line_dist_y(double x1, double y1, double x2, double y2, double \
xp, double yp); +
#endif /* NSL_GEOM_H */
diff --git a/src/backend/nsl/nsl_geom_linesim.c b/src/backend/nsl/nsl_geom_linesim.c
index 6e4bcef..da57e65 100644
--- a/src/backend/nsl/nsl_geom_linesim.c
+++ b/src/backend/nsl/nsl_geom_linesim.c
@@ -26,15 +26,6 @@
* *
***************************************************************************/
-/*
- TODO:
- * non-parametric functions (calculate eps from data)
- * more algorithms: Interpolation, Visvalingam-Whyatt, Jenks, Zhao-Saalfeld
- * sort algorithms by importance
- * error calculation by area
- * calculate error statistics
-*/
-
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
@@ -42,9 +33,8 @@
#include "nsl_geom.h"
#include "nsl_geom_linesim.h"
-
-const char* nsl_geom_linesim_type_name[] = {"Douglas-Peucker", "n-th point", "radial \
distance", "perpendicular distance" ,
- "Reumann-Witkam", "Opheim", "Lang"};
+const char* nsl_geom_linesim_type_name[] = {"Douglas-Peucker", "n-th point", "radial \
distance", "perpendicular distance", + "Interpolation", "Reumann-Witkam", "Opheim", \
"Lang"};
double nsl_geom_linesim_positional_squared_error(const double xdata[], const double \
ydata[], const size_t n, const size_t index[]) { double dist=0;
@@ -168,6 +158,29 @@ size_t nsl_geom_linesim_perpdist_repeat(const double xdata[], \
const double ydata return nout;
}
+size_t nsl_geom_linesim_interp(const double xdata[], const double ydata[], const \
size_t n, const double eps, size_t index[]) { + size_t nout=0, i;
+
+ /*first point*/
+ index[nout++] = 0;
+
+ size_t key=0;
+ for(i=1; i < n-1; i++) {
+ /*printf("%d: %d-%d\n", i, key, i+1);*/
+ double dist = nsl_geom_point_line_dist_y(xdata[key], ydata[key], xdata[i+1], \
ydata[i+1], xdata[i], ydata[i]); + /*printf("%d: dist = %g\n", i, dist);*/
+ if(dist > eps) {
+ /*printf("take it %d\n", i);*/
+ index[nout++] = key = i;
+ }
+ }
+
+ /* last point */
+ index[nout++] = n-1;
+
+ return nout;
+}
+
size_t nsl_geom_linesim_reumann_witkam(const double xdata[], const double ydata[], \
const size_t n, const double eps, size_t index[]) { size_t nout=0, key=0, key2=1, i;
diff --git a/src/backend/nsl/nsl_geom_linesim.h b/src/backend/nsl/nsl_geom_linesim.h
index cd9092c..716d991 100644
--- a/src/backend/nsl/nsl_geom_linesim.h
+++ b/src/backend/nsl/nsl_geom_linesim.h
@@ -26,14 +26,23 @@
* *
***************************************************************************/
+/*
+ TODO:
+ * non-parametric functions (calculate eps from data)
+ * more algorithms: Visvalingam-Whyatt, Jenks, Zhao-Saalfeld
+ * sort algorithms by importance
+ * error calculation by area
+ * calculate error statistics
+*/
+
#ifndef NSL_GEOM_LINESIM_H
#define NSL_GEOM_LINESIM_H
#include <stdlib.h>
-#define NSL_GEOM_LINESIM_TYPE_COUNT 7
+#define NSL_GEOM_LINESIM_TYPE_COUNT 8
typedef enum {nsl_geom_linesim_type_douglas_peucker, nsl_geom_linesim_type_nthpoint, \
nsl_geom_linesim_type_raddist, nsl_geom_linesim_type_perpdist,
- nsl_geom_linesim_type_reumann_witkam, nsl_geom_linesim_type_opheim, \
nsl_geom_linesim_type_lang} nsl_geom_linesim_type; + nsl_geom_linesim_type_interp, \
nsl_geom_linesim_type_reumann_witkam, nsl_geom_linesim_type_opheim, \
nsl_geom_linesim_type_lang} nsl_geom_linesim_type; extern const char* \
nsl_geom_linesim_type_name[];
/* calculates positional error (sum of squared perpendicular distance)
@@ -41,6 +50,16 @@ extern const char* nsl_geom_linesim_type_name[];
*/
double nsl_geom_linesim_positional_squared_error(const double xdata[], const double \
ydata[], const size_t n, const size_t index[]);
+/* Douglas-Peucker line simplification
+ xdata, ydata: data points
+ n: number of points
+ eps: minimum tolerance (perpendicular distance)
+ region: search region (number of points)
+ index: index of reduced points
+ -> returns final number of points
+*/
+size_t nsl_geom_linesim_douglas_peucker(const double xdata[], const double ydata[], \
const size_t n, const double eps, size_t index[]); +
/* simple n-th point line simplification
n: number of points
step: step size
@@ -71,6 +90,15 @@ size_t nsl_geom_linesim_perpdist(const double xdata[], const \
double ydata[], con
*/
size_t nsl_geom_linesim_perpdist_repeat(const double xdata[], const double ydata[], \
const size_t n, const double eps, const size_t repeat, size_t index[]);
+/* line simplification by nearest neigbor interpolation (idea from xmgrace)
+ xdata, ydata: data points
+ n: number of points
+ eps: tolerance (perp. distance)
+ index: index of reduced points
+ -> returns final number of points
+*/
+size_t nsl_geom_linesim_interp(const double xdata[], const double ydata[], const \
size_t n, const double eps, size_t index[]); +
/* Reumann-Witkam line simplification
xdata, ydata: data points
n: number of points
@@ -100,14 +128,4 @@ size_t nsl_geom_linesim_opheim(const double xdata[], const \
double ydata[], const
*/
size_t nsl_geom_linesim_lang(const double xdata[], const double ydata[], const \
size_t n, const double eps, const size_t region, size_t index[]);
-/* Douglas-Peucker line simplification
- xdata, ydata: data points
- n: number of points
- eps: minimum tolerance (perpendicular distance)
- region: search region (number of points)
- index: index of reduced points
- -> returns final number of points
-*/
-size_t nsl_geom_linesim_douglas_peucker(const double xdata[], const double ydata[], \
const size_t n, const double eps, size_t index[]);
-
#endif /* NSL_GEOM_LINESIM_H */
diff --git a/src/backend/nsl/nsl_geom_linesim_test.c \
b/src/backend/nsl/nsl_geom_linesim_test.c index 3701430..698ca74 100644
--- a/src/backend/nsl/nsl_geom_linesim_test.c
+++ b/src/backend/nsl/nsl_geom_linesim_test.c
@@ -32,14 +32,22 @@
double main() {
const double xdata[]={1,2,2.5,3,4,7,9,11,13,14};
const double ydata[]={1,1,1,3,4,7,8,12,13,13};
- const size_t n=10, np=2;
- size_t index[n];
+ const size_t n=10;
+ size_t index[n], i;
+ const double eps5=0.6;
+ printf("* simplification (Douglas Peucker)\n");
+ size_t nout = nsl_geom_linesim_douglas_peucker(xdata, ydata, n, eps5, index);
+ printf("nout = %d (error = %g)\n", nout, \
nsl_geom_linesim_positional_squared_error(xdata, ydata, n, index)); +
+ for(i=0; i<nout; i++)
+ printf("%d: %d\n", i, index[i]);
+
+ const size_t np=2;
printf("* n-th point\n");
- size_t nout = nsl_geom_linesim_nthpoint(n, np, index);
+ nout = nsl_geom_linesim_nthpoint(n, np, index);
printf("nout = %d (error = %g)\n", nout, \
nsl_geom_linesim_positional_squared_error(xdata, ydata, n, index));
- size_t i;
for(i=0; i<nout; i++)
printf("%d: %d\n", i, index[i]);
@@ -60,6 +68,14 @@ double main() {
for(i=0; i<nout; i++)
printf("%d: %d\n", i, index[i]);
+ const double eps6=0.7;
+ printf("* y distance (interpolation)\n", repeat);
+ nout = nsl_geom_linesim_interp(xdata, ydata, n, eps6, index);
+ printf("nout = %d (error = %g)\n", nout, \
nsl_geom_linesim_positional_squared_error(xdata, ydata, n, index)); +
+ for(i=0; i<nout; i++)
+ printf("%d: %d\n", i, index[i]);
+
const double eps3=0.7;
printf("* perp. distance (Reumann-Witkam)\n");
nout = nsl_geom_linesim_reumann_witkam(xdata, ydata, n, eps3, index);
@@ -86,12 +102,4 @@ double main() {
for(i=0; i<nout; i++)
printf("%d: %d\n", i, index[i]);
- const double eps5=0.6;
- printf("* simplification (Douglas Peucker)\n");
- nout = nsl_geom_linesim_douglas_peucker(xdata, ydata, n, eps5, index);
- printf("nout = %d (error = %g)\n", nout, \
nsl_geom_linesim_positional_squared_error(xdata, ydata, n, index));
-
- for(i=0; i<nout; i++)
- printf("%d: %d\n", i, index[i]);
-
}
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic