1 /*
2  * Copyright (c) 2016 Vivid Solutions.
3  *
4  * All rights reserved. This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License 2.0
6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8  * and the Eclipse Distribution License is available at
9  *
10  * http://www.eclipse.org/org/documents/edl-v10.php.
11  */
12 
13 package org.locationtech.jts.simplify;
14 
15 import org.locationtech.jts.geom.Coordinate;
16 import org.locationtech.jts.geom.CoordinateList;
17 import org.locationtech.jts.geom.LineSegment;
18 
19 /**
20  * Simplifies a linestring (sequence of points) using
21  * the standard Douglas-Peucker algorithm.
22  *
23  * @version 1.7
24  */
25 class DouglasPeuckerLineSimplifier
26 {
simplify(Coordinate[] pts, double distanceTolerance)27   public static Coordinate[] simplify(Coordinate[] pts, double distanceTolerance)
28   {
29     DouglasPeuckerLineSimplifier simp = new DouglasPeuckerLineSimplifier(pts);
30     simp.setDistanceTolerance(distanceTolerance);
31     return simp.simplify();
32   }
33 
34   private Coordinate[] pts;
35   private boolean[] usePt;
36   private double distanceTolerance;
37 
DouglasPeuckerLineSimplifier(Coordinate[] pts)38   public DouglasPeuckerLineSimplifier(Coordinate[] pts)
39   {
40     this.pts = pts;
41   }
42   /**
43    * Sets the distance tolerance for the simplification.
44    * All vertices in the simplified linestring will be within this
45    * distance of the original linestring.
46    *
47    * @param distanceTolerance the approximation tolerance to use
48    */
setDistanceTolerance(double distanceTolerance)49   public void setDistanceTolerance(double distanceTolerance) {
50     this.distanceTolerance = distanceTolerance;
51   }
52 
simplify()53   public Coordinate[] simplify()
54   {
55     usePt = new boolean[pts.length];
56     for (int i = 0; i < pts.length; i++) {
57       usePt[i] = true;
58     }
59     simplifySection(0, pts.length - 1);
60     CoordinateList coordList = new CoordinateList();
61     for (int i = 0; i < pts.length; i++) {
62       if (usePt[i])
63         coordList.add(new Coordinate(pts[i]));
64     }
65     return coordList.toCoordinateArray();
66   }
67 
68   private LineSegment seg = new LineSegment();
69 
simplifySection(int i, int j)70   private void simplifySection(int i, int j)
71   {
72     if((i+1) == j) {
73       return;
74     }
75     seg.p0 = pts[i];
76     seg.p1 = pts[j];
77     double maxDistance = -1.0;
78     int maxIndex = i;
79     for (int k = i + 1; k < j; k++) {
80       double distance = seg.distance(pts[k]);
81       if (distance > maxDistance) {
82         maxDistance = distance;
83         maxIndex = k;
84       }
85     }
86     if (maxDistance <= distanceTolerance) {
87       for(int k = i + 1; k < j; k++) {
88         usePt[k] = false;
89       }
90     }
91     else {
92       simplifySection(i, maxIndex);
93       simplifySection(maxIndex, j);
94     }
95   }
96 
97 }
98