IsSimpleOp.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.operation.valid;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.locationtech.jts.algorithm.BoundaryNodeRule;
import org.locationtech.jts.algorithm.LineIntersector;
import org.locationtech.jts.algorithm.RobustLineIntersector;
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.LineString;
import org.locationtech.jts.geom.Lineal;
import org.locationtech.jts.geom.MultiLineString;
import org.locationtech.jts.geom.MultiPoint;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.geom.Polygonal;
import org.locationtech.jts.geom.util.LinearComponentExtracter;
import org.locationtech.jts.noding.BasicSegmentString;
import org.locationtech.jts.noding.MCIndexNoder;
import org.locationtech.jts.noding.SegmentIntersector;
import org.locationtech.jts.noding.SegmentString;

/**
 * Tests whether a <code>Geometry</code> is simple as defined by the OGC SFS specification.
 * <p>
 * Simplicity is defined for each {@link Geometry} type as follows:
 * <ul>
 * <li><b>Point</b> geometries are simple.
 * <li><b>MultiPoint</b> geometries are simple if every point is unique
 * <li><b>LineString</b> geometries are simple if they do not self-intersect at interior points
 * (i.e. points other than the endpoints).
 * Closed linestrings which intersect only at their endpoints are simple
 * (i.e. valid <b>LinearRings</b>s.
 * <li><b>MultiLineString</b> geometries are simple if
 * their elements are simple and they intersect only at points
 * which are boundary points of both elements.
 * (The notion of boundary points can be user-specified - see below).
 * <li><b>Polygonal</b> geometries have no definition of simplicity.
 * The <code>isSimple</code> code checks if all polygon rings are simple.
 * (Note: this means that <tt>isSimple</tt> cannot be used to test
 * for <i>all</i> self-intersections in <tt>Polygon</tt>s.
 * In order to check if a <tt>Polygonal</tt> geometry has self-intersections,
 * use {@link Geometry#isValid()}).
 * <li><b>GeometryCollection</b> geometries are simple if all their elements are simple.
 * <li>Empty geometries are simple
 * </ul>
 * For {@link Lineal} geometries the evaluation of simplicity
 * can be customized by supplying a {@link BoundaryNodeRule}
 * to define how boundary points are determined.
 * The default is the SFS-standard {@link BoundaryNodeRule#MOD2_BOUNDARY_RULE}.
 * <p>
 * Note that under the <tt>Mod-2</tt> rule, closed <tt>LineString</tt>s (rings)
 * have no boundary.
 * This means that an intersection at the endpoints of
 * two closed LineStrings makes the geometry non-simple.
 * If it is required to test whether a set of <code>LineString</code>s touch
 * only at their endpoints, use {@link BoundaryNodeRule#ENDPOINT_BOUNDARY_RULE}.
 * For example, this can be used to validate that a collection of lines
 * form a topologically valid linear network.
 * <P>
 * By default this class finds a single non-simple location.
 * To find all non-simple locations, set {@link #setFindAllLocations(boolean)}
 * before calling {@link #isSimple()}, and retrieve the locations
 * via {@link #getNonSimpleLocations()}.
 * This can be used to find all intersection points in a linear network.
 *
 * @see BoundaryNodeRule
 * @see Geometry#isValid()
 *
 * @version 1.7
 */
public class IsSimpleOp
{
  /**
   * Tests whether a geometry is simple.
   *
   * @param geom the geometry to test
   * @return true if the geometry is simple
   */
  public static boolean isSimple(Geometry geom) {
    IsSimpleOp op = new IsSimpleOp(geom);
    return op.isSimple();
  }

  /**
   * Gets a non-simple location in a geometry, if any.
   *
   * @param geom the input geometry
   * @return a non-simple location, or null if the geometry is simple
   */
  public static Coordinate getNonSimpleLocation(Geometry geom) {
    IsSimpleOp op = new IsSimpleOp(geom);
    return op.getNonSimpleLocation();
  }

  private final Geometry inputGeom;
  private final boolean isClosedEndpointsInInterior;
  private boolean isFindAllLocations;

  private boolean isSimple = false;
  private List<Coordinate> nonSimplePts;

  /**
   * Creates a simplicity checker using the default SFS Mod-2 Boundary Node Rule
   *
   * @param geom the geometry to test
   */
  public IsSimpleOp(Geometry geom) {
    this(geom, BoundaryNodeRule.MOD2_BOUNDARY_RULE);
  }

  /**
   * Creates a simplicity checker using a given {@link BoundaryNodeRule}
   *
   * @param geom the geometry to test
   * @param boundaryNodeRule the boundary node rule to use.
   */
  public IsSimpleOp(Geometry geom, BoundaryNodeRule boundaryNodeRule)
  {
    this.inputGeom = geom;
    isClosedEndpointsInInterior = ! boundaryNodeRule.isInBoundary(2);
  }

  /**
   * Sets whether all non-simple intersection points
   * will be found.
   *
   * @param isFindAll whether to find all non-simple points
   */
  public void setFindAllLocations(boolean isFindAll) {
    this.isFindAllLocations = isFindAll;
  }

  /**
   * Tests whether the geometry is simple.
   *
   * @return true if the geometry is simple
   */
  public boolean isSimple()
  {
    compute();
    return isSimple;
  }

  /**
   * Gets the coordinate for an location where the geometry
   * fails to be simple.
   * (i.e. where it has a non-boundary self-intersection).
   *
   * @return a coordinate for the location of the non-boundary self-intersection
   * or null if the geometry is simple
   */
  public Coordinate getNonSimpleLocation()
  {
    compute();
    if (nonSimplePts.size() == 0) return null;
    return nonSimplePts.get(0);
  }

  /**
   * Gets all non-simple intersection locations.
   *
   * @return a list of the coordinates of non-simple locations
   */
  public List<Coordinate> getNonSimpleLocations()
  {
    compute();
    return nonSimplePts;
  }

  private void compute() {
    if (nonSimplePts != null) return;
    nonSimplePts = new ArrayList<Coordinate>();
    isSimple = computeSimple(inputGeom);
  }

  private boolean computeSimple(Geometry geom)
  {
    if (geom.isEmpty()) return true;
    if (geom instanceof Point) return true;
    if (geom instanceof LineString) return isSimpleLinearGeometry(geom);
    if (geom instanceof MultiLineString) return isSimpleLinearGeometry(geom);
    if (geom instanceof MultiPoint) return isSimpleMultiPoint((MultiPoint) geom);
    if (geom instanceof Polygonal) return isSimplePolygonal(geom);
    if (geom instanceof GeometryCollection) return isSimpleGeometryCollection(geom);
    // all other geometry types are simple by definition
    return true;
  }

  private boolean isSimpleMultiPoint(MultiPoint mp)
  {
    if (mp.isEmpty()) return true;
    boolean isSimple = true;
    Set<Coordinate> points = new HashSet<Coordinate>();
    for (int i = 0; i < mp.getNumGeometries(); i++) {
      Point pt = (Point) mp.getGeometryN(i);
      Coordinate p = pt.getCoordinate();
      if (points.contains(p)) {
        nonSimplePts.add(p);
        isSimple = false;
        if (!isFindAllLocations)
          break;
      }
      else
        points.add(p);
    }
    return isSimple;
  }

  /**
   * Computes simplicity for polygonal geometries.
   * Polygonal geometries are simple if and only if
   * all of their component rings are simple.
   *
   * @param geom a Polygonal geometry
   * @return true if the geometry is simple
   */
  private boolean isSimplePolygonal(Geometry geom)
  {
    boolean isSimple = true;
    List<Geometry> rings = LinearComponentExtracter.getLines(geom);
    for (Geometry ring : rings) {
      if (! isSimpleLinearGeometry(ring))
      {
        isSimple = false;
        if (!isFindAllLocations)
          break;
      }
    }
    return isSimple;
  }

  /**
   * Semantics for GeometryCollection is
   * simple iff all components are simple.
   *
   * @param geom a geometry collection
   * @return true if the geometry is simple
   */
  private boolean isSimpleGeometryCollection(Geometry geom)
  {
    boolean isSimple = true;
    for (int i = 0; i < geom.getNumGeometries(); i++ ) {
      Geometry comp = geom.getGeometryN(i);
      if (! computeSimple(comp))
      {
        isSimple = false;
        if (!isFindAllLocations)
          break;
      }
    }
    return isSimple;
  }

  private boolean isSimpleLinearGeometry(Geometry geom)
  {
    if (geom.isEmpty()) return true;
    List<SegmentString> segStrings = extractSegmentStrings(geom);
    NonSimpleIntersectionFinder segInt = new NonSimpleIntersectionFinder(isClosedEndpointsInInterior, isFindAllLocations, nonSimplePts);
    MCIndexNoder noder = new MCIndexNoder();
    noder.setSegmentIntersector(segInt);
    noder.computeNodes(segStrings);
    if (segInt.hasIntersection()) {
      return false;
    }
    return true;
  }

  private static List<SegmentString> extractSegmentStrings(Geometry geom) {
    List<SegmentString> segStrings = new ArrayList<SegmentString>();
    for (int i = 0; i < geom.getNumGeometries(); i++) {
      LineString line = (LineString) geom.getGeometryN(i);
      Coordinate[] trimPts = trimRepeatedPoints(line.getCoordinates());
      if (trimPts != null) {
        SegmentString ss = new BasicSegmentString(trimPts, null);
        segStrings.add(ss);
      }
    }
    return segStrings;
  }

  private static Coordinate[] trimRepeatedPoints(Coordinate[] pts) {
    if (pts.length <= 2)
      return pts;
    
    int len = pts.length;
    boolean hasRepeatedStart = pts[0].equals2D(pts[1]);
    boolean hasRepeatedEnd = pts[len - 1].equals2D(pts[len - 2]);
    if (! hasRepeatedStart && ! hasRepeatedEnd)
      return pts;
    
    //-- trim ends
    int startIndex = 0;
    Coordinate startPt = pts[0];
    while (startIndex < len - 1 && startPt.equals2D(pts[startIndex+1])) {
      startIndex++;
    }
    int endIndex = len-1;
    Coordinate endPt = pts[endIndex];
    while (endIndex > 0 && endPt.equals2D(pts[endIndex - 1])) {
      endIndex--;
    }
    //-- are all points identical?
    if (endIndex - startIndex < 1) {
      return null;
    }
    Coordinate[] trimPts = CoordinateArrays.extract(pts, startIndex, endIndex);
    return trimPts;
  }
  
  private static class NonSimpleIntersectionFinder
  implements SegmentIntersector
  {
    private final boolean isClosedEndpointsInInterior;
    private final boolean isFindAll;

    LineIntersector li = new RobustLineIntersector();
    private final List<Coordinate> intersectionPts;

    public NonSimpleIntersectionFinder(boolean isClosedEndpointsInInterior, boolean isFindAll, List<Coordinate> intersectionPts) {
      this.isClosedEndpointsInInterior =isClosedEndpointsInInterior;
      this.isFindAll = isFindAll;
      this.intersectionPts = intersectionPts;
    }

    /**
     * Tests whether an intersection was found.
     *
     * @return true if an intersection was found
     */
    public boolean hasIntersection()
    {
      return intersectionPts.size() > 0;
    }

    @Override
    public void processIntersections(SegmentString ss0, int segIndex0, SegmentString ss1, int segIndex1) {

      // don't test a segment with itself
      boolean isSameSegString = ss0 == ss1;
      boolean isSameSegment = isSameSegString && segIndex0 == segIndex1;
      if (isSameSegment) return;

      boolean hasInt = findIntersection(ss0, segIndex0, ss1, segIndex1);

      if (hasInt) {
        // found an intersection!
        intersectionPts.add(li.getIntersection(0));
      }
    }

    private boolean findIntersection(SegmentString ss0, int segIndex0,
        SegmentString ss1, int segIndex1) {

      Coordinate p00 = ss0.getCoordinate(segIndex0);
      Coordinate p01 = ss0.getCoordinate(segIndex0 + 1);
      Coordinate p10 = ss1.getCoordinate(segIndex1);
      Coordinate p11 = ss1.getCoordinate(segIndex1 + 1);

      li.computeIntersection(p00, p01, p10, p11);
      if (! li.hasIntersection()) return false;

      /**
       * Check for an intersection in the interior of a segment.
       */
      boolean hasInteriorInt = li.isInteriorIntersection();
      if (hasInteriorInt) return true;

      /**
       * Check for equal segments (which will produce two intersection points).
       * These also intersect in interior points, so are non-simple.
       * (This is not triggered by zero-length segments, since they
       * are filtered out by the MC index).
       */
      boolean hasEqualSegments = li.getIntersectionNum() >= 2;
      if (hasEqualSegments) return true;

      /**
       * Following tests assume non-adjacent segments.
       */
      boolean isSameSegString = ss0 == ss1;
      boolean isAdjacentSegment = isSameSegString && Math.abs(segIndex1 - segIndex0) <= 1;
      if (isAdjacentSegment) return false;

      /**
       * At this point there is a single intersection point
       * which is a vertex in each segString.
       * Classify them as endpoints or interior
       */
      boolean isIntersectionEndpt0 = isIntersectionEndpoint(ss0, segIndex0, li, 0);
      boolean isIntersectionEndpt1 = isIntersectionEndpoint(ss1, segIndex1, li, 1);

      boolean hasInteriorVertexInt = ! (isIntersectionEndpt0 && isIntersectionEndpt1);
      if (hasInteriorVertexInt) return true;

      /**
       * Both intersection vertices must be endpoints.
       * Final check is if one or both of them is interior due
       * to being endpoint of a closed ring.
       * This only applies to different lines
       * (which avoids reporting ring endpoints).
       */
      if (isClosedEndpointsInInterior && !isSameSegString) {
        boolean hasInteriorEndpointInt = ss0.isClosed() || ss1.isClosed();
        if (hasInteriorEndpointInt) return true;
      }
      return false;
    }

    /**
     * Tests whether an intersection vertex is an endpoint of a segment string.
     *
     * @param ss the segmentString
     * @param ssIndex index of segment in segmentString
     * @param li the line intersector
     * @param liSegmentIndex index of segment in intersector
     * @return true if the intersection vertex is an endpoint
     */
    private static boolean isIntersectionEndpoint(SegmentString ss, int ssIndex,
        LineIntersector li, int liSegmentIndex) {
      int vertexIndex = intersectionVertexIndex(li, liSegmentIndex);
      /**
       * If the vertex is the first one of the segment, check if it is the start endpoint.
       * Otherwise check if it is the end endpoint.
       */
      if (vertexIndex == 0) {
        return ssIndex == 0;
      }
      else {
        return ssIndex + 2 == ss.size();
      }
    }

    /**
     * Finds the vertex index in a segment of an intersection
     * which is known to be a vertex.
     *
     * @param li the line intersector
     * @param segmentIndex the intersection segment index
     * @return the vertex index (0 or 1) in the segment vertex of the intersection point
     */
    private static int intersectionVertexIndex(LineIntersector li, int segmentIndex) {
      Coordinate intPt = li.getIntersection(0);
      Coordinate endPt0 = li.getEndpoint(segmentIndex, 0);
      return intPt.equals2D(endPt0) ? 0 : 1;
    }

    @Override
    public boolean isDone() {
      if (isFindAll) return false;
      return intersectionPts.size() > 0;
    }

  }

}