path: root/src/com/google/common/geometry/S2Polyline.java

/*
 * Copyright 2006 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.geometry;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;

import java.util.Arrays;
import java.util.List;
import java.util.logging.Logger;

/**
 * An S2Polyline represents a sequence of zero or more vertices connected by
 * straight edges (geodesics). Edges of length 0 and 180 degrees are not
 * allowed, i.e. adjacent vertices should not be identical or antipodal.
 *
 */
public strictfp class S2Polyline implements S2Region {
  private static final Logger log = Logger.getLogger(S2Polyline.class.getCanonicalName());

  private int numVertices;

  private S2Point[] vertices;

  // TODO(kirilll): Get rid of debug mode. Turn it into tests.
  @VisibleForTesting
  static boolean debugMode = false;

  /**
   * Create a polyline that connects the given vertices. Empty polylines are
   * allowed. Adjacent vertices should not be identical or antipodal. All
   * vertices should be unit length.
   *
   * @param vertices
   */
  public S2Polyline(List<S2Point> vertices) {
    this.numVertices = vertices.size();
    this.vertices = new S2Point[numVertices];

    if (debugMode) {
      // assert (isValid(vertices));
    }

    if (numVertices > 0) {
      vertices.toArray(this.vertices);
    }
  }

  /**
   * Copy constructor.
   */
  public S2Polyline(S2Polyline src) {
    this.numVertices = src.numVertices();
    this.vertices = src.vertices.clone();
  }

  /**
   * Return true if the given vertices form a valid polyline.
   */
  public boolean isValid(List<S2Point> vertices) {
    // All vertices must be unit length.
    int n = vertices.size();
    for (int i = 0; i < n; ++i) {
      if (!S2.isUnitLength(vertices.get(i))) {
        log.info("Vertex " + i + " is not unit length");
        return false;
      }
    }

    // Adjacent vertices must not be identical or antipodal.
    for (int i = 1; i < n; ++i) {
      if (vertices.get(i - 1).equals(vertices.get(i))
          || vertices.get(i - 1).equals(S2Point.neg(vertices.get(i)))) {
        log.info("Vertices " + (i - 1) + " and " + i + " are identical or antipodal");
        return false;
      }
    }

    return true;
  }

  public int numVertices() {
    return numVertices;
  }

  public S2Point vertex(int k) {
    // assert (k >= 0 && k < numVertices);
    return vertices[k];
  }

  /**
   * Return the angle corresponding to the total arclength of the polyline on a
   * unit sphere.
   */
  public S1Angle getArclengthAngle() {
    double lengthSum = 0;
    for (int i = 1; i < numVertices(); ++i) {
      lengthSum += vertex(i - 1).angle(vertex(i));
    }
    return S1Angle.radians(lengthSum);
  }

  /**
   * Return the point whose distance from vertex 0 along the polyline is the
   * given fraction of the polyline's total length. Fractions less than zero or
   * greater than one are clamped. The return value is unit length. This cost of
   * this function is currently linear in the number of vertices.
   */
  public S2Point interpolate(double fraction) {
    // We intentionally let the (fraction >= 1) case fall through, since
    // we need to handle it in the loop below in any case because of
    // possible roundoff errors.
    if (fraction <= 0) {
      return vertex(0);
    }

    double lengthSum = 0;
    for (int i = 1; i < numVertices(); ++i) {
      lengthSum += vertex(i - 1).angle(vertex(i));
    }
    double target = fraction * lengthSum;
    for (int i = 1; i < numVertices(); ++i) {
      double length = vertex(i - 1).angle(vertex(i));
      if (target < length) {
        // This code interpolates with respect to arc length rather than
        // straight-line distance, and produces a unit-length result.
        double f = Math.sin(target) / Math.sin(length);
        return S2Point.add(S2Point.mul(vertex(i - 1), (Math.cos(target) - f * Math.cos(length))),
            S2Point.mul(vertex(i), f));
      }
      target -= length;
    }
    return vertex(numVertices() - 1);
  }

  // S2Region interface (see {@code S2Region} for details):

  /** Return a bounding spherical cap. */
  @Override
  public S2Cap getCapBound() {
    return getRectBound().getCapBound();
  }


  /** Return a bounding latitude-longitude rectangle. */
  @Override
  public S2LatLngRect getRectBound() {
    S2EdgeUtil.RectBounder bounder = new S2EdgeUtil.RectBounder();
    for (int i = 0; i < numVertices(); ++i) {
      bounder.addPoint(vertex(i));
    }
    return bounder.getBound();
  }

  /**
   * If this method returns true, the region completely contains the given cell.
   * Otherwise, either the region does not contain the cell or the containment
   * relationship could not be determined.
   */
  @Override
  public boolean contains(S2Cell cell) {
    throw new UnsupportedOperationException(
        "'containment' is not numerically well-defined " + "except at the polyline vertices");
  }

  /**
   * If this method returns false, the region does not intersect the given cell.
   * Otherwise, either region intersects the cell, or the intersection
   * relationship could not be determined.
   */
  @Override
  public boolean mayIntersect(S2Cell cell) {
    if (numVertices() == 0) {
      return false;
    }

    // We only need to check whether the cell contains vertex 0 for correctness,
    // but these tests are cheap compared to edge crossings so we might as well
    // check all the vertices.
    for (int i = 0; i < numVertices(); ++i) {
      if (cell.contains(vertex(i))) {
        return true;
      }
    }
    S2Point[] cellVertices = new S2Point[4];
    for (int i = 0; i < 4; ++i) {
      cellVertices[i] = cell.getVertex(i);
    }
    for (int j = 0; j < 4; ++j) {
      S2EdgeUtil.EdgeCrosser crosser =
          new S2EdgeUtil.EdgeCrosser(cellVertices[j], cellVertices[(j + 1) & 3], vertex(0));
      for (int i = 1; i < numVertices(); ++i) {
        if (crosser.robustCrossing(vertex(i)) >= 0) {
          // There is a proper crossing, or two vertices were the same.
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Given a point, returns the index of the start point of the (first) edge on
   * the polyline that is closest to the given point. The polyline must have at
   * least one vertex. Throws IllegalStateException if this is not the case.
   */
  public int getNearestEdgeIndex(S2Point point) {
    Preconditions.checkState(numVertices() > 0, "Empty polyline");

    if (numVertices() == 1) {
      // If there is only one vertex, the "edge" is trivial, and it's the only one
      return 0;
    }

    // Initial value larger than any possible distance on the unit sphere.
    S1Angle minDistance = S1Angle.radians(10);
    int minIndex = -1;

    // Find the line segment in the polyline that is closest to the point given.
    for (int i = 0; i < numVertices() - 1; ++i) {
      S1Angle distanceToSegment = S2EdgeUtil.getDistance(point, vertex(i), vertex(i + 1));
      if (distanceToSegment.lessThan(minDistance)) {
        minDistance = distanceToSegment;
        minIndex = i;
      }
    }

    return minIndex;
  }

  /**
   * Given a point p and the index of the start point of an edge of this polyline,
   * returns the point on that edge that is closest to p.
   */
  public S2Point projectToEdge(S2Point point, int index) {
    Preconditions.checkState(numVertices() > 0, "Empty polyline");
    Preconditions.checkState(numVertices() == 1 || index < numVertices() - 1, "Invalid edge index");
    if (numVertices() == 1) {
      // If there is only one vertex, it is always closest to any given point.
      return vertex(0);
    }
    return S2EdgeUtil.getClosestPoint(point, vertex(index), vertex(index + 1));
  }

  @Override
  public boolean equals(Object that) {
    if (!(that instanceof S2Polyline)) {
      return false;
    }

    S2Polyline thatPolygon = (S2Polyline) that;

    if (numVertices != thatPolygon.numVertices) {
      return false;
    }

    for (int i = 0; i < vertices.length; i++) {
      if (!vertices[i].equals(thatPolygon.vertices[i])) {
        return false;
      }
    }

    return true;
  }

  @Override
  public int hashCode() {
    return Objects.hashCode(numVertices, Arrays.deepHashCode(vertices));
  }


  // Polylines do not have a Contains(S2Point) method, because "containment"
  // is not numerically well-defined except at the polyline vertices.
}