Polygonizer.java
/*
* Copyright (c) 2016 Vivid Solutions.
*
* 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.operation.polygonize;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryComponentFilter;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LineString;
import org.locationtech.jts.geom.Polygon;
/**
* Polygonizes a set of {@link Geometry}s which contain linework that
* represents the edges of a planar graph.
* All types of Geometry are accepted as input;
* the constituent linework is extracted as the edges to be polygonized.
* The processed edges must be correctly noded; that is, they must only meet
* at their endpoints. Polygonization will accept incorrectly noded input
* but will not form polygons from non-noded edges,
* and reports them as errors.
* <p>
* The Polygonizer reports the follow kinds of errors:
* <ul>
* <li><b>{@link #getDangles() Dangles}</b> - edges which have one or both ends which are not incident on another edge endpoint
* <li><b>{@link #getCutEdges() Cut Edges}</b> - edges which are connected at both ends but which do not form part of polygon
* <li><b>{@link #getInvalidRingLines() Invalid Ring Lines}</b> - edges which form rings which are invalid
* (e.g. the component lines contain a self-intersection)
* </ul>
* The {@link #Polygonizer(boolean)} constructor allows
* extracting only polygons which form a valid polygonal result.
* The set of extracted polygons is guaranteed to be edge-disjoint.
* This is useful where it is known that the input lines form a
* valid polygonal geometry (which may include holes or nested polygons).
*
* @version 1.7
*/
public class Polygonizer
{
/**
* Adds every linear element in a {@link Geometry} into the polygonizer graph.
*/
private static class LineStringAdder
implements GeometryComponentFilter
{
Polygonizer p;
LineStringAdder(Polygonizer p) {
this.p = p;
}
public void filter(Geometry g) {
if (g instanceof LineString)
p.add((LineString) g);
}
}
// default factory
private LineStringAdder lineStringAdder = new LineStringAdder(this);
protected PolygonizeGraph graph;
// initialize with empty collections, in case nothing is computed
protected Collection<LineString> dangles = new ArrayList<LineString>();
protected List<LineString> cutEdges = new ArrayList<LineString>();
protected List<LineString> invalidRingLines = new ArrayList<LineString>();
protected List<EdgeRing> holeList = null;
protected List<EdgeRing> shellList = null;
protected List<Polygon> polyList = null;
private boolean isCheckingRingsValid = true;
private boolean extractOnlyPolygonal;
private GeometryFactory geomFactory = null;
/**
* Creates a polygonizer that extracts all polygons.
*/
public Polygonizer()
{
this(false);
}
/**
* Creates a polygonizer, specifying whether a valid polygonal geometry must be created.
* If the argument is <code>true</code>
* then areas may be discarded in order to
* ensure that the extracted geometry is a valid polygonal geometry.
*
* @param extractOnlyPolygonal true if a valid polygonal geometry should be extracted
*/
public Polygonizer(boolean extractOnlyPolygonal)
{
this.extractOnlyPolygonal = extractOnlyPolygonal;
}
/**
* Adds a collection of geometries to the edges to be polygonized.
* May be called multiple times.
* Any dimension of Geometry may be added;
* the constituent linework will be extracted and used.
*
* @param geomList a list of {@link Geometry}s with linework to be polygonized
*/
public void add(Collection geomList)
{
for (Iterator i = geomList.iterator(); i.hasNext(); ) {
Geometry geometry = (Geometry) i.next();
add(geometry);
}
}
/**
* Add a {@link Geometry} to the edges to be polygonized.
* May be called multiple times.
* Any dimension of Geometry may be added;
* the constituent linework will be extracted and used
*
* @param g a {@link Geometry} with linework to be polygonized
*/
public void add(Geometry g)
{
g.apply(lineStringAdder);
}
/**
* Adds a linestring to the graph of polygon edges.
*
* @param line the {@link LineString} to add
*/
private void add(LineString line)
{
// record the geometry factory for later use
geomFactory = line.getFactory();
// create a new graph using the factory from the input Geometry
if (graph == null)
graph = new PolygonizeGraph(geomFactory);
graph.addEdge(line);
}
/**
* Allows disabling the valid ring checking,
* to optimize situations where invalid rings are not expected.
* <p>
* The default is <code>true</code>.
*
* @param isCheckingRingsValid true if generated rings should be checked for validity
*/
public void setCheckRingsValid(boolean isCheckingRingsValid)
{
this.isCheckingRingsValid = isCheckingRingsValid;
}
/**
* Gets the list of polygons formed by the polygonization.
* @return a collection of {@link Polygon}s
*/
public Collection getPolygons()
{
polygonize();
return polyList;
}
/**
* Gets a geometry representing the polygons formed by the polygonization.
* If a valid polygonal geometry was extracted the result is a {@link org.locationtech.jts.geom.Polygonal} geometry.
*
* @return a geometry containing the polygons
*/
public Geometry getGeometry()
{
if (geomFactory == null) geomFactory = new GeometryFactory();
polygonize();
if (extractOnlyPolygonal) {
return geomFactory.buildGeometry(polyList);
}
// result may not be valid Polygonal, so return as a GeometryCollection
return geomFactory.createGeometryCollection(GeometryFactory.toGeometryArray(polyList));
}
/**
* Gets the list of dangling lines found during polygonization.
* @return a collection of the input {@link LineString}s which are dangles
*/
public Collection getDangles()
{
polygonize();
return dangles;
}
/**
* Gets the list of cut edges found during polygonization.
* @return a collection of the input {@link LineString}s which are cut edges
*/
public Collection getCutEdges()
{
polygonize();
return cutEdges;
}
/**
* Gets the list of lines forming invalid rings found during polygonization.
* @return a collection of the input {@link LineString}s which form invalid rings
*/
public Collection getInvalidRingLines()
{
polygonize();
return invalidRingLines;
}
/**
* Performs the polygonization, if it has not already been carried out.
*/
private void polygonize()
{
// check if already computed
if (polyList != null) return;
polyList = new ArrayList<Polygon>();
// if no geometries were supplied it's possible that graph is null
if (graph == null) return;
dangles = graph.deleteDangles();
cutEdges = graph.deleteCutEdges();
List<EdgeRing> edgeRingList = graph.getEdgeRings();
//Debug.printTime("Build Edge Rings");
List<EdgeRing> validEdgeRingList = new ArrayList<EdgeRing>();
List<EdgeRing> invalidRings = new ArrayList<EdgeRing>();
if (isCheckingRingsValid) {
findValidRings(edgeRingList, validEdgeRingList, invalidRings);
invalidRingLines = extractInvalidLines(invalidRings);
}
else {
validEdgeRingList = edgeRingList;
}
//Debug.printTime("Validate Rings");
findShellsAndHoles(validEdgeRingList);
HoleAssigner.assignHolesToShells(holeList, shellList);
// order the shells to make any subsequent processing deterministic
Collections.sort(shellList, new EdgeRing.EnvelopeComparator());
//Debug.printTime("Assign Holes");
boolean includeAll = true;
if (extractOnlyPolygonal) {
findDisjointShells(shellList);
includeAll = false;
}
polyList = extractPolygons(shellList, includeAll);
}
private void findValidRings(List<EdgeRing> edgeRingList, List<EdgeRing> validEdgeRingList, List<EdgeRing> invalidRingList)
{
for (EdgeRing er : edgeRingList) {
er.computeValid();
if (er.isValid())
validEdgeRingList.add(er);
else
invalidRingList.add(er);
}
}
private void findShellsAndHoles(List<EdgeRing> edgeRingList)
{
holeList = new ArrayList<EdgeRing>();
shellList = new ArrayList<EdgeRing>();
for (EdgeRing er : edgeRingList) {
er.computeHole();
if (er.isHole())
holeList.add(er);
else
shellList.add(er);
}
}
private static void findDisjointShells(List<EdgeRing> shellList) {
findOuterShells(shellList);
boolean isMoreToScan;
do {
isMoreToScan = false;
for (EdgeRing er : shellList) {
if (er.isIncludedSet())
continue;
er.updateIncluded();
if (! er.isIncludedSet()) {
isMoreToScan = true;
}
}
} while (isMoreToScan);
}
/**
* For each outer hole finds and includes a single outer shell.
* This seeds the traversal algorithm for finding only polygonal shells.
*
* @param shellList the list of shell EdgeRings
*/
private static void findOuterShells(List<EdgeRing> shellList) {
for (EdgeRing er : shellList) {
EdgeRing outerHoleER = er.getOuterHole();
if (outerHoleER != null && ! outerHoleER.isProcessed()) {
er.setIncluded(true);
outerHoleER.setProcessed(true);
}
}
}
/**
* Extracts unique lines for invalid rings,
* discarding rings which correspond to outer rings and hence contain
* duplicate linework.
*
* @param invalidRings
* @return
*/
private List<LineString> extractInvalidLines(List<EdgeRing> invalidRings) {
/**
* Sort rings by increasing envelope area.
* This causes inner rings to be processed before the outer rings
* containing them, which allows outer invalid rings to be discarded
* since their linework is already reported in the inner rings.
*/
Collections.sort(invalidRings, new EdgeRing.EnvelopeAreaComparator());
/**
* Scan through rings. Keep only rings which have an adjacent EdgeRing
* which is either valid or marked as not processed.
* This avoids including outer rings which have linework which is duplicated.
*/
List<LineString> invalidLines = new ArrayList<LineString>();
for (EdgeRing er : invalidRings) {
if (isIncludedInvalid(er)) {
invalidLines.add(er.getLineString());
}
er.setProcessed(true);
}
return invalidLines;
}
/**
* Tests if a invalid ring should be included in
* the list of reported invalid rings.
*
* Rings are included only if they contain
* linework which is not already in a valid ring,
* or in an already-included ring.
*
* Because the invalid rings list is sorted by extent area,
* this results in outer rings being discarded,
* since all their linework is reported in the rings they contain.
*
* @param invalidRing the ring to test
* @return true if the ring should be included
*/
private boolean isIncludedInvalid(EdgeRing invalidRing) {
for (PolygonizeDirectedEdge de : invalidRing.getEdges()) {
PolygonizeDirectedEdge deAdj = (PolygonizeDirectedEdge) de.getSym();
EdgeRing erAdj = deAdj.getRing();
/**
*
*/
boolean isEdgeIncluded = erAdj.isValid() || erAdj.isProcessed();
if ( ! isEdgeIncluded)
return true;
}
return false;
}
private static List<Polygon> extractPolygons(List<EdgeRing> shellList, boolean includeAll) {
List<Polygon> polyList = new ArrayList<Polygon>();
for (EdgeRing er : shellList) {
if (includeAll || er.isIncluded()) {
polyList.add(er.getPolygon());
}
}
return polyList;
}
}