| /* |
| * 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 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, create an array of vertex counts for each loop |
| * in the loop sequence and pass it to this constructor. Overwrite |
| * edgeFromTo(), calling decodeIndex() and use the resulting two indices to |
| * access your accessing vertices. |
| */ |
| private abstract static class S2LoopSequenceIndex extends S2EdgeIndex { |
| /** Map from the unidimensional edge index to the loop this edge belongs to. */ |
| private final int[] indexToLoop; |
| |
| /** |
| * Reverse of indexToLoop: maps a loop index to the unidimensional index |
| * of the first edge in the loop. |
| */ |
| private final int[] loopToFirstIndex; |
| |
| /** |
| * Must be called by each subclass with the array of vertices per loop. The |
| * length of the array is the number of loops, and the <code>i</code> |
| * <sup>th</sup> loop's vertex count is in the <code>i</code> |
| * <sup>th</sup> index of the array. |
| */ |
| public S2LoopSequenceIndex(int[] numVertices) { |
| int totalEdges = 0; |
| for (int edges : numVertices) { |
| totalEdges += edges; |
| } |
| indexToLoop = new int[totalEdges]; |
| loopToFirstIndex = new int[numVertices.length]; |
| |
| totalEdges = 0; |
| for (int j = 0; j < numVertices.length; j++) { |
| loopToFirstIndex[j] = totalEdges; |
| for (int i = 0; i < numVertices[j]; i++) { |
| indexToLoop[totalEdges] = j; |
| totalEdges++; |
| } |
| } |
| } |
| |
| public final LoopVertexIndexPair decodeIndex(int index) { |
| int loopIndex = indexToLoop[index]; |
| int vertexInLoop = index - loopToFirstIndex[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 |
| public final int getNumEdges() { |
| return indexToLoop.length; |
| } |
| |
| @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; |
| } |
| } |
| |
| // Indexing structure for an S2Polygon. |
| private static final class S2PolygonIndex extends S2LoopSequenceIndex { |
| private final S2Polygon poly; |
| private final boolean reverse; |
| |
| private static int[] getVertices(S2Polygon poly) { |
| int[] vertices = new int[poly.numLoops()]; |
| for (int i = 0; i < vertices.length; i++) { |
| vertices[i] = poly.loop(i).numVertices(); |
| } |
| return vertices; |
| } |
| |
| public S2PolygonIndex(S2Polygon poly, boolean reverse) { |
| super(getVertices(poly)); |
| this.poly = poly; |
| this.reverse = reverse; |
| } |
| |
| @Override |
| public S2Edge edgeFromTo(int index) { |
| LoopVertexIndexPair indices = decodeIndex(index); |
| int loopIndex = indices.getLoopIndex(); |
| int vertexInLoop = indices.getVertexIndex(); |
| S2Loop loop = 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); |
| // assert ((b.contains(a1) ^ invertB) == inside); |
| if (inside) { |
| intersections.add(new ParametrizedS2Point(1.0, a1)); |
| } |
| |
| // Remove duplicates and produce a list of unique intersections. |
| Collections.sort(intersections); |
| for (int size = intersections.size(), i = 1; i < size; i += 2) { |
| builder.addEdge(intersections.get(i - 1).getPoint(), intersections.get(i).getPoint()); |
| } |
| } |
| } |
| } |
| |
| /** |
| * 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 final class UndirectedEdge { |
| // Note: An UndirectedEdge and an S2Edge can never be considered equal (in |
| // terms of the equals() method) and hence they re not be related types. |
| // If you need to convert between the types then separate conversion |
| // methods should be introduced. |
| |
| private final S2Point a; |
| private final S2Point b; |
| |
| public UndirectedEdge(S2Point start, S2Point end) { |
| this.a = start; |
| this.b = end; |
| } |
| |
| public S2Point getStart() { |
| return a; |
| } |
| |
| public S2Point getEnd() { |
| return b; |
| } |
| |
| @Override |
| public String toString() { |
| return String.format("Edge: (%s <-> %s)\n or [%s <-> %s]", |
| a.toDegreesString(), b.toDegreesString(), a, b); |
| } |
| |
| @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 final 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 final 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.time); |
| if (compareTime != 0) { |
| return compareTime; |
| } |
| return point.compareTo(o.point); |
| } |
| } |
| } |