-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
RamerDouglasPeucker.java
92 lines (82 loc) · 3.4 KB
/
RamerDouglasPeucker.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package com.jwetherell.algorithms.mathematics;
import java.util.ArrayList;
import java.util.List;
/**
* The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a
* curve that is approximated by a series of points.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm">Ramer–Douglas–Peucker Algorithm (Wikipedia)</a>
* <br>
* @author Justin Wetherell <[email protected]>
*/
public class RamerDouglasPeucker {
private RamerDouglasPeucker() { }
private static final double sqr(double x) {
return Math.pow(x, 2);
}
private static final double distanceBetweenPoints(double vx, double vy, double wx, double wy) {
return sqr(vx - wx) + sqr(vy - wy);
}
private static final double distanceToSegmentSquared(double px, double py, double vx, double vy, double wx, double wy) {
final double l2 = distanceBetweenPoints(vx, vy, wx, wy);
if (l2 == 0)
return distanceBetweenPoints(px, py, vx, vy);
final double t = ((px - vx) * (wx - vx) + (py - vy) * (wy - vy)) / l2;
if (t < 0)
return distanceBetweenPoints(px, py, vx, vy);
if (t > 1)
return distanceBetweenPoints(px, py, wx, wy);
return distanceBetweenPoints(px, py, (vx + t * (wx - vx)), (vy + t * (wy - vy)));
}
private static final double perpendicularDistance(double px, double py, double vx, double vy, double wx, double wy) {
return Math.sqrt(distanceToSegmentSquared(px, py, vx, vy, wx, wy));
}
private static final void douglasPeucker(List<Double[]> list, int s, int e, double epsilon, List<Double[]> resultList) {
// Find the point with the maximum distance
double dmax = 0;
int index = 0;
final int start = s;
final int end = e-1;
for (int i=start+1; i<end; i++) {
// Point
final double px = list.get(i)[0];
final double py = list.get(i)[1];
// Start
final double vx = list.get(start)[0];
final double vy = list.get(start)[1];
// End
final double wx = list.get(end)[0];
final double wy = list.get(end)[1];
final double d = perpendicularDistance(px, py, vx, vy, wx, wy);
if (d > dmax) {
index = i;
dmax = d;
}
}
// If max distance is greater than epsilon, recursively simplify
if (dmax > epsilon) {
// Recursive call
douglasPeucker(list, s, index, epsilon, resultList);
douglasPeucker(list, index, e, epsilon, resultList);
} else {
if ((end-start)>0) {
resultList.add(list.get(start));
resultList.add(list.get(end));
} else {
resultList.add(list.get(start));
}
}
}
/**
* Given a curve composed of line segments find a similar curve with fewer points.
*
* @param list List of Double[] points (x,y)
* @param epsilon Distance dimension
* @return Similar curve with fewer points
*/
public static final List<Double[]> douglasPeucker(List<Double[]> list, double epsilon) {
final List<Double[]> resultList = new ArrayList<Double[]>();
douglasPeucker(list, 0, list.size(), epsilon, resultList);
return resultList;
}
}