Class S2CellUnion
- java.lang.Object
-
- com.google.common.geometry.S2CellUnion
-
@GwtCompatible(serializable=true) public class S2CellUnion extends java.lang.Object implements S2Region, java.lang.Iterable<S2CellId>, java.io.Serializable
An S2CellUnion is a region consisting of cells of various sizes. Typically a cell union is used to approximate some other shape. There is a tradeoff between the accuracy of the approximation and how many cells are used. Unlike polygons, cells have a fixed hierarchical structure. This makes them more suitable for optimizations based on preprocessing.An S2CellUnion is represented as a vector of sorted, non-overlapping S2CellIds. By default the vector is also "normalized", meaning that groups of 4 child cells have been replaced by their parent cell whenever possible. S2CellUnions are not required to be normalized, but certain operations will return different results if they are not, e.g.
contains(S2CellUnion)
.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.ArrayList<S2CellId>
cellIds
The CellIds that form the Unionprivate static byte
LOSSLESS_ENCODING_VERSION
private static long
serialVersionUID
-
Constructor Summary
Constructors Constructor Description S2CellUnion()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
approxArea()
Calculates this cell union's area by summing the approximate area for each contained cell, usingS2Cell.approxArea()
.private static boolean
areSiblings(S2CellId a, S2CellId b, S2CellId c, S2CellId d)
Returns true if the given four cells have a common parent.double
averageBasedArea()
Approximate this cell union's area by summing the average area of each contained cell's average area, usingS2Cell.averageArea()
.S2CellId
cellId(int i)
Convenience methods for accessing the individual cell ids.java.util.ArrayList<S2CellId>
cellIds()
Direct access to the underlying vector for iteration .S2Region
clone()
boolean
contains(S2Cell cell)
This is a fast operation (logarithmic in the size of the cell union).boolean
contains(S2CellId id)
Return true if the cell union contains the given cell id.boolean
contains(S2CellUnion that)
Returns true if this cell union containsthat
.boolean
contains(S2Point p)
The point 'p' does not need to be normalized.static S2CellUnion
decode(LittleEndianInput input)
Asdecode(InputStream)
, but avoids creating a little endian input helper.static S2CellUnion
decode(java.io.InputStream input)
Decodes an S2CellUnion encoded with Encode().void
denormalize(int minLevel, int levelMod, java.util.ArrayList<S2CellId> output)
Replaces "output" with an expanded version of the cell union where any cells whose level is less than "min_level" or where (level - min_level) is not a multiple of "level_mod" are replaced by their children, until either both of these conditions are satisfied or the maximum level is reached.void
encode(LittleEndianOutput output)
Asencode(OutputStream)
, but avoids creating a little endian output helper.void
encode(java.io.OutputStream output)
Writes a simple lossless encoding of this cell union to the given output stream.boolean
equals(java.lang.Object that)
Return true if two cell unions are identical.double
exactArea()
Calculates this cell union's area by summing the exact area for each contained cell, using theS2Cell.exactArea()
.void
expand(int level)
Expands the cell union such that it contains all cells of the given level that are adjacent to any cell of the original union.void
expand(S1Angle minRadius, int maxLevelDiff)
Expand the cell union such that it contains all points whose distance to the cell union is at most minRadius, but do not use cells that are more than maxLevelDiff levels higher than the largest cell in the input.S2Cap
getCapBound()
Return a bounding spherical cap.void
getDifference(S2CellUnion x, S2CellUnion y)
Initiaizes this cell union to the difference of the two given cell unions.private void
getDifferenceInternal(S2CellId cell, S2CellUnion y)
void
getIntersection(S2CellUnion x, S2CellId id)
Specialized version of GetIntersection() that gets the intersection of a cell union with the given cell id.void
getIntersection(S2CellUnion x, S2CellUnion y)
Initializes this cell union to the intersection of the two given cell unions.static void
getIntersection(java.util.List<S2CellId> x, java.util.List<S2CellId> y, java.util.List<S2CellId> results)
Like#getIntersection(S2CellUnion, S2CellUnion)
, but works directly with lists of S2CellIds, and this method has slightly more relaxed normalization requirements: the input vectors may contain groups of 4 child cells that all have the same parent.S2LatLngRect
getRectBound()
Return a bounding latitude-longitude rectangle.void
getUnion(S2CellUnion x, S2CellUnion y)
Sets this cell union to the union ofx
andy
.int
hashCode()
private static int
indexedBinarySearch(java.util.List<S2CellId> l, S2CellId key, int low)
Just as normal binary search, except that it allows specifying the starting value for the lower bound.void
initFromBeginEnd(S2CellId begin, S2CellId end)
AsinitFromMinMax(S2CellId, S2CellId)
, except that the union covers the range of leaf cells from "begin" (inclusive) to "end" (exclusive.) Ifbegin.equals(end)
, the result is empty.void
initFromCellIds(java.util.ArrayList<S2CellId> cellIds)
Populates a cell union with the given S2CellIds, and then calls normalize().void
initFromIds(java.util.List<java.lang.Long> cellIds)
Populates a cell union with the given 64-bit cell ids, and then calls normalize().void
initFromMinMax(S2CellId minId, S2CellId maxId)
Create a cell union that corresponds to a continuous range of cell ids.void
initRawCellIds(java.util.ArrayList<S2CellId> cellIds)
Populates a cell union with the given S2CellIds.void
initRawIds(java.util.List<java.lang.Long> cellIds)
Populates a cell union with the given 64 bit cell ids.void
initRawSwap(java.util.List<S2CellId> cellIds)
Like the initFrom*() constructors, but does not call normalize().void
initSwap(java.util.List<S2CellId> cellIds)
Populates a cell union with the given S2CellIds.boolean
intersects(S2CellId id)
Return true if the cell union intersects the given cell id.boolean
intersects(S2CellUnion union)
Return true if this cell union intersectsunion
.boolean
isNormalized()
Returns true if the cell union is normalized, meaning that itisValid()
is true and that no four cells have a common parent.boolean
isValid()
Returns true if the cell union is valid, meaning that the S2CellIds are non-overlapping and sorted in increasing order.java.util.Iterator<S2CellId>
iterator()
Enable iteration over the union's cells.long
leafCellsCovered()
The number of leaf cells covered by the union.boolean
mayIntersect(S2Cell cell)
This is a fast operation (logarithmic in the size of the cell union).boolean
normalize()
Normalizes the cell union by discarding cells that are contained by other cells, replacing groups of 4 child cells by their parent cell whenever possible, and sorting all the cell ids in increasing order.static boolean
normalize(java.util.List<S2CellId> ids)
Likenormalize()
, but works directly with a vector of S2CellIds.void
pack()
If there are more than "excess" elements of the cell_ids() vector that are allocated but unused, reallocate the array to eliminate the excess space.int
size()
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
LOSSLESS_ENCODING_VERSION
private static final byte LOSSLESS_ENCODING_VERSION
- See Also:
- Constant Field Values
-
cellIds
private java.util.ArrayList<S2CellId> cellIds
The CellIds that form the Union
-
-
Method Detail
-
initFromCellIds
public void initFromCellIds(java.util.ArrayList<S2CellId> cellIds)
Populates a cell union with the given S2CellIds, and then calls normalize(). This directly uses the input list, without copying it.
-
initFromIds
public void initFromIds(java.util.List<java.lang.Long> cellIds)
Populates a cell union with the given 64-bit cell ids, and then calls normalize().
-
initSwap
public void initSwap(java.util.List<S2CellId> cellIds)
Populates a cell union with the given S2CellIds. The input list is copied, and then cleared.
-
initRawCellIds
public void initRawCellIds(java.util.ArrayList<S2CellId> cellIds)
Populates a cell union with the given S2CellIds. This does not call normalize, seeinitRawSwap(java.util.List<com.google.common.geometry.S2CellId>)
for details. This directly uses the input list, without copying it.
-
initRawIds
public void initRawIds(java.util.List<java.lang.Long> cellIds)
Populates a cell union with the given 64 bit cell ids. This does not call normalize, seeinitRawSwap(java.util.List<com.google.common.geometry.S2CellId>)
for details. The input list is copied.
-
initRawSwap
public void initRawSwap(java.util.List<S2CellId> cellIds)
Like the initFrom*() constructors, but does not call normalize(). The cell union *must* be normalized before doing any calculations with it, so it is the caller's * responsibility to make sure that the input is normalized. This method is useful when converting cell unions to another representation and back.The input list is copied, and then cleared.
-
initFromMinMax
public void initFromMinMax(S2CellId minId, S2CellId maxId)
Create a cell union that corresponds to a continuous range of cell ids. The output is a normalized collection of cell ids that covers the leaf cells between "minId" and "maxId" inclusive.Requires that minId.isLeaf(), maxId.isLeaf(), and minId <= maxId.
-
initFromBeginEnd
public void initFromBeginEnd(S2CellId begin, S2CellId end)
AsinitFromMinMax(S2CellId, S2CellId)
, except that the union covers the range of leaf cells from "begin" (inclusive) to "end" (exclusive.) Ifbegin.equals(end)
, the result is empty.Requires that begin.isLeaf(), end.isLeaf(), and begin <= end.
-
size
public int size()
-
cellId
public S2CellId cellId(int i)
Convenience methods for accessing the individual cell ids.
-
iterator
public java.util.Iterator<S2CellId> iterator()
Enable iteration over the union's cells.- Specified by:
iterator
in interfacejava.lang.Iterable<S2CellId>
-
cellIds
public java.util.ArrayList<S2CellId> cellIds()
Direct access to the underlying vector for iteration .
-
isValid
public boolean isValid()
Returns true if the cell union is valid, meaning that the S2CellIds are non-overlapping and sorted in increasing order.
-
isNormalized
public boolean isNormalized()
Returns true if the cell union is normalized, meaning that itisValid()
is true and that no four cells have a common parent.Certain operations such as
contains(S2CellUnion)
may return a different result if the cell union is not normalized.
-
areSiblings
private static boolean areSiblings(S2CellId a, S2CellId b, S2CellId c, S2CellId d)
Returns true if the given four cells have a common parent.Requires the four cells are distinct.
-
denormalize
public void denormalize(int minLevel, int levelMod, java.util.ArrayList<S2CellId> output)
Replaces "output" with an expanded version of the cell union where any cells whose level is less than "min_level" or where (level - min_level) is not a multiple of "level_mod" are replaced by their children, until either both of these conditions are satisfied or the maximum level is reached.This method allows a covering generated by S2RegionCoverer using min_level() or level_mod() constraints to be stored as a normalized cell union (which allows various geometric computations to be done) and then converted back to the original list of cell ids that satisfies the desired constraints.
-
pack
public void pack()
If there are more than "excess" elements of the cell_ids() vector that are allocated but unused, reallocate the array to eliminate the excess space. This reduces memory usage when many cell unions need to be held in memory at once.
-
contains
public boolean contains(S2CellId id)
Return true if the cell union contains the given cell id. Containment is defined with respect to regions, e.g. a cell contains its 4 children. This is a fast operation (logarithmic in the size of the cell union).CAVEAT: If you have constructed a valid but non-normalized S2CellUnion, note that groups of 4 child cells are not considered to contain their parent cell. To get this behavior you must construct a normalized cell union, or call
normalize()
prior to this method.
-
intersects
public boolean intersects(S2CellId id)
Return true if the cell union intersects the given cell id. This is a fast operation (logarithmic in the size of the cell union).
-
contains
public boolean contains(S2CellUnion that)
Returns true if this cell union containsthat
.CAVEAT: If you have constructed a valid but non-normalized S2CellUnion, note that groups of 4 child cells are not considered to contain their parent cell. To get this behavior you must construct a normalized cell union, or call
normalize()
prior to this method.
-
contains
public boolean contains(S2Cell cell)
This is a fast operation (logarithmic in the size of the cell union).
-
intersects
public boolean intersects(S2CellUnion union)
Return true if this cell union intersectsunion
.
-
getUnion
public void getUnion(S2CellUnion x, S2CellUnion y)
Sets this cell union to the union ofx
andy
.
-
getIntersection
public void getIntersection(S2CellUnion x, S2CellId id)
Specialized version of GetIntersection() that gets the intersection of a cell union with the given cell id. This can be useful for "splitting" a cell union into chunks.Note:
x
andy
must be normalized.
-
getIntersection
public void getIntersection(S2CellUnion x, S2CellUnion y)
Initializes this cell union to the intersection of the two given cell unions. Requires: x != this and y != this.Note:
x
andy
must be normalized.
-
getIntersection
public static void getIntersection(java.util.List<S2CellId> x, java.util.List<S2CellId> y, java.util.List<S2CellId> results)
Like#getIntersection(S2CellUnion, S2CellUnion)
, but works directly with lists of S2CellIds, and this method has slightly more relaxed normalization requirements: the input vectors may contain groups of 4 child cells that all have the same parent. (In a normalized S2CellUnion, such groups are always replaced by the parent cell.)Note:
x
andy
must be sorted.
-
getDifference
public void getDifference(S2CellUnion x, S2CellUnion y)
Initiaizes this cell union to the difference of the two given cell unions.
-
getDifferenceInternal
private void getDifferenceInternal(S2CellId cell, S2CellUnion y)
-
indexedBinarySearch
private static int indexedBinarySearch(java.util.List<S2CellId> l, S2CellId key, int low)
Just as normal binary search, except that it allows specifying the starting value for the lower bound.- Returns:
- The position of the searched element in the list (if found), or the position where the element could be inserted without violating the order.
-
expand
public void expand(int level)
Expands the cell union such that it contains all cells of the given level that are adjacent to any cell of the original union. Two cells are defined as adjacent if their boundaries have any points in common, i.e. most cells have 8 adjacent cells (not counting the cell itself).Note that the size of the output is exponential in "level". For example, if level == 20 and the input has a cell at level 10, there will be on the order of 4000 adjacent cells in the output. For most applications the Expand(min_fraction, min_distance) method below is easier to use.
-
expand
public void expand(S1Angle minRadius, int maxLevelDiff)
Expand the cell union such that it contains all points whose distance to the cell union is at most minRadius, but do not use cells that are more than maxLevelDiff levels higher than the largest cell in the input. The second parameter controls the tradeoff between accuracy and output size when a large region is being expanded by a small amount (e.g. expanding Canada by 1km).For example, if maxLevelDiff == 4, the region will always be expanded by approximately 1/16 the width of its largest cell. Note that in the worst case, the number of cells in the output can be up to 4 * (1 + 2 ** maxLevelDiff) times larger than the number of cells in the input.
-
clone
public S2Region clone()
- Overrides:
clone
in classjava.lang.Object
-
getCapBound
public S2Cap getCapBound()
Description copied from interface:S2Region
Return a bounding spherical cap.- Specified by:
getCapBound
in interfaceS2Region
-
getRectBound
public S2LatLngRect getRectBound()
Description copied from interface:S2Region
Return a bounding latitude-longitude rectangle.- Specified by:
getRectBound
in interfaceS2Region
-
mayIntersect
public boolean mayIntersect(S2Cell cell)
This is a fast operation (logarithmic in the size of the cell union).- Specified by:
mayIntersect
in interfaceS2Region
-
contains
public boolean contains(S2Point p)
The point 'p' does not need to be normalized. This is a fast operation (logarithmic in the size of the cell union).
-
leafCellsCovered
public long leafCellsCovered()
The number of leaf cells covered by the union. This will be no more than 6*2^60 for the whole sphere.- Returns:
- the number of leaf cells covered by the union
-
averageBasedArea
public double averageBasedArea()
Approximate this cell union's area by summing the average area of each contained cell's average area, usingS2Cell.averageArea()
. This is equivalent to the number of leaves covered, multiplied by the average area of a leaf.Note that
S2Cell.averageArea()
does not take into account distortion of cell, and thus may be off by up to a factor of 1.7. NOTE: Since this is proportional to LeafCellsCovered(), it is always better to use the other function if all you care about is the relative average area between objects.- Returns:
- the sum of the average area of each contained cell's average area
-
approxArea
public double approxArea()
Calculates this cell union's area by summing the approximate area for each contained cell, usingS2Cell.approxArea()
.- Returns:
- approximate area of the cell union
-
exactArea
public double exactArea()
Calculates this cell union's area by summing the exact area for each contained cell, using theS2Cell.exactArea()
.- Returns:
- the exact area of the cell union
-
equals
public boolean equals(java.lang.Object that)
Return true if two cell unions are identical.- Overrides:
equals
in classjava.lang.Object
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
normalize
public boolean normalize()
Normalizes the cell union by discarding cells that are contained by other cells, replacing groups of 4 child cells by their parent cell whenever possible, and sorting all the cell ids in increasing order. Returns true if the number of cells was reduced.This method *must* be called before doing any calculations on the cell union, such as Intersects() or Contains().
- Returns:
- true if the normalize operation had any effect on the cell union, false if the union was already normalized
-
normalize
public static boolean normalize(java.util.List<S2CellId> ids)
Likenormalize()
, but works directly with a vector of S2CellIds.
-
encode
public void encode(java.io.OutputStream output) throws java.io.IOException
Writes a simple lossless encoding of this cell union to the given output stream. This encoding uses 1 byte for a version number, and N+1 64-bit longs where the first is the number of longs that follow.- Throws:
java.io.IOException
- there is a problem writing to the underlying stream
-
encode
public void encode(LittleEndianOutput output) throws java.io.IOException
Asencode(OutputStream)
, but avoids creating a little endian output helper.Use this method if a number of S2 objects will be encoded to the same underlying stream.
- Throws:
java.io.IOException
-
decode
public static S2CellUnion decode(java.io.InputStream input) throws java.io.IOException
Decodes an S2CellUnion encoded with Encode(). Returns true on success.- Throws:
java.io.IOException
- there is a problem reading from the underlying stream, the version number doesn't match, or the number of elements to read is not between 0 and 2^31-1.
-
decode
public static S2CellUnion decode(LittleEndianInput input) throws java.io.IOException
Asdecode(InputStream)
, but avoids creating a little endian input helper.Use this method if a number of S2 objects will be decoded from the same underlying stream.
- Throws:
java.io.IOException
-
-