path: root/src/com/google/common/geometry/S2Polygon.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.base.Preconditions;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multiset;
import com.google.common.collect.TreeMultimap;
import com.google.common.collect.TreeMultiset;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Logger;

/**
 * An S2Polygon is an S2Region object that represents a polygon. A polygon
 * consists of zero or more {@link S2Loop loops} representing "shells" and
 * "holes". All loops should be oriented CCW, i.e. the shell or hole is on the
 * left side of the loop. Loops may be specified in any order. A point is
 * defined to be inside the polygon if it is contained by an odd number of
 * loops.
 *
 *  Polygons have the following restrictions:
 *
 *  - Loops may not cross, i.e. the boundary of a loop may not intersect both
 * the interior and exterior of any other loop.
 *
 *  - Loops may not share edges, i.e. if a loop contains an edge AB, then no
 * other loop may contain AB or BA.
 *
 *  - No loop may cover more than half the area of the sphere. This ensures that
 * no loop properly contains the complement of any other loop, even if the loops
 * are from different polygons. (Loops that represent exact hemispheres are
 * allowed.)
 *
 *  Loops may share vertices, however no vertex may appear twice in a single
 * loop.
 *
 */
public final strictfp class S2Polygon implements S2Region, Comparable<S2Polygon> {
  private static final Logger log = Logger.getLogger(S2Polygon.class.getCanonicalName());

  private List<S2Loop> loops;

  private S2LatLngRect bound;
  private boolean hasHoles;
  private int numVertices;

  /**
   * Creates an empty polygon that should be initialized by calling Init().
   */
  public S2Polygon() {
    this.loops = Lists.newArrayList();
    this.bound = S2LatLngRect.empty();
    this.hasHoles = false;
    this.numVertices = 0;
  }

  /**
   * Convenience constructor that calls Init() with the given loops. Clears the
   * given list.
   */
  public S2Polygon(List<S2Loop> loops) {
    this.loops = Lists.newArrayList();
    this.bound = S2LatLngRect.empty();

    init(loops);
  }

  /**
   * Copy constructor.
   */
  public S2Polygon(S2Loop loop) {
    this.loops = Lists.newArrayList();
    this.bound = loop.getRectBound();
    this.hasHoles = false;
    this.numVertices = loop.numVertices();

    loops.add(loop);
  }

  /**
   * Copy constructor.
   */
  public S2Polygon(S2Polygon src) {
    this.loops = Lists.newArrayList();
    this.bound = src.getRectBound();
    this.hasHoles = src.hasHoles;
    this.numVertices = src.numVertices;

    for (int i = 0; i < src.numLoops(); ++i) {
      loops.add(new S2Loop(src.loop(i)));
    }
  }

  /**
   * Comparator (needed by Comparable interface). For two polygons to be
   * compared as equal: - the must have the same number of loops; - the loops
   * must be ordered in the same way (this is guaranteed by the total ordering
   * imposed by sortValueLoops). - loops must be logically equivalent (even if
   * ordered with a different starting point, e.g. ABCD and BCDA).
   */
  @Override
  public int compareTo(S2Polygon other) {
    // If number of loops differ, use that.
    if (this.numLoops() != other.numLoops()) {
      return this.numLoops() - other.numLoops();
    }
    for (int i = 0; i < this.numLoops(); ++i) {
      int compare = this.loops.get(i).compareTo(other.loops.get(i));
      if (compare != 0) {
        return compare;
      }
    }
    return 0;
  }

  /**
   * Initialize a polygon by taking ownership of the given loops and clearing
   * the given list. This method figures out the loop nesting hierarchy and then
   * reorders the loops by following a preorder traversal. This implies that
   * each loop is immediately followed by its descendants in the nesting
   * hierarchy. (See also getParent and getLastDescendant.)
   */
  public void init(List<S2Loop> loops) {
    // assert isValid(loops);
    // assert (this.loops.isEmpty());

    Map<S2Loop, List<S2Loop>> loopMap = Maps.newHashMap();
    // Yes, a null key is valid. It is used here to refer to the root of the
    // loopMap
    loopMap.put(null, Lists.<S2Loop>newArrayList());

    for (S2Loop loop : loops) {
      insertLoop(loop, null, loopMap);
      this.numVertices += loop.numVertices();
    }
    loops.clear();

    // Sort all of the lists of loops; in this way we guarantee a total ordering
    // on loops in the polygon. Loops will be sorted by their natural ordering,
    // while also preserving the requirement that each loop is immediately
    // followed by its descendants in the nesting hierarchy.
    //
    // TODO(andriy): as per kirilll in CL 18750833 code review comments:
    // This should work for now, but I think it's possible to guarantee the
    // correct order inside insertLoop by searching for the correct position in
    // the children list before inserting.
    sortValueLoops(loopMap);

    // Reorder the loops in depth-first traversal order.
    // Starting at null == starting at the root
    initLoop(null, -1, loopMap);

    // TODO(dbeaumont): Add tests or preconditions for these asserts (here and elesewhere).
    // forall i != j : containsChild(loop(i), loop(j), loopMap) == loop(i).containsNested(loop(j)));

    // Compute the bounding rectangle of the entire polygon.
    hasHoles = false;
    bound = S2LatLngRect.empty();
    for (int i = 0; i < numLoops(); ++i) {
      if (loop(i).sign() < 0) {
        hasHoles = true;
      } else {
        bound = bound.union(loop(i).getRectBound());
      }
    }
  }

  /**
   * Release ownership of the loops of this polygon by appending them to the
   * given list. Resets the polygon to be empty.
   */
  public void release(List<S2Loop> loops) {
    loops.addAll(this.loops);
    this.loops.clear();
    bound = S2LatLngRect.empty();
    hasHoles = false;
    numVertices = 0;
  }

  /**
   * Return true if the given loops form a valid polygon. Assumes that that all
   * of the given loops have already been validated.
   */
  public static boolean isValid(final List<S2Loop> loops) {
    // If a loop contains an edge AB, then no other loop may contain AB or BA.
    // We only need this test if there are at least two loops, assuming that
    // each loop has already been validated.
    if (loops.size() > 1) {
      Map<UndirectedEdge, LoopVertexIndexPair> edges = Maps.newHashMap();
      for (int i = 0; i < loops.size(); ++i) {
        S2Loop lp = loops.get(i);
        for (int j = 0; j < lp.numVertices(); ++j) {
          UndirectedEdge key = new UndirectedEdge(lp.vertex(j), lp.vertex(j + 1));
          LoopVertexIndexPair value = new LoopVertexIndexPair(i, j);
          if (edges.containsKey(key)) {
            LoopVertexIndexPair other = edges.get(key);
            log.info(
                "Duplicate edge: loop " + i + ", edge " + j + " and loop " + other.getLoopIndex()
                    + ", edge " + other.getVertexIndex());
            return false;
          } else {
            edges.put(key, value);
          }
        }
      }
    }

    // Verify that no loop covers more than half of the sphere, and that no
    // two loops cross.
    for (int i = 0; i < loops.size(); ++i) {
      if (!loops.get(i).isNormalized()) {
        log.info("Loop " + i + " encloses more than half the sphere");
        return false;
      }
      for (int j = i + 1; j < loops.size(); ++j) {
        // This test not only checks for edge crossings, it also detects
        // cases where the two boundaries cross at a shared vertex.
        if (loops.get(i).containsOrCrosses(loops.get(j)) < 0) {
          log.info("Loop " + i + " crosses loop " + j);
          return false;
        }
      }
    }
    return true;
  }

  public int numLoops() {
    return loops.size();
  }

  public S2Loop loop(int k) {
    return loops.get(k);
  }

  /**
   * Return the index of the parent of loop k, or -1 if it has no parent.
   */
  public int getParent(int k) {
    int depth = loop(k).depth();
    if (depth == 0) {
      return -1; // Optimization.
    }
    while (--k >= 0 && loop(k).depth() >= depth) {
      // spin
    }
    return k;
  }

  /**
   * Return the index of the last loop that is contained within loop k. Returns
   * num_loops() - 1 if k < 0. Note that loops are indexed according to a
   * preorder traversal of the nesting hierarchy, so the immediate children of
   * loop k can be found by iterating over loops (k+1)..getLastDescendant(k) and
   * selecting those whose depth is equal to (loop(k).depth() + 1).
   */
  public int getLastDescendant(int k) {
    if (k < 0) {
      return numLoops() - 1;
    }
    int depth = loop(k).depth();
    while (++k < numLoops() && loop(k).depth() > depth) {
      // spin
    }
    return k - 1;
  }

  private S2AreaCentroid getAreaCentroid(boolean doCentroid) {
    double areaSum = 0;
    S2Point centroidSum = new S2Point(0, 0, 0);
    for (int i = 0; i < numLoops(); ++i) {
      S2AreaCentroid areaCentroid = doCentroid ? loop(i).getAreaAndCentroid() : null;
      double loopArea = doCentroid ? areaCentroid.getArea() : loop(i).getArea();

      int loopSign = loop(i).sign();
      areaSum += loopSign * loopArea;
      if (doCentroid) {
        S2Point currentCentroid = areaCentroid.getCentroid();
        centroidSum =
            new S2Point(centroidSum.x + loopSign * currentCentroid.x,
                centroidSum.y + loopSign * currentCentroid.y,
                centroidSum.z + loopSign * currentCentroid.z);
      }
    }

    return new S2AreaCentroid(areaSum, doCentroid ? centroidSum : null);
  }

  /**
   * Return the area of the polygon interior, i.e. the region on the left side
   * of an odd number of loops (this value return value is between 0 and 4*Pi)
   * and the true centroid of the polygon multiplied by the area of the polygon
   * (see s2.h for details on centroids). Note that the centroid may not be
   * contained by the polygon.
   */
  public S2AreaCentroid getAreaAndCentroid() {
    return getAreaCentroid(true);
  }

  /**
   * Return the area of the polygon interior, i.e. the region on the left side
   * of an odd number of loops. The return value is between 0 and 4*Pi.
   */
  public double getArea() {
    return getAreaCentroid(false).getArea();
  }

  /**
   * Return the true centroid of the polygon multiplied by the area of the
   * polygon (see s2.h for details on centroids). Note that the centroid may not
   * be contained by the polygon.
   */
  public S2Point getCentroid() {
    return getAreaCentroid(true).getCentroid();
  }

  /**
   * Returns the shortest distance from a point P to this polygon, given as the
   * angle formed between P, the origin and the nearest point on the polygon to
   * P. This angle in radians is equivalent to the arclength along the unit
   * sphere.
   *
   * If the point is contained inside the polygon, the distance returned is 0.
   */
  public S1Angle getDistance(S2Point p) {
    if (contains(p)) {
      return S1Angle.radians(0);
    }

    // The furthest point from p on the sphere is its antipode, which is an
    // angle of PI radians. This is an upper bound on the angle.
    S1Angle minDistance = S1Angle.radians(Math.PI);
    for (int i = 0; i < numLoops(); i++) {
      minDistance = S1Angle.min(minDistance, loop(i).getDistance(p));
    }

    return minDistance;
  }


  /**
   * Return true if this polygon contains the given other polygon, i.e. if
   * polygon A contains all points contained by polygon B.
   */
  public boolean contains(S2Polygon b) {
    // If both polygons have one loop, use the more efficient S2Loop method.
    // Note that S2Loop.contains does its own bounding rectangle check.
    if (numLoops() == 1 && b.numLoops() == 1) {
      return loop(0).contains(b.loop(0));
    }

    // Otherwise if neither polygon has holes, we can still use the more
    // efficient S2Loop::Contains method (rather than ContainsOrCrosses),
    // but it's worthwhile to do our own bounds check first.
    if (!bound.contains(b.getRectBound())) {
      // If the union of the bounding boxes spans the full longitude range,
      // it is still possible that polygon A contains B. (This is only
      // possible if at least one polygon has multiple shells.)
      if (!bound.lng().union(b.getRectBound().lng()).isFull()) {
        return false;
      }
    }
    if (!hasHoles && !b.hasHoles) {
      for (int j = 0; j < b.numLoops(); ++j) {
        if (!anyLoopContains(b.loop(j))) {
          return false;
        }
      }
      return true;
    }

    // This could be implemented more efficiently for polygons with lots of
    // holes by keeping a copy of the LoopMap computed during initialization.
    // However, in practice most polygons are one loop, and multiloop polygons
    // tend to consist of many shells rather than holes. In any case, the real
    // way to get more efficiency is to implement a sub-quadratic algorithm
    // such as building a trapezoidal map.

    // Every shell of B must be contained by an odd number of loops of A,
    // and every hole of A must be contained by an even number of loops of B.
    return containsAllShells(b) && b.excludesAllHoles(this);
  }

  /**
   * Return true if this polygon intersects the given other polygon, i.e. if
   * there is a point that is contained by both polygons.
   */
  public boolean intersects(S2Polygon b) {
    // A.intersects(B) if and only if !complement(A).contains(B). However,
    // implementing a complement() operation is trickier than it sounds,
    // and in any case it's more efficient to test for intersection directly.

    // If both polygons have one loop, use the more efficient S2Loop method.
    // Note that S2Loop.intersects does its own bounding rectangle check.
    if (numLoops() == 1 && b.numLoops() == 1) {
      return loop(0).intersects(b.loop(0));
    }

    // Otherwise if neither polygon has holes, we can still use the more
    // efficient S2Loop.intersects method. The polygons intersect if and
    // only if some pair of loop regions intersect.
    if (!bound.intersects(b.getRectBound())) {
      return false;
    }
    if (!hasHoles && !b.hasHoles) {
      for (int i = 0; i < numLoops(); ++i) {
        for (int j = 0; j < b.numLoops(); ++j) {
          if (loop(i).intersects(b.loop(j))) {
            return true;
          }
        }
      }
      return false;
    }

    // Otherwise if any shell of B is contained by an odd number of loops of A,
    // or any shell of A is contained by an odd number of loops of B, there is
    // an intersection.
    return intersectsAnyShell(b) || b.intersectsAnyShell(this);
  }

  /**
   * Indexing structure to efficiently clipEdge() of a polygon. This is an
   * abstract class because we need to use if for both polygons (for
   * initToIntersection() and friends) and for sets of lists of points (for
   * initToSimplified()).
   *
   *  Usage -- in your subclass: - Call addLoop() for each of your loops -- and
   * keep them accessible in your subclass. - Overwrite edgeFromTo(), calling
   * decodeIndex() and accessing your underlying data with the resulting two
   * indices.
   */
  private abstract static class S2LoopSequenceIndex extends S2EdgeIndex {
    public S2LoopSequenceIndex() {
      numEdges = 0;
      numLoops = 0;
      indexToLoop = Lists.newArrayList();
      loopToFirstIndex = Lists.newArrayList();
    }

    public void addLoop(int numVertices) {
      int verticesSoFar = numEdges;
      loopToFirstIndex.add(verticesSoFar);
      indexToLoop.ensureCapacity(verticesSoFar + numVertices);
      for (int i = 0; i < numVertices; ++i) {
        indexToLoop.add(verticesSoFar, numLoops);
        ++verticesSoFar;
      }
      numEdges += numVertices;
      ++numLoops;
    }

    public LoopVertexIndexPair decodeIndex(int index) {
      int loopIndex = indexToLoop.get(index);
      int vertexInLoop = index - loopToFirstIndex.get(loopIndex);
      return new LoopVertexIndexPair(loopIndex, vertexInLoop);
    }

    // It is faster to return both vertices at once. It makes a difference
    // for small polygons.
    public abstract S2Edge edgeFromTo(int index);

    @Override
    protected int getNumEdges() {
      return numEdges;
    }

    @Override
    public S2Point edgeFrom(int index) {
      S2Edge fromTo = edgeFromTo(index);
      S2Point from = fromTo.getStart();
      return from;
    }

    @Override
    protected S2Point edgeTo(int index) {
      S2Edge fromTo = edgeFromTo(index);
      S2Point to = fromTo.getEnd();
      return to;
    }

    // Map from the unidimensional edge index to the loop this edge belongs to.
    ArrayList<Integer> indexToLoop;
    // Reverse of index_to_loop_: maps a loop index to the
    // unidimensional index of the first edge in the loop.
    List<Integer> loopToFirstIndex;

    // Total number of edges.
    int numEdges;

    // Total number of loops.
    int numLoops;
  }

  // Indexing structure for an S2Polygon.
  static class S2PolygonIndex extends S2LoopSequenceIndex {
    private S2Polygon poly;
    private boolean reverse;

    public S2PolygonIndex(S2Polygon poly, boolean reverse) {
      this.poly = poly;
      this.reverse = reverse;
      for (int i = 0; i < poly.numLoops(); ++i) {
        addLoop(poly.loop(i).numVertices());
      }
    }

    @Override
    public S2Edge edgeFromTo(int index) {
      int loopIndex = 0;
      int vertexInLoop = 0;
      LoopVertexIndexPair indices = decodeIndex(index);
      loopIndex = indices.getLoopIndex();
      vertexInLoop = indices.getVertexIndex();
      S2Loop loop = new S2Loop(poly.loop(loopIndex));
      int fromIndex;
      int toIndex;
      if (loop.isHole() ^ reverse) {
        fromIndex = loop.numVertices() - 1 - vertexInLoop;
        toIndex = 2 * loop.numVertices() - 2 - vertexInLoop;
      } else {
        fromIndex = vertexInLoop;
        toIndex = vertexInLoop + 1;
      }
      S2Point from = loop.vertex(fromIndex);
      S2Point to = loop.vertex(toIndex);
      return new S2Edge(from, to);
    }
  }

  private static void addIntersection(S2Point a0,
      S2Point a1,
      S2Point b0,
      S2Point b1,
      boolean addSharedEdges,
      int crossing,
      List<ParametrizedS2Point> intersections) {
    if (crossing > 0) {
      // There is a proper edge crossing.
      S2Point x = S2EdgeUtil.getIntersection(a0, a1, b0, b1);
      double t = S2EdgeUtil.getDistanceFraction(x, a0, a1);
      intersections.add(new ParametrizedS2Point(t, x));
    } else if (S2EdgeUtil.vertexCrossing(a0, a1, b0, b1)) {
      // There is a crossing at one of the vertices. The basic rule is simple:
      // if a0 equals one of the "b" vertices, the crossing occurs at t=0;
      // otherwise, it occurs at t=1.
      //
      // This has the effect that when two symmetric edges are encountered (an
      // edge an its reverse), neither one is included in the output. When two
      // duplicate edges are encountered, both are included in the output. The
      // "addSharedEdges" flag allows one of these two copies to be removed by
      // changing its intersection parameter from 0 to 1.
      double t = (a0 == b0 || a0 == b1) ? 0 : 1;
      if (!addSharedEdges && a1 == b1) {
        t = 1;
      }
      intersections.add(new ParametrizedS2Point(t, t == 0 ? a0 : a1));
    }
  }

  /**
   * Find all points where the polygon B intersects the edge (a0,a1), and add
   * the corresponding parameter values (in the range [0,1]) to "intersections".
   */
  private static void clipEdge(final S2Point a0, final S2Point a1, S2LoopSequenceIndex bIndex,
      boolean addSharedEdges, List<ParametrizedS2Point> intersections) {
    S2LoopSequenceIndex.DataEdgeIterator it = new S2LoopSequenceIndex.DataEdgeIterator(bIndex);
    it.getCandidates(a0, a1);
    S2EdgeUtil.EdgeCrosser crosser = new S2EdgeUtil.EdgeCrosser(a0, a1, a0);
    S2Point from = null;
    S2Point to = null;
    for (; it.hasNext(); it.next()) {
      S2Point previousTo = to;
      S2Edge fromTo = bIndex.edgeFromTo(it.index());
      from = fromTo.getStart();
      to = fromTo.getEnd();
      if (previousTo != from) {
        crosser.restartAt(from);
      }
      int crossing = crosser.robustCrossing(to);
      if (crossing < 0) {
        continue;
      }
      addIntersection(a0, a1, from, to, addSharedEdges, crossing, intersections);
    }
  }

  /**
   * Clip the boundary of A to the interior of B, and add the resulting edges to
   * "builder". Shells are directed CCW and holes are directed clockwise, unless
   * "reverseA" or "reverseB" is true in which case these directions in the
   * corresponding polygon are reversed. If "invertB" is true, the boundary of A
   * is clipped to the exterior rather than the interior of B. If
   * "adSharedEdges" is true, then the output will include any edges that are
   * shared between A and B (both edges must be in the same direction after any
   * edge reversals are taken into account).
   */
  private static void clipBoundary(final S2Polygon a,
      boolean reverseA,
      final S2Polygon b,
      boolean reverseB,
      boolean invertB,
      boolean addSharedEdges,
      S2PolygonBuilder builder) {
    S2PolygonIndex bIndex = new S2PolygonIndex(b, reverseB);
    bIndex.predictAdditionalCalls(a.getNumVertices());

    List<ParametrizedS2Point> intersections = Lists.newArrayList();
    for (S2Loop aLoop : a.loops) {
      int n = aLoop.numVertices();
      int dir = (aLoop.isHole() ^ reverseA) ? -1 : 1;
      boolean inside = b.contains(aLoop.vertex(0)) ^ invertB;
      for (int j = (dir > 0) ? 0 : n; n > 0; --n, j += dir) {
        S2Point a0 = aLoop.vertex(j);
        S2Point a1 = aLoop.vertex(j + dir);
        intersections.clear();
        clipEdge(a0, a1, bIndex, addSharedEdges, intersections);

        if (inside) {
          intersections.add(new ParametrizedS2Point(0.0, a0));
        }
        inside = ((intersections.size() & 0x1) == 0x1);
        if ((b.contains(a1) ^ invertB) != inside) {
          // TODO(andriy): do something more meaningful here.
          // Better yet, refactor and move this check to the unit test.
          log.severe("Internal clipBoundary error.");
        }
        if (inside) {
          intersections.add(new ParametrizedS2Point(1.0, a1));
        }

        // Remove duplicates and produce a list of unique intersections.
        TreeMultiset<ParametrizedS2Point> sortedIntersections = TreeMultiset.create();
        sortedIntersections.addAll(intersections);
        Iterator<ParametrizedS2Point> iter = sortedIntersections.iterator();
        while (iter.hasNext()) {
          S2Point p0 = iter.next().getPoint();
          if (!iter.hasNext()) {
            break;
          }
          S2Point p1 = iter.next().getPoint();
          if (p0.equals(p1)) {
            continue;
          }
          builder.addEdge(p0, p1);
        }
      }
    }
  }

  /**
   * Returns total number of vertices in all loops.
   */
  public int getNumVertices() {
    return this.numVertices;
  }

  /**
   * Initialize this polygon to the intersection, union, or difference (A - B)
   * of the given two polygons. The "vertexMergeRadius" determines how close two
   * vertices must be to be merged together and how close a vertex must be to an
   * edge in order to be spliced into it (see S2PolygonBuilder for details). By
   * default, the merge radius is just large enough to compensate for errors
   * that occur when computing intersection points between edges
   * (S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE).
   *
   *  If you are going to convert the resulting polygon to a lower-precision
   * format, it is necessary to increase the merge radius in order to get a
   * valid result after rounding (i.e. no duplicate vertices, etc). For example,
   * if you are going to convert them to geostore.PolygonProto format, then
   * S1Angle.e7(1) is a good value for "vertex_merge_radius".
   */
  public void initToIntersection(final S2Polygon a, final S2Polygon b) {
    initToIntersectionSloppy(a, b, S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE);
  }

  public void initToIntersectionSloppy(
      final S2Polygon a, final S2Polygon b, S1Angle vertexMergeRadius) {
    Preconditions.checkState(numLoops() == 0);
    if (!a.bound.intersects(b.bound)) {
      return;
    }

    // We want the boundary of A clipped to the interior of B,
    // plus the boundary of B clipped to the interior of A,
    // plus one copy of any directed edges that are in both boundaries.

    S2PolygonBuilder.Options options = S2PolygonBuilder.Options.DIRECTED_XOR;
    options.setMergeDistance(vertexMergeRadius);
    S2PolygonBuilder builder = new S2PolygonBuilder(options);
    clipBoundary(a, false, b, false, false, true, builder);
    clipBoundary(b, false, a, false, false, false, builder);
    if (!builder.assemblePolygon(this, null)) {
      // TODO (andriy): do something more meaningful here.
      log.severe("Bad directed edges");
    }
  }

  public void initToUnion(final S2Polygon a, final S2Polygon b) {
    initToUnionSloppy(a, b, S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE);
  }

  public void initToUnionSloppy(final S2Polygon a, final S2Polygon b, S1Angle vertexMergeRadius) {
    Preconditions.checkState(numLoops() == 0);

    // We want the boundary of A clipped to the exterior of B,
    // plus the boundary of B clipped to the exterior of A,
    // plus one copy of any directed edges that are in both boundaries.

    S2PolygonBuilder.Options options = S2PolygonBuilder.Options.DIRECTED_XOR;
    options.setMergeDistance(vertexMergeRadius);
    S2PolygonBuilder builder = new S2PolygonBuilder(options);
    clipBoundary(a, false, b, false, true, true, builder);
    clipBoundary(b, false, a, false, true, false, builder);
    if (!builder.assemblePolygon(this, null)) {
      // TODO(andriy): do something more meaningful here.
      log.severe("Bad directed edges");
    }
  }

  /**
   * Return a polygon which is the union of the given polygons. Note: clears the
   * List!
   */
  public static S2Polygon destructiveUnion(List<S2Polygon> polygons) {
    return destructiveUnionSloppy(polygons, S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE);
  }

  /**
   * Return a polygon which is the union of the given polygons; combines
   * vertices that form edges that are almost identical, as defined by
   * vertexMergeRadius. Note: clears the List!
   */
  public static S2Polygon destructiveUnionSloppy(
      List<S2Polygon> polygons, S1Angle vertexMergeRadius) {
    // Effectively create a priority queue of polygons in order of number of
    // vertices. Repeatedly union the two smallest polygons and add the result
    // to the queue until we have a single polygon to return.

    // map: # of vertices -> polygon
    TreeMultimap<Integer, S2Polygon> queue = TreeMultimap.create();

    for (S2Polygon polygon : polygons) {
      queue.put(polygon.getNumVertices(), polygon);
    }
    polygons.clear();

    Set<Map.Entry<Integer, S2Polygon>> queueSet = queue.entries();
    while (queueSet.size() > 1) {
      // Pop two simplest polygons from queue.
      queueSet = queue.entries();
      Iterator<Map.Entry<Integer, S2Polygon>> smallestIter = queueSet.iterator();

      Map.Entry<Integer, S2Polygon> smallest = smallestIter.next();
      int aSize = smallest.getKey().intValue();
      S2Polygon aPolygon = smallest.getValue();
      smallestIter.remove();

      smallest = smallestIter.next();
      int bSize = smallest.getKey().intValue();
      S2Polygon bPolygon = smallest.getValue();
      smallestIter.remove();

      // Union and add result back to queue.
      S2Polygon unionPolygon = new S2Polygon();
      unionPolygon.initToUnionSloppy(aPolygon, bPolygon, vertexMergeRadius);
      int unionSize = aSize + bSize;
      queue.put(unionSize, unionPolygon);
      // We assume that the number of vertices in the union polygon is the
      // sum of the number of vertices in the original polygons, which is not
      // always true, but will almost always be a decent approximation, and
      // faster than recomputing.
    }

    if (queue.isEmpty()) {
      return new S2Polygon();
    } else {
      return queue.get(queue.asMap().firstKey()).first();
    }
  }

  public boolean isNormalized() {
    Multiset<S2Point> vertices = HashMultiset.<S2Point>create();
    S2Loop lastParent = null;
    for (int i = 0; i < numLoops(); ++i) {
      S2Loop child = loop(i);
      if (child.depth() == 0) {
        continue;
      }
      S2Loop parent = loop(getParent(i));
      if (parent != lastParent) {
        vertices.clear();
        for (int j = 0; j < parent.numVertices(); ++j) {
          vertices.add(parent.vertex(j));
        }
        lastParent = parent;
      }
      int count = 0;
      for (int j = 0; j < child.numVertices(); ++j) {
        if (vertices.count(child.vertex(j)) > 0) {
          ++count;
        }
      }
      if (count > 1) {
        return false;
      }
    }
    return true;
  }

  /**
   * Return true if two polygons have the same boundary except for vertex
   * perturbations. Both polygons must have loops with the same cyclic vertex
   * order and the same nesting hierarchy, but the vertex locations are allowed
   * to differ by up to "max_error". Note: This method mostly useful only for
   * testing purposes.
   */
  boolean boundaryApproxEquals(S2Polygon b, double maxError) {
    if (numLoops() != b.numLoops()) {
      log.severe(
          "!= loops: " + Integer.toString(numLoops()) + " vs. " + Integer.toString(b.numLoops()));
      return false;
    }

    // For now, we assume that there is at most one candidate match for each
    // loop. (So far this method is just used for testing.)
    for (int i = 0; i < numLoops(); ++i) {
      S2Loop aLoop = loop(i);
      boolean success = false;
      for (int j = 0; j < numLoops(); ++j) {
        S2Loop bLoop = b.loop(j);
        if (bLoop.depth() == aLoop.depth() && bLoop.boundaryApproxEquals(aLoop, maxError)) {
          success = true;
          break;
        }
      }
      if (!success) {
        return false;
      }
    }
    return true;
  }

  // S2Region interface (see S2Region.java for details):

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


  /** Return a bounding latitude-longitude rectangle. */
  @Override
  public S2LatLngRect getRectBound() {
    return bound;
  }

  /**
   * 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) {
    if (numLoops() == 1) {
      return loop(0).contains(cell);
    }
    S2LatLngRect cellBound = cell.getRectBound();
    if (!bound.contains(cellBound)) {
      return false;
    }

    S2Loop cellLoop = new S2Loop(cell, cellBound);
    S2Polygon cellPoly = new S2Polygon(cellLoop);
    return contains(cellPoly);
  }

  /**
   * 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 (numLoops() == 1) {
      return loop(0).mayIntersect(cell);
    }
    S2LatLngRect cellBound = cell.getRectBound();
    if (!bound.intersects(cellBound)) {
      return false;
    }

    S2Loop cellLoop = new S2Loop(cell, cellBound);
    S2Polygon cellPoly = new S2Polygon(cellLoop);
    return intersects(cellPoly);
  }

  /**
   * The point 'p' does not need to be normalized.
   */
  public boolean contains(S2Point p) {
    if (numLoops() == 1) {
      return loop(0).contains(p); // Optimization.
    }
    if (!bound.contains(p)) {
      return false;
    }
    boolean inside = false;
    for (int i = 0; i < numLoops(); ++i) {
      inside ^= loop(i).contains(p);
      if (inside && !hasHoles) {
        break; // Shells are disjoint.
      }
    }
    return inside;
  }

  // For each map entry, sorts the value list.
  private static void sortValueLoops(Map<S2Loop, List<S2Loop>> loopMap) {
    for (S2Loop key : loopMap.keySet()) {
      Collections.sort(loopMap.get(key));
    }
  }

  private static void insertLoop(S2Loop newLoop, S2Loop parent, Map<S2Loop, List<S2Loop>> loopMap) {
    List<S2Loop> children = loopMap.get(parent);

    if (children == null) {
      children = Lists.newArrayList();
      loopMap.put(parent, children);
    }

    for (S2Loop child : children) {
      if (child.containsNested(newLoop)) {
        insertLoop(newLoop, child, loopMap);
        return;
      }
    }

    // No loop may contain the complement of another loop. (Handling this case
    // is significantly more complicated.)
    // assert (parent == null || !newLoop.containsNested(parent));

    // Some of the children of the parent loop may now be children of
    // the new loop.
    List<S2Loop> newChildren = loopMap.get(newLoop);
    for (int i = 0; i < children.size();) {
      S2Loop child = children.get(i);
      if (newLoop.containsNested(child)) {
        if (newChildren == null) {
          newChildren = Lists.newArrayList();
          loopMap.put(newLoop, newChildren);
        }
        newChildren.add(child);
        children.remove(i);
      } else {
        ++i;
      }
    }
    children.add(newLoop);
  }

  private void initLoop(S2Loop loop, int depth, Map<S2Loop, List<S2Loop>> loopMap) {
    if (loop != null) {
      loop.setDepth(depth);
      loops.add(loop);
    }
    List<S2Loop> children = loopMap.get(loop);
    if (children != null) {
      for (S2Loop child : children) {
        initLoop(child, depth + 1, loopMap);
      }
    }
  }

  private int containsOrCrosses(S2Loop b) {
    boolean inside = false;
    for (int i = 0; i < numLoops(); ++i) {
      int result = loop(i).containsOrCrosses(b);
      if (result < 0) {
        return -1; // The loop boundaries intersect.
      }
      if (result > 0) {
        inside ^= true;
      }
    }
    return inside ? 1 : 0; // True if loop B is contained by the polygon.
  }

  /** Return true if any loop contains the given loop. */
  private boolean anyLoopContains(S2Loop b) {
    for (int i = 0; i < numLoops(); ++i) {
      if (loop(i).contains(b)) {
        return true;
      }
    }
    return false;
  }

  /** Return true if this polygon (A) contains all the shells of B. */
  private boolean containsAllShells(S2Polygon b) {
    for (int j = 0; j < b.numLoops(); ++j) {
      if (b.loop(j).sign() < 0) {
        continue;
      }
      if (containsOrCrosses(b.loop(j)) <= 0) {
        // Shell of B is not contained by A, or the boundaries intersect.
        return false;
      }
    }
    return true;
  }

  /**
   * Return true if this polygon (A) excludes (i.e. does not intersect) all
   * holes of B.
   */
  private boolean excludesAllHoles(S2Polygon b) {
    for (int j = 0; j < b.numLoops(); ++j) {
      if (b.loop(j).sign() > 0) {
        continue;
      }
      if (containsOrCrosses(b.loop(j)) != 0) {
        // Hole of B is contained by A, or the boundaries intersect.
        return false;
      }
    }
    return true;
  }

  /** Return true if this polygon (A) intersects any shell of B. */
  private boolean intersectsAnyShell(S2Polygon b) {
    for (int j = 0; j < b.numLoops(); ++j) {
      if (b.loop(j).sign() < 0) {
        continue;
      }
      if (containsOrCrosses(b.loop(j)) != 0) {
        // Shell of B is contained by A, or the boundaries intersect.
        return true;
      }
    }
    return false;
  }

  /**
   * A human readable representation of the polygon
   */
  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("Polygon: (").append(numLoops()).append(") loops:\n");
    for (int i = 0; i < numLoops(); ++i) {
      S2Loop s2Loop = loop(i);
      sb.append("loop <\n");
      for (int v = 0; v < s2Loop.numVertices(); ++v) {
        S2Point s2Point = s2Loop.vertex(v);
        sb.append(s2Point.toDegreesString());
        sb.append("\n"); // end of vertex
      }
      sb.append(">\n"); // end of loop
    }
    return sb.toString();
  }

  private static class UndirectedEdge extends S2Edge {

    public UndirectedEdge(S2Point vertexA, S2Point vertexB) {
      super(vertexA, vertexB);
    }

    @Override
    public boolean equals(Object o) {
      if (o == null || !(o instanceof UndirectedEdge)) {
        return false;
      }
      UndirectedEdge other = (UndirectedEdge) o;
      return ((getStart().equals(other.getStart()) && getEnd().equals(other.getEnd()))
          || (getStart().equals(other.getEnd()) && getEnd().equals(other.getStart())));
    }

    @Override
    public int hashCode() {
      return getStart().hashCode() + getEnd().hashCode();
    }
  }

  private static class LoopVertexIndexPair {

    private final int loopIndex;
    private final int vertexIndex;

    public LoopVertexIndexPair(int loopIndex, int vertexIndex) {
      this.loopIndex = loopIndex;
      this.vertexIndex = vertexIndex;
    }

    public int getLoopIndex() {
      return loopIndex;
    }

    public int getVertexIndex() {
      return vertexIndex;
    }
  }

  /**
   * An S2Point that also has a parameter associated with it, which corresponds
   * to a time-like order on the points.
   */
  private static class ParametrizedS2Point implements Comparable<ParametrizedS2Point> {

    private final double time;
    private final S2Point point;

    public ParametrizedS2Point(double time, S2Point point) {
      this.time = time;
      this.point = point;
    }

    public double getTime() {
      return time;
    }

    public S2Point getPoint() {
      return point;
    }

    @Override
    public int compareTo(ParametrizedS2Point o) {
      int compareTime = Double.compare(time, o.getTime());
      if (compareTime != 0) {
        return compareTime;
      }
      return point.compareTo(o.getPoint());
    }

  }
}