FacetSequence.java

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

import org.locationtech.jts.algorithm.Distance;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.CoordinateSequence;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.LineSegment;

/**
 * Represents a sequence of facets (points or line segments)
 * of a {@link Geometry}
 * specified by a subsequence of a {@link CoordinateSequence}.
 * 
 * @author Martin Davis
 *
 */
public class FacetSequence
{
  private Geometry geom = null;
  private CoordinateSequence pts;
  private int start;
  private int end;
  
  /**
   * Creates a new sequence of facets based on a {@link CoordinateSequence}
   * contained in the given {@link Geometry}.
   * 
   * @param geom the geometry containing the facets 
   * @param pts the sequence containing the facet points
   * @param start the index of the start point
   * @param end the index of the end point + 1
   */
  public FacetSequence(Geometry geom, CoordinateSequence pts, int start, int end) 
  {
    this.geom = geom;
    this.pts = pts;
    this.start = start;
    this.end = end;
  } 
  
  /**
   * Creates a new sequence of facets based on a {@link CoordinateSequence}.
   * 
   * @param pts the sequence containing the facet points
   * @param start the index of the start point
   * @param end the index of the end point + 1
   */
  public FacetSequence(CoordinateSequence pts, int start, int end) 
  {
    this.pts = pts;
    this.start = start;
    this.end = end;
  }
  
  /**
   * Creates a new sequence for a single point from a {@link CoordinateSequence}.
   * 
   * @param pts the sequence containing the facet point
   * @param start the index of the point
   */
  public FacetSequence(CoordinateSequence pts, int start) 
  {
    this.pts = pts;
    this.start = start;
    this.end = start + 1;
  }
  
  public Envelope getEnvelope()
  {
    Envelope env = new Envelope();
    for (int i = start; i < end; i++) {
      env.expandToInclude(pts.getX(i), pts.getY(i));
    }
    return env;
  }
  
  public int size()
  {
    return end - start;
  }
  
  public Coordinate getCoordinate(int index)
  {
    return pts.getCoordinate(start + index);
  }
  
  public boolean isPoint()
  {
    return end - start == 1;
  }
  
  /**
   * Computes the distance between this and another
   * <tt>FacetSequence</tt>.
   * 
   * @param facetSeq the sequence to compute the distance to
   * @return the minimum distance between the sequences
   */
  public double distance(FacetSequence facetSeq)
  {
    boolean isPoint = isPoint();
    boolean isPointOther = facetSeq.isPoint();
    double distance;
    
    if (isPoint && isPointOther) {
      Coordinate pt = pts.getCoordinate(start);
      Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
      distance = pt.distance(seqPt);
    }
    else if (isPoint) {
      Coordinate pt = pts.getCoordinate(start);      
      distance = computeDistancePointLine(pt, facetSeq, null);
    }
    else if (isPointOther) {
      Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
      distance = computeDistancePointLine(seqPt, this, null);
    }
    else {
      distance = computeDistanceLineLine(facetSeq, null);
    }
    return distance;
  }
  
  /**
   * Computes the locations of the nearest points between this sequence
   * and another sequence.
   * The locations are presented in the same order as the input sequences.
   *
   * @return a pair of {@link GeometryLocation}s for the nearest points
   */
  public GeometryLocation[] nearestLocations(FacetSequence facetSeq)
  {
    boolean isPoint = isPoint();
    boolean isPointOther = facetSeq.isPoint();
    GeometryLocation[] locs = new GeometryLocation[2];
    
    if (isPoint && isPointOther) {
      Coordinate pt = pts.getCoordinate(start);
      Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
      locs[0] = new  GeometryLocation(geom, start, new Coordinate(pt));
      locs[1] = new  GeometryLocation(facetSeq.geom, facetSeq.start, new Coordinate(seqPt));
    }
    else if (isPoint) {
      Coordinate pt = pts.getCoordinate(start);      
      computeDistancePointLine(pt, facetSeq, locs);
    }
    else if (isPointOther) {
      Coordinate seqPt = facetSeq.pts.getCoordinate(facetSeq.start);
      computeDistancePointLine(seqPt, this, locs);
      // unflip the locations
      GeometryLocation tmp = locs[0];
      locs[0] = locs[1];
      locs[1] = tmp;
    }
    else {
      computeDistanceLineLine(facetSeq, locs);
    }
    return locs;    
  }

  private double computeDistanceLineLine(FacetSequence facetSeq, GeometryLocation[] locs)
  {
    // both linear - compute minimum segment-segment distance
    double minDistance = Double.MAX_VALUE;

    for (int i = start; i < end - 1; i++) {
      Coordinate p0 = pts.getCoordinate(i);
      Coordinate p1 = pts.getCoordinate(i + 1);
      for (int j = facetSeq.start; j < facetSeq.end - 1; j++) {
        Coordinate q0 = facetSeq.pts.getCoordinate(j);
        Coordinate q1 = facetSeq.pts.getCoordinate(j + 1);
        
        double dist = Distance.segmentToSegment(p0, p1, q0, q1);
        if (dist < minDistance) {
          minDistance = dist;
          if (locs != null) updateNearestLocationsLineLine(i, p0, p1, facetSeq, j, q0, q1, locs);
          if (minDistance <= 0.0) return minDistance;
        }
      }
    }
    return minDistance;
  }

  private void updateNearestLocationsLineLine(int i, Coordinate p0, Coordinate p1, FacetSequence facetSeq, int j,
      Coordinate q0, Coordinate q1, GeometryLocation[] locs) {
    LineSegment seg0 = new LineSegment(p0, p1);
    LineSegment seg1 = new LineSegment(q0, q1);
    Coordinate[] closestPt = seg0.closestPoints(seg1);
    locs[0] = new GeometryLocation(geom, i, new Coordinate(closestPt[0]));
    locs[1] = new GeometryLocation(facetSeq.geom, j, new Coordinate(closestPt[1]));    
  }
  
  private double computeDistancePointLine(Coordinate pt, FacetSequence facetSeq, GeometryLocation[] locs) 
  {
    double minDistance = Double.MAX_VALUE;

    for (int i = facetSeq.start; i < facetSeq.end - 1; i++) {
      Coordinate q0 = facetSeq.pts.getCoordinate(i);
      Coordinate q1 = facetSeq.pts.getCoordinate(i + 1);
      double dist = Distance.pointToSegment(pt, q0, q1);
      if (dist < minDistance) {
        minDistance = dist;
        if (locs != null) updateNearestLocationsPointLine(pt, facetSeq, i, q0, q1, locs);
        if (minDistance <= 0.0) return minDistance;
      }
    }
    return minDistance;
  }
  
  private void updateNearestLocationsPointLine(Coordinate pt, 
      FacetSequence facetSeq, int i, Coordinate q0, Coordinate q1, 
      GeometryLocation[] locs) {
    locs[0] = new GeometryLocation(geom, start, new Coordinate(pt));
    LineSegment seg = new LineSegment(q0, q1);
    Coordinate segClosestPoint = seg.closestPoint(pt);
    locs[1] = new  GeometryLocation(facetSeq.geom, i, new Coordinate(segClosestPoint));
  }

  public String toString()
  {
    StringBuffer buf = new StringBuffer();
    buf.append("LINESTRING ( ");
    Coordinate p = new Coordinate();
    for (int i = start; i < end; i++) {
      if (i > start)
        buf.append(", ");
      pts.getCoordinate(i, p);
      buf.append(p.x + " " + p.y);
    }
    buf.append(" )");
    return buf.toString();
  }
}