0
# Geometry Simplification
1
2
The Elasticsearch Geo library provides memory-efficient algorithms for simplifying complex geometries while preserving essential geometric features. The simplification framework supports both batch processing of complete geometries and streaming processing of coordinate sequences.
3
4
## Capabilities
5
6
### GeometrySimplifier Base Class
7
Abstract base class for all geometry simplification implementations.
8
9
```java { .api }
10
/**
11
* Abstract base class for geometry simplification with memory constraints
12
* @param <T> the geometry type to simplify
13
*/
14
public abstract class GeometrySimplifier<T extends Geometry> {
15
16
/**
17
* Maximum number of points to retain in simplified geometry
18
*/
19
protected final int maxPoints;
20
21
/**
22
* Error calculator for determining point removal priority
23
*/
24
protected final SimplificationErrorCalculator calculator;
25
26
/**
27
* Optional monitor for tracking simplification progress
28
*/
29
protected final StreamingGeometrySimplifier.Monitor monitor;
30
31
/**
32
* Creates a geometry simplifier with specified constraints
33
* @param description descriptive name for logging/monitoring
34
* @param maxPoints maximum points to retain
35
* @param calculator error calculator for point prioritization
36
* @param monitor optional progress monitor (can be null)
37
* @param innerSimplifier streaming simplifier for actual computation
38
*/
39
protected GeometrySimplifier(
40
String description,
41
int maxPoints,
42
SimplificationErrorCalculator calculator,
43
StreamingGeometrySimplifier.Monitor monitor,
44
StreamingGeometrySimplifier<T> innerSimplifier
45
)
46
47
/**
48
* Simplifies an entire geometry in a non-streaming fashion
49
* @param geometry the geometry to simplify
50
* @return simplified geometry with at most maxPoints vertices
51
*/
52
public abstract T simplify(T geometry);
53
54
/**
55
* Resets internal memory for reusing simplifier instance
56
* Call before processing new geometry to clear previous state
57
*/
58
public void reset();
59
}
60
```
61
62
### StreamingGeometrySimplifier
63
Memory-efficient streaming simplification for processing coordinate sequences.
64
65
```java { .api }
66
/**
67
* Streaming geometry simplifier that processes coordinates one at a time
68
* Maintains only a fixed-size buffer of points, making it very memory efficient
69
* @param <T> the geometry type to produce
70
*/
71
public class StreamingGeometrySimplifier<T extends Geometry> {
72
73
/**
74
* Monitor interface for tracking simplification progress
75
*/
76
public interface Monitor {
77
/**
78
* Called when simplification starts
79
* @param description simplification description
80
* @param maxPoints maximum points allowed
81
*/
82
void startSimplification(String description, int maxPoints);
83
84
/**
85
* Called when simplification completes
86
* @param description simplification description
87
* @param finalPoints actual number of points in result
88
*/
89
void endSimplification(String description, int finalPoints);
90
}
91
92
/**
93
* Creates a streaming simplifier
94
* @param maxPoints maximum points to retain
95
* @param calculator error calculator for point selection
96
* @param monitor optional progress monitor
97
*/
98
public StreamingGeometrySimplifier(
99
int maxPoints,
100
SimplificationErrorCalculator calculator,
101
Monitor monitor
102
)
103
104
/**
105
* Adds a coordinate point to the simplification buffer
106
* @param x longitude coordinate
107
* @param y latitude coordinate
108
* @param z altitude coordinate (can be NaN)
109
*/
110
public void addPoint(double x, double y, double z);
111
112
/**
113
* Finalizes simplification and produces the simplified geometry
114
* @return simplified geometry containing the most important points
115
*/
116
public T finish();
117
118
/**
119
* Resets the simplifier for processing new coordinate sequence
120
*/
121
public void reset();
122
}
123
```
124
125
### SimplificationErrorCalculator Interface
126
Interface for calculating errors when removing points during simplification.
127
128
```java { .api }
129
/**
130
* Interface for calculating the error introduced by removing a point
131
* Uses triangle-based error calculation with three consecutive points
132
*/
133
public interface SimplificationErrorCalculator {
134
135
/**
136
* Represents a point with coordinates for error calculation
137
*/
138
interface PointLike {
139
/**
140
* @return x coordinate (longitude)
141
*/
142
double x();
143
144
/**
145
* @return y coordinate (latitude)
146
*/
147
double y();
148
}
149
150
/**
151
* Calculates the error introduced by removing the middle point
152
* @param left the point before the candidate for removal
153
* @param middle the point candidate for removal
154
* @param right the point after the candidate for removal
155
* @return error value (higher values indicate more important points)
156
*/
157
double calculateError(PointLike left, PointLike middle, PointLike right);
158
159
/**
160
* Gets error calculator by name
161
* @param calculatorName name of the calculator implementation
162
* @return corresponding calculator instance
163
* @throws IllegalArgumentException if calculator name is unknown
164
*/
165
static SimplificationErrorCalculator byName(String calculatorName);
166
167
// Built-in calculator implementations
168
SimplificationErrorCalculator CARTESIAN_TRIANGLE_AREA = new CartesianTriangleAreaCalculator();
169
SimplificationErrorCalculator TRIANGLE_AREA = new TriangleAreaCalculator();
170
SimplificationErrorCalculator TRIANGLE_HEIGHT = new TriangleHeightCalculator();
171
SimplificationErrorCalculator HEIGHT_AND_BACKPATH_DISTANCE = new CartesianHeightAndBackpathDistanceCalculator();
172
SimplificationErrorCalculator SPHERICAL_HEIGHT_AND_BACKPATH_DISTANCE = new SphericalHeightAndBackpathDistanceCalculator();
173
174
/**
175
* Called when simplification ends to allow cleanup
176
* @param points final point list
177
*/
178
default void endSimplification(List<PointLike> points) {}
179
}
180
```
181
182
### SloppyMath Utility
183
Fast approximate mathematical operations for simplification algorithms.
184
185
```java { .api }
186
/**
187
* Utility class providing fast approximations for mathematical calculations
188
* Used in simplification algorithms where performance is more important than precision
189
*/
190
public class SloppyMath {
191
192
/**
193
* Fast approximation of distance between two points
194
* @param x1 first point longitude
195
* @param y1 first point latitude
196
* @param x2 second point longitude
197
* @param y2 second point latitude
198
* @return approximate distance
199
*/
200
public static double distance(double x1, double y1, double x2, double y2);
201
202
/**
203
* Fast approximation of haversine distance for geographic coordinates
204
* @param lat1 first point latitude in degrees
205
* @param lon1 first point longitude in degrees
206
* @param lat2 second point latitude in degrees
207
* @param lon2 second point longitude in degrees
208
* @return approximate distance in meters
209
*/
210
public static double haversinMeters(double lat1, double lon1, double lat2, double lon2);
211
212
// Additional fast mathematical approximations for geometric calculations
213
}
214
```
215
216
## Error Calculation Strategies
217
218
### Triangle Area Error Calculator
219
Calculates error based on the area of triangle formed by removing a point.
220
221
```java { .api }
222
/**
223
* Error calculator that uses triangle area as error metric
224
* Points that form larger triangles have higher error (more important)
225
*/
226
public class TriangleAreaErrorCalculator implements SimplificationErrorCalculator {
227
228
@Override
229
public double calculateError(List<PointLike> points, int index) {
230
if (index <= 0 || index >= points.size() - 1) {
231
return Double.MAX_VALUE; // Don't remove endpoints
232
}
233
234
PointLike prev = points.get(index - 1);
235
PointLike curr = points.get(index);
236
PointLike next = points.get(index + 1);
237
238
// Calculate triangle area using cross product
239
double area = Math.abs(
240
(prev.getX() - next.getX()) * (curr.getY() - next.getY()) -
241
(next.getX() - curr.getX()) * (prev.getY() - next.getY())
242
) / 2.0;
243
244
return area;
245
}
246
}
247
```
248
249
### Distance-Based Error Calculator
250
Calculates error based on perpendicular distance from point to connecting line.
251
252
```java { .api }
253
/**
254
* Error calculator based on perpendicular distance to line segment
255
* Points farther from the line formed by neighbors have higher error
256
*/
257
public class PerpendicularDistanceErrorCalculator implements SimplificationErrorCalculator {
258
259
@Override
260
public double calculateError(List<PointLike> points, int index) {
261
if (index <= 0 || index >= points.size() - 1) {
262
return Double.MAX_VALUE; // Don't remove endpoints
263
}
264
265
PointLike prev = points.get(index - 1);
266
PointLike curr = points.get(index);
267
PointLike next = points.get(index + 1);
268
269
// Calculate perpendicular distance from curr to line prev-next
270
return perpendicularDistance(
271
curr.getX(), curr.getY(),
272
prev.getX(), prev.getY(),
273
next.getX(), next.getY()
274
);
275
}
276
277
private double perpendicularDistance(double px, double py,
278
double x1, double y1,
279
double x2, double y2) {
280
double dx = x2 - x1;
281
double dy = y2 - y1;
282
283
if (dx == 0 && dy == 0) {
284
// Line segment is a point
285
return SloppyMath.distance(px, py, x1, y1);
286
}
287
288
double t = ((px - x1) * dx + (py - y1) * dy) / (dx * dx + dy * dy);
289
t = Math.max(0, Math.min(1, t)); // Clamp to line segment
290
291
double projX = x1 + t * dx;
292
double projY = y1 + t * dy;
293
294
return SloppyMath.distance(px, py, projX, projY);
295
}
296
}
297
```
298
299
## Simplification Implementations
300
301
### Line Simplification
302
Simplify line geometries while preserving shape characteristics.
303
304
```java { .api }
305
/**
306
* Example line simplifier implementation
307
*/
308
public class LineSimplifier extends GeometrySimplifier<Line> {
309
310
public LineSimplifier(int maxPoints, SimplificationErrorCalculator calculator, Monitor monitor) {
311
super("Line Simplification", maxPoints, calculator, monitor);
312
}
313
314
@Override
315
public Line simplify(Line line) {
316
if (line.isEmpty() || line.length() <= maxPoints) {
317
return line; // No simplification needed
318
}
319
320
// Use streaming simplifier for memory efficiency
321
StreamingGeometrySimplifier<Line> streaming =
322
new StreamingGeometrySimplifier<>(maxPoints, calculator, monitor);
323
324
// Add all points to streaming simplifier
325
for (int i = 0; i < line.length(); i++) {
326
streaming.addPoint(line.getX(i), line.getY(i), line.getZ(i));
327
}
328
329
return streaming.finish();
330
}
331
}
332
```
333
334
### Polygon Simplification
335
Simplify polygon geometries including holes with proportional point allocation.
336
337
```java { .api }
338
/**
339
* Example polygon simplifier that handles shells and holes
340
*/
341
public class PolygonSimplifier extends GeometrySimplifier<Polygon> {
342
343
public PolygonSimplifier(int maxPoints, SimplificationErrorCalculator calculator, Monitor monitor) {
344
super("Polygon Simplification", maxPoints, calculator, monitor);
345
}
346
347
@Override
348
public Polygon simplify(Polygon polygon) {
349
if (polygon.isEmpty()) {
350
return polygon;
351
}
352
353
LinearRing shell = polygon.getPolygon();
354
int totalPoints = shell.length();
355
356
// Count total points in all holes
357
for (int i = 0; i < polygon.getNumberOfHoles(); i++) {
358
totalPoints += polygon.getHole(i).length();
359
}
360
361
if (totalPoints <= maxPoints) {
362
return polygon; // No simplification needed
363
}
364
365
// Allocate points proportionally
366
int shellPoints = Math.max(4, (shell.length() * maxPoints) / totalPoints);
367
LinearRing simplifiedShell = simplifyRing(shell, shellPoints);
368
369
// Simplify holes proportionally
370
List<LinearRing> simplifiedHoles = new ArrayList<>();
371
int remainingPoints = maxPoints - simplifiedShell.length();
372
373
for (int i = 0; i < polygon.getNumberOfHoles() && remainingPoints > 0; i++) {
374
LinearRing hole = polygon.getHole(i);
375
int holePoints = Math.max(4, Math.min(remainingPoints,
376
(hole.length() * maxPoints) / totalPoints));
377
378
LinearRing simplifiedHole = simplifyRing(hole, holePoints);
379
simplifiedHoles.add(simplifiedHole);
380
remainingPoints -= simplifiedHole.length();
381
}
382
383
return new Polygon(simplifiedShell, simplifiedHoles);
384
}
385
386
private LinearRing simplifyRing(LinearRing ring, int targetPoints) {
387
if (ring.length() <= targetPoints) {
388
return ring;
389
}
390
391
// Use streaming simplifier for the ring
392
StreamingGeometrySimplifier<Line> streaming =
393
new StreamingGeometrySimplifier<>(targetPoints, calculator, monitor);
394
395
for (int i = 0; i < ring.length(); i++) {
396
streaming.addPoint(ring.getX(i), ring.getY(i), ring.getZ(i));
397
}
398
399
Line simplifiedLine = streaming.finish();
400
401
// Convert back to LinearRing (ensure closure)
402
double[] x = simplifiedLine.getX();
403
double[] y = simplifiedLine.getY();
404
double[] z = simplifiedLine.getZ();
405
406
// Ensure ring is closed
407
if (x[0] != x[x.length - 1] || y[0] != y[y.length - 1] ||
408
(z != null && z[0] != z[z.length - 1])) {
409
// Add closing point
410
x = Arrays.copyOf(x, x.length + 1);
411
y = Arrays.copyOf(y, y.length + 1);
412
x[x.length - 1] = x[0];
413
y[y.length - 1] = y[0];
414
415
if (z != null) {
416
z = Arrays.copyOf(z, z.length + 1);
417
z[z.length - 1] = z[0];
418
}
419
}
420
421
return new LinearRing(x, y, z);
422
}
423
}
424
```
425
426
## Usage Examples
427
428
### Basic Line Simplification
429
430
```java
431
import org.elasticsearch.geometry.*;
432
import org.elasticsearch.geometry.simplify.*;
433
434
// Create a complex line with many points
435
double[] lons = new double[1000];
436
double[] lats = new double[1000];
437
for (int i = 0; i < 1000; i++) {
438
lons[i] = -74.0 + (i * 0.001); // Incremental longitude
439
lats[i] = 40.7 + Math.sin(i * 0.1) * 0.01; // Wavy latitude
440
}
441
Line complexLine = new Line(lons, lats);
442
443
// Create simplifier with triangle area error calculator
444
SimplificationErrorCalculator calculator = new TriangleAreaErrorCalculator();
445
LineSimplifier simplifier = new LineSimplifier(100, calculator, null);
446
447
// Simplify the line
448
Line simplifiedLine = simplifier.simplify(complexLine);
449
450
System.out.println("Original points: " + complexLine.length()); // 1000
451
System.out.println("Simplified points: " + simplifiedLine.length()); // <= 100
452
453
// Reuse simplifier for another line
454
simplifier.reset();
455
Line anotherSimplified = simplifier.simplify(anotherComplexLine);
456
```
457
458
### Polygon Simplification with Monitoring
459
460
```java
461
// Create monitoring implementation
462
StreamingGeometrySimplifier.Monitor monitor = new StreamingGeometrySimplifier.Monitor() {
463
@Override
464
public void startSimplification(String description, int maxPoints) {
465
System.out.println("Starting " + description + " with max " + maxPoints + " points");
466
}
467
468
@Override
469
public void endSimplification(String description, int finalPoints) {
470
System.out.println("Completed " + description + " with " + finalPoints + " points");
471
}
472
};
473
474
// Create complex polygon
475
double[] shellLons = new double[500];
476
double[] shellLats = new double[500];
477
// ... populate arrays with complex polygon boundary
478
479
LinearRing shell = new LinearRing(shellLons, shellLats);
480
Polygon complexPolygon = new Polygon(shell);
481
482
// Simplify with monitoring
483
SimplificationErrorCalculator calculator = new PerpendicularDistanceErrorCalculator();
484
PolygonSimplifier polygonSimplifier = new PolygonSimplifier(50, calculator, monitor);
485
486
Polygon simplified = polygonSimplifier.simplify(complexPolygon);
487
// Output: "Starting Polygon Simplification with max 50 points"
488
// Output: "Completed Polygon Simplification with 47 points"
489
```
490
491
### Streaming Simplification
492
493
```java
494
// Direct use of streaming simplifier for coordinate streams
495
SimplificationErrorCalculator calculator = new TriangleAreaErrorCalculator();
496
StreamingGeometrySimplifier<Line> streaming =
497
new StreamingGeometrySimplifier<>(100, calculator, null);
498
499
// Process coordinates from external source (file, network, etc.)
500
BufferedReader coordSource = // ... coordinate source
501
String coordLine;
502
while ((coordLine = coordSource.readLine()) != null) {
503
String[] parts = coordLine.split(",");
504
double lon = Double.parseDouble(parts[0]);
505
double lat = Double.parseDouble(parts[1]);
506
507
streaming.addPoint(lon, lat, Double.NaN);
508
}
509
510
// Get simplified result
511
Line streamingResult = streaming.finish();
512
513
System.out.println("Streaming simplified to: " + streamingResult.length() + " points");
514
```
515
516
### Custom Error Calculator
517
518
```java
519
// Create custom error calculator that considers geographic distance
520
public class GeographicErrorCalculator implements SimplificationErrorCalculator {
521
522
@Override
523
public double calculateError(List<PointLike> points, int index) {
524
if (index <= 0 || index >= points.size() - 1) {
525
return Double.MAX_VALUE;
526
}
527
528
PointLike prev = points.get(index - 1);
529
PointLike curr = points.get(index);
530
PointLike next = points.get(index + 1);
531
532
// Use haversine distance for geographic accuracy
533
double distToPrev = SloppyMath.haversinMeters(
534
curr.getY(), curr.getX(), prev.getY(), prev.getX());
535
double distToNext = SloppyMath.haversinMeters(
536
curr.getY(), curr.getX(), next.getY(), next.getX());
537
double directDist = SloppyMath.haversinMeters(
538
prev.getY(), prev.getX(), next.getY(), next.getX());
539
540
// Error is the difference between going through curr vs. direct
541
return (distToPrev + distToNext) - directDist;
542
}
543
}
544
545
// Use custom calculator
546
GeographicErrorCalculator geoCalculator = new GeographicErrorCalculator();
547
LineSimplifier geoSimplifier = new LineSimplifier(100, geoCalculator, null);
548
```