TPVWSimplifier.java

/*
 * Copyright (c) 2022 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.coverage;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.PriorityQueue;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LineString;
import org.locationtech.jts.geom.MultiLineString;
import org.locationtech.jts.index.VertexSequencePackedRtree;
import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.simplify.LinkedLine;

/**
 * Computes a Topology-Preserving Visvalingam-Whyatt simplification
 * of a set of input lines.
 * The simplified lines will contain no more intersections than are present
 * in the original input.
 * Line and ring endpoints are preserved, except for rings 
 * which are flagged as "free".
 * <p>
 * The amount of simplification is determined by a tolerance value, 
 * which is a non-zero quantity. 
 * It is the square root of the area tolerance used 
 * in the Visvalingam-Whyatt algorithm.
 * This equates roughly to the maximum
 * distance by which a simplified line can change from the original.
 * 
 * @author mdavis
 *
 */
class TPVWSimplifier {

  /**
   * Simplifies a set of lines, preserving the topology of the lines.
   * 
   * @param lines the lines to simplify
   * @param distanceTolerance the simplification tolerance
   * @return the simplified lines
   */
  public static MultiLineString simplify(MultiLineString lines, double distanceTolerance) {
    TPVWSimplifier simp = new TPVWSimplifier(lines, distanceTolerance);
    MultiLineString result = (MultiLineString) simp.simplify();
    return result;
  }
  
  /**
   * Simplifies a set of lines, preserving the topology of the lines between
   * themselves and a set of linear constraints.
   * The endpoints of lines are preserved.
   * The endpoint of rings are preserved as well, unless
   * the ring is indicated as "free" via a bit flag with the same index.
   * 
   * @param lines the lines to simplify
   * @param freeRings flags indicating which ring edges do not have node endpoints
   * @param constraintLines the linear constraints (may be null)
   * @param distanceTolerance the simplification tolerance
   * @return the simplified lines
   */
  public static MultiLineString simplify(MultiLineString lines, BitSet freeRings,
      MultiLineString constraintLines, double distanceTolerance) {
    TPVWSimplifier simp = new TPVWSimplifier(lines, distanceTolerance);
    simp.setFreeRingIndices(freeRings);
    simp.setConstraints(constraintLines);
    MultiLineString result = (MultiLineString) simp.simplify();
    return result;
  }
 
  private MultiLineString inputLines;
  private BitSet isFreeRing;
  private double areaTolerance;
  private GeometryFactory geomFactory;
  private MultiLineString constraintLines = null;

  private TPVWSimplifier(MultiLineString lines, double distanceTolerance) {
    this.inputLines = lines;
    this.areaTolerance = distanceTolerance * distanceTolerance;
    geomFactory = inputLines.getFactory();
  }
  
  private void setConstraints(MultiLineString constraints) {
    this.constraintLines = constraints;
  }

  public void setFreeRingIndices(BitSet isFreeRing) {
    //Assert: bit set has same size as number of lines.
    this.isFreeRing = isFreeRing;
  }

  private Geometry simplify() {
    List<Edge> edges = createEdges(inputLines, this.isFreeRing);
    List<Edge> constraintEdges = createEdges(constraintLines, null);

    EdgeIndex edgeIndex = new EdgeIndex();
    edgeIndex.add(edges);
    edgeIndex.add(constraintEdges);

    LineString[] result = new LineString[edges.size()];
    for (int i = 0 ; i < edges.size(); i++) {
      Edge edge = edges.get(i);
      Coordinate[] ptsSimp = edge.simplify(edgeIndex);
      result[i] = geomFactory.createLineString(ptsSimp);
    }
    return geomFactory.createMultiLineString(result);
  }

  private List<Edge> createEdges(MultiLineString lines, BitSet isFreeRing) {
    List<Edge> edges = new ArrayList<Edge>();
    if (lines == null)
      return edges;
    for (int i = 0 ; i < lines.getNumGeometries(); i++) {
      LineString line = (LineString) lines.getGeometryN(i);
      boolean isFree = isFreeRing == null ? false : isFreeRing.get(i);
      edges.add(new Edge(line, isFree, areaTolerance));
    }
    return edges;
  }
  
  private static class Edge {
    private double areaTolerance;
    private LinkedLine linkedLine;
    private int minEdgeSize;
    private boolean isFreeRing;
    private int nbPts;

    private VertexSequencePackedRtree vertexIndex;
    private Envelope envelope;

    /**
     * Creates a new edge.
     * The endpoints of the edge are preserved during simplification,
     * unless it is a ring and the {@Link #isFreeRing} flag is set.
     * 
     * @param inputLine the line or ring
     * @param isFreeRing whether a ring endpoint can be removed
     * @param areaTolerance the simplification tolerance
     */
    Edge(LineString inputLine, boolean isFreeRing, double areaTolerance) {
      this.areaTolerance = areaTolerance;
      this.isFreeRing = isFreeRing;
      this.envelope = inputLine.getEnvelopeInternal();
      Coordinate[] pts = inputLine.getCoordinates();
      this.nbPts = pts.length;
      linkedLine = new LinkedLine(pts);
      minEdgeSize = linkedLine.isRing() ? 3 : 2;
      
      vertexIndex = new VertexSequencePackedRtree(pts);
      //-- remove ring duplicate final vertex
      if (linkedLine.isRing()) {
        vertexIndex.remove(pts.length-1);
      }
    }

    private Coordinate getCoordinate(int index) {
      return linkedLine.getCoordinate(index);
    }
  
    public Envelope getEnvelope() {
      return envelope;
    }
    
    public int size() {
      return linkedLine.size();
    }
    
    private Coordinate[] simplify(EdgeIndex edgeIndex) {        
      PriorityQueue<Corner> cornerQueue = createQueue();
      while (! cornerQueue.isEmpty()
          && size() > minEdgeSize) {
        Corner corner = cornerQueue.poll();
        //-- a corner may no longer be valid due to removal of adjacent corners
        if (corner.isRemoved())
          continue;
        //System.out.println(corner.toLineString(edge));
        //-- done when all small corners are removed
        if (corner.getArea() > areaTolerance)
          break;
        if (isRemovable(corner, edgeIndex) ) {
          removeCorner(corner, cornerQueue);
        }
      }
      return linkedLine.getCoordinates();
    }

    private PriorityQueue<Corner> createQueue() {
      PriorityQueue<Corner> cornerQueue = new PriorityQueue<Corner>();
      int minIndex = (linkedLine.isRing() && isFreeRing) ? 0 : 1;
      int maxIndex = nbPts - 1;
      for (int i = minIndex; i < maxIndex; i++) {
        addCorner(i, cornerQueue);
      }
      return cornerQueue;
    }
    
    private void addCorner(int i, PriorityQueue<Corner> cornerQueue) {
      if (isFreeRing || (i != 0 && i != nbPts-1)) {
        Corner corner = new Corner(linkedLine, i);
        if (corner.getArea() <= areaTolerance) {
          cornerQueue.add(corner);
        }
      }
    }
    
    private boolean isRemovable(Corner corner, EdgeIndex edgeIndex) {
      Envelope cornerEnv = corner.envelope();
      //-- check nearby lines for violating intersections
      //-- the query also returns this line for checking
      for (Edge edge : edgeIndex.query(cornerEnv)) {
        if (hasIntersectingVertex(corner, cornerEnv, edge))
          return false;
        //-- check if corner base equals line (2-pts)
        //-- if so, don't remove corner, since that would collapse to the line
        if (edge != this && edge.size() == 2) {
          Coordinate[] linePts = edge.linkedLine.getCoordinates();
          if (corner.isBaseline(linePts[0], linePts[1]))
            return false;
        }
      }
      return true;
    }

    /**
     * Tests if any vertices in a line intersect the corner triangle.
     * Uses the vertex spatial index for efficiency.
     * 
     * @param corner the corner vertices
     * @param cornerEnv the envelope of the corner
     * @param edge the hull to test
     * @return true if there is an intersecting vertex
     */
    private boolean hasIntersectingVertex(Corner corner, Envelope cornerEnv, 
        Edge edge) {
      int[] result = edge.query(cornerEnv);
      for (int index : result) {

        Coordinate v = edge.getCoordinate(index);
        // ok if corner touches another line - should only happen at endpoints
        if (corner.isVertex(v))
            continue;
        
        //--- does corner triangle contain vertex?
        if (corner.intersects(v))
          return true;
      }
      return false;
    }

    private int[] query(Envelope cornerEnv) {
      return vertexIndex.query(cornerEnv);
    }

    /**
     * Removes a corner by removing the apex vertex from the ring.
     * Two new corners are created with apexes
     * at the other vertices of the corner
     * (if they are non-convex and thus removable).
     * 
     * @param corner the corner to remove
     * @param cornerQueue the corner queue
     */
    private void removeCorner(Corner corner, PriorityQueue<Corner> cornerQueue) {
      int index = corner.getIndex();
      int prev = linkedLine.prev(index);
      int next = linkedLine.next(index);
      linkedLine.remove(index);
      vertexIndex.remove(index);

      //-- potentially add the new corners created
      addCorner(prev, cornerQueue);
      addCorner(next, cornerQueue);
    }

    public String toString() {
      return linkedLine.toString();
    }
  }
  
  private static class EdgeIndex {

    STRtree index = new STRtree(); 
    
    public void add(List<Edge> edges) {
      for (Edge edge : edges) {
        add(edge);
      }
    }
    
    public void add(Edge edge) {
      index.insert(edge.getEnvelope(), edge);
    }
    
    public List<Edge> query(Envelope queryEnv) {
      return index.query(queryEnv);
    }
  }
  
}