EdgeNodingBuilder.java
/*
* Copyright (c) 2019 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.operation.overlayng;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import org.locationtech.jts.algorithm.LineIntersector;
import org.locationtech.jts.algorithm.Orientation;
import org.locationtech.jts.algorithm.RobustLineIntersector;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.CoordinateArrays;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryCollection;
import org.locationtech.jts.geom.LineString;
import org.locationtech.jts.geom.LinearRing;
import org.locationtech.jts.geom.MultiLineString;
import org.locationtech.jts.geom.MultiPolygon;
import org.locationtech.jts.geom.Polygon;
import org.locationtech.jts.geom.PrecisionModel;
import org.locationtech.jts.noding.IntersectionAdder;
import org.locationtech.jts.noding.MCIndexNoder;
import org.locationtech.jts.noding.NodedSegmentString;
import org.locationtech.jts.noding.Noder;
import org.locationtech.jts.noding.SegmentString;
import org.locationtech.jts.noding.ValidatingNoder;
import org.locationtech.jts.noding.snapround.SnapRoundingNoder;
/**
* Builds a set of noded, unique, labelled Edges from
* the edges of the two input geometries.
* <p>
* It performs the following steps:
* <ul>
* <li>Extracts input edges, and attaches topological information
* <li>if clipping is enabled, handles clipping or limiting input geometry
* <li>chooses a {@link Noder} based on provided precision model, unless a custom one is supplied
* <li>calls the chosen Noder, with precision model
* <li>removes any fully collapsed noded edges
* <li>builds {@link Edge}s and merges them
* </ul>
*
* @author mdavis
*
*/
class EdgeNodingBuilder {
/**
* Limiting is skipped for Lines with few vertices,
* to avoid additional copying.
*/
private static final int MIN_LIMIT_PTS = 20;
/**
* Indicates whether floating precision noder output is validated.
*/
private static final boolean IS_NODING_VALIDATED = true;
private static Noder createFixedPrecisionNoder(PrecisionModel pm) {
//Noder noder = new MCIndexSnapRounder(pm);
//Noder noder = new SimpleSnapRounder(pm);
Noder noder = new SnapRoundingNoder(pm);
return noder;
}
private static Noder createFloatingPrecisionNoder(boolean doValidation) {
MCIndexNoder mcNoder = new MCIndexNoder();
LineIntersector li = new RobustLineIntersector();
mcNoder.setSegmentIntersector(new IntersectionAdder(li));
Noder noder = mcNoder;
if (doValidation) {
noder = new ValidatingNoder( mcNoder);
}
return noder;
}
private PrecisionModel pm;
private List<NodedSegmentString> inputEdges = new ArrayList<NodedSegmentString>();
private Noder customNoder;
private Envelope clipEnv = null;
private RingClipper clipper;
private LineLimiter limiter;
private boolean[] hasEdges = new boolean[2];
/**
* Creates a new builder, with an optional custom noder.
* If the noder is not provided, a suitable one will
* be used based on the supplied precision model.
*
* @param pm the precision model to use
* @param noder an optional custom noder to use (may be null)
*/
public EdgeNodingBuilder(PrecisionModel pm, Noder noder) {
this.pm = pm;
this.customNoder = noder;
}
/**
* Gets a noder appropriate for the precision model supplied.
* This is one of:
* <ul>
* <li>Fixed precision: a snap-rounding noder (which should be fully robust)
* <li>Floating precision: a conventional nodel (which may be non-robust).
* In this case, a validation step is applied to the output from the noder.
* </ul>
*
* @return
*/
private Noder getNoder() {
if (customNoder != null) return customNoder;
if (OverlayUtil.isFloating(pm))
return createFloatingPrecisionNoder(IS_NODING_VALIDATED);
return createFixedPrecisionNoder(pm);
}
public void setClipEnvelope(Envelope clipEnv) {
this.clipEnv = clipEnv;
clipper = new RingClipper(clipEnv);
limiter = new LineLimiter(clipEnv);
}
/**
* Reports whether there are noded edges
* for the given input geometry.
* If there are none, this indicates that either
* the geometry was empty, or has completely collapsed
* (because it is smaller than the noding precision).
*
* @param geomIndex index of input geometry
* @return true if there are edges for the geometry
*/
public boolean hasEdgesFor(int geomIndex ) {
return hasEdges[geomIndex];
}
/**
* Creates a set of labelled {Edge}s.
* representing the fully noded edges of the input geometries.
* Coincident edges (from the same or both geometries)
* are merged along with their labels
* into a single unique, fully labelled edge.
*
* @param geom0 the first geometry
* @param geom1 the second geometry
* @return the noded, merged, labelled edges
*/
public List<Edge> build(Geometry geom0, Geometry geom1) {
add(geom0, 0);
add(geom1, 1);
List<Edge> nodedEdges = node(inputEdges);
/**
* Merge the noded edges to eliminate duplicates.
* Labels are combined.
*/
List<Edge> mergedEdges = EdgeMerger.merge(nodedEdges);
return mergedEdges;
}
/**
* Nodes a set of segment strings and creates {@link Edge}s from the result.
* The input segment strings each carry a {@link EdgeSourceInfo} object,
* which is used to provide source topology info to the constructed Edges
* (and then is discarded).
*
* @param segStrings
* @return
*/
private List<Edge> node(List<NodedSegmentString> segStrings) {
Noder noder = getNoder();
noder.computeNodes(segStrings);
@SuppressWarnings("unchecked")
Collection<SegmentString> nodedSS = noder.getNodedSubstrings();
List<Edge> edges = createEdges(nodedSS);
return edges;
}
private List<Edge> createEdges(Collection<SegmentString> segStrings) {
List<Edge> edges = new ArrayList<Edge>();
for (SegmentString ss : segStrings) {
Coordinate[] pts = ss.getCoordinates();
//-- don't create edges from collapsed lines
if ( Edge.isCollapsed(pts) )
continue;
EdgeSourceInfo info = (EdgeSourceInfo) ss.getData();
//-- Record that a non-collapsed edge exists for the parent geometry
hasEdges[ info.getIndex() ] = true;
edges.add(new Edge(ss.getCoordinates(), info));
}
return edges;
}
private void add(Geometry g, int geomIndex)
{
if (g == null || g.isEmpty()) return;
if (isClippedCompletely(g.getEnvelopeInternal()))
return;
if (g instanceof Polygon) addPolygon((Polygon) g, geomIndex);
// LineString also handles LinearRings
else if (g instanceof LineString) addLine((LineString) g, geomIndex);
else if (g instanceof MultiLineString) addCollection((MultiLineString) g, geomIndex);
else if (g instanceof MultiPolygon) addCollection((MultiPolygon) g, geomIndex);
else if (g instanceof GeometryCollection) addGeometryCollection((GeometryCollection) g, geomIndex, g.getDimension());
// ignore Point geometries - they are handled elsewhere
}
private void addCollection(GeometryCollection gc, int geomIndex)
{
for (int i = 0; i < gc.getNumGeometries(); i++) {
Geometry g = gc.getGeometryN(i);
add(g, geomIndex);
}
}
private void addGeometryCollection(GeometryCollection gc, int geomIndex, int expectedDim)
{
for (int i = 0; i < gc.getNumGeometries(); i++) {
Geometry g = gc.getGeometryN(i);
// check for mixed-dimension input, which is not supported
if (g.getDimension() != expectedDim) {
throw new IllegalArgumentException("Overlay input is mixed-dimension");
}
add(g, geomIndex);
}
}
private void addPolygon(Polygon poly, int geomIndex)
{
LinearRing shell = poly.getExteriorRing();
addPolygonRing(shell, false, geomIndex);
for (int i = 0; i < poly.getNumInteriorRing(); i++) {
LinearRing hole = poly.getInteriorRingN(i);
// Holes are topologically labelled opposite to the shell, since
// the interior of the polygon lies on their opposite side
// (on the left, if the hole is oriented CW)
addPolygonRing(hole, true, geomIndex);
}
}
/**
* Adds a polygon ring to the graph.
* Empty rings are ignored.
*/
private void addPolygonRing(LinearRing ring, boolean isHole, int index)
{
// don't add empty rings
if (ring.isEmpty()) return;
if (isClippedCompletely(ring.getEnvelopeInternal()))
return;
Coordinate[] pts = clip( ring );
/**
* Don't add edges that collapse to a point
*/
if (pts.length < 2) {
return;
}
//if (pts.length < ring.getNumPoints()) System.out.println("Ring clipped: " + ring.getNumPoints() + " => " + pts.length);
int depthDelta = computeDepthDelta(ring, isHole);
EdgeSourceInfo info = new EdgeSourceInfo(index, depthDelta, isHole);
addEdge(pts, info);
}
/**
* Tests whether a geometry (represented by its envelope)
* lies completely outside the clip extent(if any).
*
* @param env the geometry envelope
* @return true if the geometry envelope is outside the clip extent.
*/
private boolean isClippedCompletely(Envelope env) {
if (clipEnv == null) return false;
return clipEnv.disjoint(env);
}
/**
* If a clipper is present,
* clip the line to the clip extent.
* Otherwise, remove duplicate points from the ring.
* <p>
* If clipping is enabled, then every ring MUST
* be clipped, to ensure that holes are clipped to
* be inside the shell.
* This means it is not possible to skip
* clipping for rings with few vertices.
*
* @param ring the line to clip
* @return the points in the clipped line
*/
private Coordinate[] clip(LinearRing ring) {
Coordinate[] pts = ring.getCoordinates();
Envelope env = ring.getEnvelopeInternal();
/**
* If no clipper or ring is completely contained then no need to clip.
* But repeated points must be removed to ensure correct noding.
*/
if (clipper == null || clipEnv.covers(env)) {
return removeRepeatedPoints(ring);
}
return clipper.clip(pts);
}
/**
* Removes any repeated points from a linear component.
* This is required so that noding can be computed correctly.
*
* @param line the line to process
* @return the points of the line with repeated points removed
*/
private static Coordinate[] removeRepeatedPoints(LineString line) {
Coordinate[] pts = line.getCoordinates();
return CoordinateArrays.removeRepeatedPoints(pts);
}
private static int computeDepthDelta(LinearRing ring, boolean isHole) {
/**
* Compute the orientation of the ring, to
* allow assigning side interior/exterior labels correctly.
* JTS canonical orientation is that shells are CW, holes are CCW.
*
* It is important to compute orientation on the original ring,
* since topology collapse can make the orientation computation give the wrong answer.
*/
boolean isCCW = Orientation.isCCW( ring.getCoordinateSequence() );
/**
* Compute whether ring is in canonical orientation or not.
* Canonical orientation for the overlay process is
* Shells : CW, Holes: CCW
*/
boolean isOriented = true;
if (! isHole)
isOriented = ! isCCW;
else {
isOriented = isCCW;
}
/**
* Depth delta can now be computed.
* Canonical depth delta is 1 (Exterior on L, Interior on R).
* It is flipped to -1 if the ring is oppositely oriented.
*/
int depthDelta = isOriented ? 1 : -1;
return depthDelta;
}
/**
* Adds a line geometry, limiting it if enabled,
* and otherwise removing repeated points.
*
* @param line the line to add
* @param geomIndex the index of the parent geometry
*/
private void addLine(LineString line, int geomIndex)
{
// don't add empty lines
if (line.isEmpty()) return;
if (isClippedCompletely(line.getEnvelopeInternal()))
return;
if (isToBeLimited(line)) {
List<Coordinate[]> sections = limit( line );
for (Coordinate[] pts : sections) {
addLine( pts, geomIndex );
}
}
else {
Coordinate[] ptsNoRepeat = removeRepeatedPoints(line);
addLine( ptsNoRepeat, geomIndex );
}
}
private void addLine(Coordinate[] pts, int geomIndex) {
/**
* Don't add edges that collapse to a point
*/
if (pts.length < 2) {
return;
}
EdgeSourceInfo info = new EdgeSourceInfo(geomIndex);
addEdge(pts, info);
}
private void addEdge(Coordinate[] pts, EdgeSourceInfo info) {
NodedSegmentString ss = new NodedSegmentString(pts, info);
inputEdges.add(ss);
}
/**
* Tests whether it is worth limiting a line.
* Lines that have few vertices or are covered
* by the clip extent do not need to be limited.
*
* @param line line to test
* @return true if the line should be limited
*/
private boolean isToBeLimited(LineString line) {
Coordinate[] pts = line.getCoordinates();
if (limiter == null || pts.length <= MIN_LIMIT_PTS) {
return false;
}
Envelope env = line.getEnvelopeInternal();
/**
* If line is completely contained then no need to limit
*/
if (clipEnv.covers(env)) {
return false;
}
return true;
}
/**
* If limiter is provided,
* limit the line to the clip envelope.
*
* @param line the line to clip
* @return the point sections in the clipped line
*/
private List<Coordinate[]> limit(LineString line) {
Coordinate[] pts = line.getCoordinates();
return limiter.limit(pts);
}
}