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.CoordinateSequence; 17 import org.locationtech.jts.geom.Geometry; 18 import org.locationtech.jts.geom.LinearRing; 19 import org.locationtech.jts.geom.MultiPolygon; 20 import org.locationtech.jts.geom.Polygon; 21 import org.locationtech.jts.geom.util.GeometryTransformer; 22 23 /** 24 * Simplifies a {@link Geometry} using the Douglas-Peucker algorithm. 25 * Ensures that any polygonal geometries returned are valid. 26 * Simple lines are not guaranteed to remain simple after simplification. 27 * All geometry types are handled. 28 * Empty and point geometries are returned unchanged. 29 * Empty geometry components are deleted. 30 * <p> 31 * Note that in general D-P does not preserve topology - 32 * e.g. polygons can be split, collapse to lines or disappear 33 * holes can be created or disappear, 34 * and lines can cross. 35 * To simplify geometry while preserving topology use {@link TopologyPreservingSimplifier}. 36 * (However, using D-P is significantly faster). 37 *<h2>KNOWN BUGS</h2> 38 *<ul> 39 *<li>In some cases the approach used to clean invalid simplified polygons 40 *can distort the output geometry severely. 41 *</ul> 42 * 43 * 44 * @version 1.7 45 * @see TopologyPreservingSimplifier 46 */ 47 public class DouglasPeuckerSimplifier 48 { 49 50 /** 51 * Simplifies a geometry using a given tolerance. 52 * 53 * @param geom geometry to simplify 54 * @param distanceTolerance the tolerance to use 55 * @return a simplified version of the geometry 56 */ simplify(Geometry geom, double distanceTolerance)57 public static Geometry simplify(Geometry geom, double distanceTolerance) 58 { 59 DouglasPeuckerSimplifier tss = new DouglasPeuckerSimplifier(geom); 60 tss.setDistanceTolerance(distanceTolerance); 61 return tss.getResultGeometry(); 62 } 63 64 private Geometry inputGeom; 65 private double distanceTolerance; 66 private boolean isEnsureValidTopology = true; 67 68 /** 69 * Creates a simplifier for a given geometry. 70 * 71 * @param inputGeom the geometry to simplify 72 */ DouglasPeuckerSimplifier(Geometry inputGeom)73 public DouglasPeuckerSimplifier(Geometry inputGeom) 74 { 75 this.inputGeom = inputGeom; 76 } 77 78 /** 79 * Sets the distance tolerance for the simplification. 80 * All vertices in the simplified geometry will be within this 81 * distance of the original geometry. 82 * The tolerance value must be non-negative. 83 * 84 * @param distanceTolerance the approximation tolerance to use 85 */ setDistanceTolerance(double distanceTolerance)86 public void setDistanceTolerance(double distanceTolerance) { 87 if (distanceTolerance < 0.0) 88 throw new IllegalArgumentException("Tolerance must be non-negative"); 89 this.distanceTolerance = distanceTolerance; 90 } 91 92 /** 93 * Controls whether simplified polygons will be "fixed" 94 * to have valid topology. 95 * The caller may choose to disable this because: 96 * <ul> 97 * <li>valid topology is not required 98 * <li>fixing topology is a relative expensive operation 99 * <li>in some pathological cases the topology fixing operation may either fail or run for too long 100 * </ul> 101 * 102 * The default is to fix polygon topology. 103 * 104 * @param isEnsureValidTopology 105 */ setEnsureValid(boolean isEnsureValidTopology)106 public void setEnsureValid(boolean isEnsureValidTopology) 107 { 108 this.isEnsureValidTopology = isEnsureValidTopology; 109 } 110 111 /** 112 * Gets the simplified geometry. 113 * 114 * @return the simplified geometry 115 */ getResultGeometry()116 public Geometry getResultGeometry() 117 { 118 // empty input produces an empty result 119 if (inputGeom.isEmpty()) return inputGeom.copy(); 120 121 return (new DPTransformer(isEnsureValidTopology, distanceTolerance)).transform(inputGeom); 122 } 123 124 static class DPTransformer 125 extends GeometryTransformer 126 { 127 private boolean isEnsureValidTopology = true; 128 private double distanceTolerance; 129 DPTransformer(boolean isEnsureValidTopology, double distanceTolerance)130 public DPTransformer(boolean isEnsureValidTopology, double distanceTolerance) 131 { 132 this.isEnsureValidTopology = isEnsureValidTopology; 133 this.distanceTolerance = distanceTolerance; 134 } 135 transformCoordinates(CoordinateSequence coords, Geometry parent)136 protected CoordinateSequence transformCoordinates(CoordinateSequence coords, Geometry parent) 137 { 138 Coordinate[] inputPts = coords.toCoordinateArray(); 139 Coordinate[] newPts = null; 140 if (inputPts.length == 0) { 141 newPts = new Coordinate[0]; 142 } 143 else { 144 newPts = DouglasPeuckerLineSimplifier.simplify(inputPts, distanceTolerance); 145 } 146 return factory.getCoordinateSequenceFactory().create(newPts); 147 } 148 149 /** 150 * Simplifies a polygon, fixing it if required. 151 */ transformPolygon(Polygon geom, Geometry parent)152 protected Geometry transformPolygon(Polygon geom, Geometry parent) { 153 // empty geometries are simply removed 154 if (geom.isEmpty()) 155 return null; 156 Geometry rawGeom = super.transformPolygon(geom, parent); 157 // don't try and correct if the parent is going to do this 158 if (parent instanceof MultiPolygon) { 159 return rawGeom; 160 } 161 return createValidArea(rawGeom); 162 } 163 164 /** 165 * Simplifies a LinearRing. If the simplification results 166 * in a degenerate ring, remove the component. 167 * 168 * @return null if the simplification results in a degenerate ring 169 */ transformLinearRing(LinearRing geom, Geometry parent)170 protected Geometry transformLinearRing(LinearRing geom, Geometry parent) 171 { 172 boolean removeDegenerateRings = parent instanceof Polygon; 173 Geometry simpResult = super.transformLinearRing(geom, parent); 174 if (removeDegenerateRings && ! (simpResult instanceof LinearRing)) 175 return null;; 176 return simpResult; 177 } 178 179 /** 180 * Simplifies a MultiPolygon, fixing it if required. 181 */ transformMultiPolygon(MultiPolygon geom, Geometry parent)182 protected Geometry transformMultiPolygon(MultiPolygon geom, Geometry parent) { 183 Geometry rawGeom = super.transformMultiPolygon(geom, parent); 184 return createValidArea(rawGeom); 185 } 186 187 /** 188 * Creates a valid area geometry from one that possibly has 189 * bad topology (i.e. self-intersections). 190 * Since buffer can handle invalid topology, but always returns 191 * valid geometry, constructing a 0-width buffer "corrects" the 192 * topology. 193 * Note this only works for area geometries, since buffer always returns 194 * areas. This also may return empty geometries, if the input 195 * has no actual area. 196 * If the input is empty or is not polygonal, 197 * this ensures that POLYGON EMPTY is returned. 198 * 199 * @param rawAreaGeom an area geometry possibly containing self-intersections 200 * @return a valid area geometry 201 */ createValidArea(Geometry rawAreaGeom)202 private Geometry createValidArea(Geometry rawAreaGeom) 203 { 204 boolean isValidArea = rawAreaGeom.getDimension() == 2 && rawAreaGeom.isValid(); 205 // if geometry is invalid then make it valid 206 if (isEnsureValidTopology && ! isValidArea) 207 return rawAreaGeom.buffer(0.0); 208 return rawAreaGeom; 209 } 210 } 211 212 } 213 214 215