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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
package tim.prune.function.compress.methods;
import tim.prune.data.DataPoint;
import tim.prune.data.MarkingData;
import tim.prune.data.NumberUtils;
import tim.prune.data.Track;
import tim.prune.function.compress.CompressionMethodType;
import tim.prune.function.compress.TrackDetails;
import tim.prune.function.compress.XYpoint;
public class DouglasPeuckerMethod extends CompressionMethod
{
private final int _factor;
public DouglasPeuckerMethod(int factor) {
_factor = factor;
}
public DouglasPeuckerMethod(String inString) {
_factor = recogniseString(inString) ? NumberUtils.getIntOrZero(inString.substring(4)) : (int) NumberUtils.getDoubleOrZero(inString);
}
public CompressionMethodType getType() {
return CompressionMethodType.DOUGLAS_PEUCKER;
}
public String getParam() {
return "" + Math.abs(_factor);
}
public int compress(Track inTrack, TrackDetails inDetails, MarkingData inMarkings)
{
// Parse parameter
double param = _factor <= 0 ? 1.0 : (1.0 / _factor);
double threshold = inDetails.getTrackSpan() * param;
int numPoints = inTrack.getNumPoints();
int origNumDeleted = inMarkings.getNumDeleted();
// Convert inFlags into keepFlags
int[] keepFlags = new int[numPoints];
int segStart = -1, segEnd = -1;
// Loop over all points in track
for (int i=0; i<numPoints; i++)
{
DataPoint currPoint = inTrack.getPoint(i);
if (currPoint.getSegmentStart())
{
// new segment found, so process previous one
if (segStart > -1 && segEnd > segStart)
{
keepFlags[segEnd] = 1; // keep
compressSegment(inTrack, keepFlags, segStart, segEnd, threshold);
segStart = segEnd = -1;
}
}
if (inMarkings.isPointMarkedForDeletion(i)) {
keepFlags[i] = -1; // already deleted
}
else if (currPoint.isWaypoint() || currPoint.hasMedia() || currPoint.getSegmentStart()) {
keepFlags[i] = 1; // keep
}
// Don't consider points which are already marked as deleted, ignore waypoints
if (!inMarkings.isPointMarkedForDeletion(i) && !currPoint.isWaypoint())
{
// remember starts and ends
if (segStart < 0) {segStart = i;}
else {segEnd = i;}
}
}
// Last segment, if any
if (segStart >= 0 && segEnd > segStart) {
keepFlags[segEnd] = 1; // keep
compressSegment(inTrack, keepFlags, segStart, segEnd, threshold);
}
// Convert keepFlags back into inFlags
for (int i=1; i<numPoints; i++)
{
if (keepFlags[i] < 1) {
inMarkings.markPointForDeletion(i);
}
}
return inMarkings.getNumDeleted() - origNumDeleted;
}
/**
* Compress the given segment (recursively)
* @param inTrack the track to compress
* @param inFlags int array of deletion flags for entire track
* @param inSegStart index of start of segment
* @param inSegEnd index of end of segment
* @param inThreshold threshold to use
*/
private void compressSegment(Track inTrack, int[] inFlags, int inSegStart, int inSegEnd,
double inThreshold)
{
// System.out.println("Compress segment " + inSegStart + "-" + inSegEnd);
final int numPoints = inSegEnd - inSegStart + 1;
if (numPoints < 3) {
// segment too short to compress
return;
}
// Calculate parameters of straight line between first and last
XYpoint startxy = new XYpoint(inTrack.getX(inSegStart), inTrack.getY(inSegStart));
XYpoint endxy = new XYpoint(inTrack.getX(inSegEnd), inTrack.getY(inSegEnd));
XYpoint ab = startxy.vectorTo(endxy);
final double dist2AB = ab.len2();
// create unit vector perpendicular to AB
final double distAB = ab.len();
XYpoint perpendicular = new XYpoint(ab.y/distAB, -ab.x/distAB);
// Check whether distAB is 0.0 - if so, find furthest point from startxy and compress from start to here and here to end
if (distAB <= 0.0)
{
final int furthestIndex = getFurthestPointIndex(inTrack, inSegStart, inSegEnd);
if (furthestIndex > inSegStart)
{
compressSegment(inTrack, inFlags, inSegStart, furthestIndex, inThreshold);
compressSegment(inTrack, inFlags, furthestIndex, inSegEnd, inThreshold);
}
return;
}
double maxDist = -1.0;
int furthestIndex = -1;
for (int i=inSegStart+1; i<inSegEnd; i++)
{
if (inFlags[i] == 0) // unknown status
{
XYpoint currPoint = new XYpoint(inTrack.getX(i), inTrack.getY(i));
XYpoint ac = startxy.vectorTo(currPoint);
double distAP = ab.dot(ac) / dist2AB;
// calc distance from point to line depending on distAP
final double dist;
if (distAP < 0.0) {
dist = ac.len(); // outside line segment AB on the A side
}
else if (distAP > 1.0) {
dist = endxy.vectorTo(currPoint).len(); // outside on the B side
}
else {
// P lies between A and B so use dot product
dist = Math.abs(perpendicular.dot(ac));
}
if (dist > maxDist)
{
maxDist = dist;
furthestIndex = i;
}
}
}
// Check furthest point and see if it's further than the threshold
if (maxDist > inThreshold)
{
inFlags[furthestIndex] = 1;
// Make recursive calls for bit before and bit after kept point
compressSegment(inTrack, inFlags, inSegStart, furthestIndex, inThreshold);
compressSegment(inTrack, inFlags, furthestIndex, inSegEnd, inThreshold);
}
}
/**
* Find the index of the point furthest away from the start and end points
* @param inTrack the track to compress
* @param inStartIndex start index of segment to check
* @param inEndIndex end index of segment to check
* @return index of furthest point, or -1 if none found
*/
private int getFurthestPointIndex(Track inTrack, int inStartIndex, int inEndIndex)
{
int furthestIndex = -1;
if (inStartIndex >= 0 && inEndIndex > inStartIndex)
{
final DataPoint startPoint = inTrack.getPoint(inStartIndex);
double maxDist = 0.0;
// Loop over points between start and end
for (int i=inStartIndex+1; i<inEndIndex; i++)
{
DataPoint p = inTrack.getPoint(i);
if (p.isWaypoint()) {
continue;
}
double distFromStart = DataPoint.calculateRadiansBetween(startPoint, p);
if (distFromStart > maxDist)
{
furthestIndex = i;
maxDist = distFromStart;
}
}
}
return furthestIndex;
}
public String getSettingsString() {
return getType().getKey() + _factor;
}
static boolean recogniseString(String inString) {
return recogniseString(inString, CompressionMethodType.DOUGLAS_PEUCKER);
}
}
|
