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