GeometryFixer.java
/*
* Copyright (c) 2021 Martin Davis.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.geom.util;
import java.util.ArrayList;
import java.util.List;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.CoordinateArrays;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryCollection;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LineString;
import org.locationtech.jts.geom.LinearRing;
import org.locationtech.jts.geom.MultiLineString;
import org.locationtech.jts.geom.MultiPoint;
import org.locationtech.jts.geom.MultiPolygon;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.geom.Polygon;
import org.locationtech.jts.geom.prep.PreparedGeometry;
import org.locationtech.jts.geom.prep.PreparedGeometryFactory;
import org.locationtech.jts.operation.buffer.BufferOp;
import org.locationtech.jts.operation.overlayng.OverlayNG;
import org.locationtech.jts.operation.overlayng.OverlayNGRobust;
/**
* Fixes a geometry to be a valid geometry, while preserving as much as
* possible of the shape and location of the input.
* Validity is determined according to {@link Geometry#isValid()}.
* <p>
* Input geometries are always processed, so even valid inputs may
* have some minor alterations. The output is always a new geometry object.
*
* <h2>Semantic Rules</h2>
* <ol>
* <li>Vertices with non-finite X or Y ordinates are removed
* (as per {@link Coordinate#isValid()}.</li>
* <li>Repeated points are reduced to a single point</li>
* <li>Empty atomic geometries are valid and are returned unchanged</li>
* <li>Empty elements are removed from collections</li>
* <li><code>Point</code>: keep valid coordinate, or EMPTY</li>
* <li><code>LineString</code>: coordinates are fixed</li>
* <li><code>LinearRing</code>: coordinates are fixed. Keep valid ring, or else convert into <code>LineString</code></li>
* <li><code>Polygon</code>: transform into a valid polygon or multipolygon,
* preserving as much of the extent and vertices as possible.
* <ul>
* <li>Rings are fixed to ensure they are valid</li>
* <li>Holes intersecting the shell are subtracted from the shell</li>
* <li>Holes outside the shell are converted into polygons</li>
* </ul></li>
* <li><code>MultiPolygon</code>: each polygon is fixed,
* then result made non-overlapping (via union)</li>
* <li><code>GeometryCollection</code>: each element is fixed</li>
* <li>Collapsed lines and polygons are handled as follows,
* depending on the <code>keepCollapsed</code> setting:
* <ul>
* <li><code>false</code>: (default) collapses are converted to empty geometries
* (and removed if they are elements of collections)</li>
* <li><code>true</code>: collapses are converted to a valid geometry of lower dimension</li>
* </ul>
* </li>
* </ol>
*
* @author Martin Davis
*
* @see Geometry#isValid()
*/
public class GeometryFixer {
private static final boolean DEFAULT_KEEP_MULTI = true;
/**
* Fixes a geometry to be valid.
*
* @param geom the geometry to be fixed
* @return the valid fixed geometry
*/
public static Geometry fix(Geometry geom) {
return fix(geom, DEFAULT_KEEP_MULTI);
}
/**
* Fixes a geometry to be valid, allowing to set a flag controlling how
* single item results from fixed {@code MULTI} geometries should be
* returned.
*
* @param geom the geometry to be fixed
* @param isKeepMulti a flag indicating if {@code MULTI} geometries should not be converted to single instance types
* if they consist of only one item.
* @return the valid fixed geometry
*/
public static Geometry fix(Geometry geom, boolean isKeepMulti) {
GeometryFixer fix = new GeometryFixer(geom);
fix.setKeepMulti(isKeepMulti);
return fix.getResult();
}
private Geometry geom;
private GeometryFactory factory;
private boolean isKeepCollapsed = false;
private boolean isKeepMulti = DEFAULT_KEEP_MULTI;
/**
* Creates a new instance to fix a given geometry.
*
* @param geom the geometry to be fixed
*/
public GeometryFixer(Geometry geom) {
this.geom = geom;
this.factory = geom.getFactory();
}
/**
* Sets whether collapsed geometries are converted to empty,
* (which will be removed from collections),
* or to a valid geometry of lower dimension.
* The default is to convert collapses to empty geometries.
*
* @param isKeepCollapsed whether collapses should be converted to a lower dimension geometry
*/
public void setKeepCollapsed(boolean isKeepCollapsed) {
this.isKeepCollapsed = isKeepCollapsed;
}
/**
* Sets whether fixed {@code MULTI} geometries that consist of
* only one item should still be returned as {@code MULTI} geometries.
*
* The default is to keep {@code MULTI} geometries.
*
* @param isKeepMulti flag whether to keep {@code MULTI} geometries.
*/
public void setKeepMulti(boolean isKeepMulti) {
this.isKeepMulti = isKeepMulti;
}
/**
* Gets the fixed geometry.
*
* @return the fixed geometry
*/
public Geometry getResult() {
/*
* Truly empty geometries are simply copied.
* Geometry collections with elements are evaluated on a per-element basis.
*/
if (geom.getNumGeometries() == 0) {
return geom.copy();
}
if (geom instanceof Point) return fixPoint((Point) geom);
// LinearRing must come before LineString
if (geom instanceof LinearRing) return fixLinearRing((LinearRing) geom);
if (geom instanceof LineString) return fixLineString((LineString) geom);
if (geom instanceof Polygon) return fixPolygon((Polygon) geom);
if (geom instanceof MultiPoint) return fixMultiPoint((MultiPoint) geom);
if (geom instanceof MultiLineString) return fixMultiLineString((MultiLineString) geom);
if (geom instanceof MultiPolygon) return fixMultiPolygon((MultiPolygon) geom);
if (geom instanceof GeometryCollection) return fixCollection((GeometryCollection) geom);
throw new UnsupportedOperationException(geom.getClass().getName());
}
private Point fixPoint(Point geom) {
Geometry pt = fixPointElement(geom);
if (pt == null)
return factory.createPoint();
return (Point) pt;
}
private Point fixPointElement(Point geom) {
if (geom.isEmpty() || ! isValidPoint(geom)) {
return null;
}
return (Point) geom.copy();
}
private static boolean isValidPoint(Point pt) {
Coordinate p = pt.getCoordinate();
return p.isValid();
}
private Geometry fixMultiPoint(MultiPoint geom) {
List<Point> pts = new ArrayList<Point>();
for (int i = 0; i < geom.getNumGeometries(); i++) {
Point pt = (Point) geom.getGeometryN(i);
if (pt.isEmpty()) continue;
Point fixPt = fixPointElement(pt);
if (fixPt != null) {
pts.add(fixPt);
}
}
if (!this.isKeepMulti && pts.size() == 1)
return pts.get(0);
return factory.createMultiPoint(GeometryFactory.toPointArray(pts));
}
private Geometry fixLinearRing(LinearRing geom) {
Geometry fix = fixLinearRingElement(geom);
if (fix == null)
return factory.createLinearRing();
return fix;
}
private Geometry fixLinearRingElement(LinearRing geom) {
if (geom.isEmpty()) return null;
Coordinate[] pts = geom.getCoordinates();
Coordinate[] ptsFix = fixCoordinates(pts);
if (this.isKeepCollapsed) {
if (ptsFix.length == 1) {
return factory.createPoint(ptsFix[0]);
}
if (ptsFix.length > 1 && ptsFix.length <= 3) {
return factory.createLineString(ptsFix);
}
}
//--- too short to be a valid ring
if (ptsFix.length <= 3) {
return null;
}
LinearRing ring = factory.createLinearRing(ptsFix);
//--- convert invalid ring to LineString
if (! ring.isValid()) {
return factory.createLineString(ptsFix);
}
return ring;
}
private Geometry fixLineString(LineString geom) {
Geometry fix = fixLineStringElement(geom);
if (fix == null)
return factory.createLineString();
return fix;
}
private Geometry fixLineStringElement(LineString geom) {
if (geom.isEmpty()) return null;
Coordinate[] pts = geom.getCoordinates();
Coordinate[] ptsFix = fixCoordinates(pts);
if (this.isKeepCollapsed && ptsFix.length == 1) {
return factory.createPoint(ptsFix[0]);
}
if (ptsFix.length <= 1) {
return null;
}
return factory.createLineString(ptsFix);
}
/**
* Returns a clean copy of the input coordinate array.
*
* @param pts coordinates to clean
* @return an array of clean coordinates
*/
private static Coordinate[] fixCoordinates(Coordinate[] pts) {
Coordinate[] ptsClean = CoordinateArrays.removeRepeatedOrInvalidPoints(pts);
return CoordinateArrays.copyDeep(ptsClean);
}
private Geometry fixMultiLineString(MultiLineString geom) {
List<Geometry> fixed = new ArrayList<Geometry>();
boolean isMixed = false;
for (int i = 0; i < geom.getNumGeometries(); i++) {
LineString line = (LineString) geom.getGeometryN(i);
if (line.isEmpty()) continue;
Geometry fix = fixLineStringElement(line);
if (fix == null) continue;
if (! (fix instanceof LineString)) {
isMixed = true;
}
fixed.add(fix);
}
if (fixed.size() == 1) {
if (!this.isKeepMulti || !(fixed.get(0) instanceof LineString))
return fixed.get(0);
}
if (isMixed) {
return factory.createGeometryCollection(GeometryFactory.toGeometryArray(fixed));
}
return factory.createMultiLineString(GeometryFactory.toLineStringArray(fixed));
}
private Geometry fixPolygon(Polygon geom) {
Geometry fix = fixPolygonElement(geom);
if (fix == null)
return factory.createPolygon();
return fix;
}
private Geometry fixPolygonElement(Polygon geom) {
LinearRing shell = geom.getExteriorRing();
Geometry fixShell = fixRing(shell);
if (fixShell.isEmpty()) {
if (this.isKeepCollapsed) {
return fixLineString(shell);
}
//--- if not allowing collapses then return empty polygon
return null;
}
//--- if no holes then done
if (geom.getNumInteriorRing() == 0) {
return fixShell;
}
//--- fix holes, classify, and construct shell-true holes
List<Geometry> holesFixed = fixHoles(geom);
List<Geometry> holes = new ArrayList<Geometry>();
List<Geometry> shells = new ArrayList<Geometry>();
classifyHoles(fixShell, holesFixed, holes, shells);
Geometry polyWithHoles = difference(fixShell, holes);
if (shells.size() == 0) {
return polyWithHoles;
}
//--- if some holes converted to shells, union all shells
shells.add(polyWithHoles);
Geometry result = union(shells);
return result;
}
private List<Geometry> fixHoles(Polygon geom) {
List<Geometry> holes = new ArrayList<Geometry>();
for (int i = 0; i < geom.getNumInteriorRing(); i++) {
Geometry holeRep = fixRing(geom.getInteriorRingN(i));
if (holeRep != null) {
holes.add(holeRep);
}
}
return holes;
}
private void classifyHoles(Geometry shell, List<Geometry> holesFixed, List<Geometry> holes, List<Geometry> shells) {
PreparedGeometry shellPrep = PreparedGeometryFactory.prepare(shell);
for (Geometry hole : holesFixed) {
if (shellPrep.intersects(hole)) {
holes.add(hole);
}
else {
shells.add(hole);
}
}
}
/**
* Subtracts a list of polygonal geometries from a polygonal geometry.
*
* @param shell polygonal geometry for shell
* @param holes polygonal geometries to subtract
* @return the result geometry
*/
private Geometry difference(Geometry shell, List<Geometry> holes) {
if (holes == null || holes.size() == 0)
return shell;
Geometry holesUnion = union(holes);
return OverlayNGRobust.overlay(shell, holesUnion, OverlayNG.DIFFERENCE);
}
/**
* Unions a list of polygonal geometries.
* Optimizes case of zero or one input geometries.
* Requires that the inputs are net new objects.
*
* @param polys the polygonal geometries to union
* @return the union of the inputs
*/
private Geometry union(List<Geometry> polys) {
if (polys.size() == 0) return factory.createPolygon();
if (polys.size() == 1) {
return polys.get(0);
}
// TODO: replace with holes.union() once OverlayNG is the default
return OverlayNGRobust.union(polys);
}
private Geometry fixRing(LinearRing ring) {
//-- always execute fix, since it may remove repeated/invalid coords etc
// TODO: would it be faster to check ring validity first?
Geometry poly = factory.createPolygon(ring);
return BufferOp.bufferByZero(poly, true);
}
private Geometry fixMultiPolygon(MultiPolygon geom) {
List<Geometry> polys = new ArrayList<Geometry>();
for (int i = 0; i < geom.getNumGeometries(); i++) {
Polygon poly = (Polygon) geom.getGeometryN(i);
Geometry polyFix = fixPolygonElement(poly);
if (polyFix != null && ! polyFix.isEmpty()) {
polys.add(polyFix);
}
}
if (polys.size() == 0) {
return factory.createMultiPolygon();
}
// TODO: replace with polys.union() once OverlayNG is the default
Geometry result = union(polys);
if (this.isKeepMulti && result instanceof Polygon)
result = factory.createMultiPolygon(new Polygon[]{(Polygon) result});
return result;
}
private Geometry fixCollection(GeometryCollection geom) {
Geometry[] geomRep = new Geometry[geom.getNumGeometries()];
for (int i = 0; i < geom.getNumGeometries(); i++) {
geomRep[i] = fix(geom.getGeometryN(i), this.isKeepCollapsed, this.isKeepMulti);
}
return factory.createGeometryCollection(geomRep);
}
private static Geometry fix(Geometry geom, boolean isKeepCollapsed, boolean isKeepMulti) {
GeometryFixer fix = new GeometryFixer(geom);
fix.setKeepCollapsed(isKeepCollapsed);
fix.setKeepMulti(isKeepMulti);
return fix.getResult();
}
}