Class S2CellUnion
- All Implemented Interfaces:
S2Region
,Serializable
,Iterable<S2CellId>
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:
-
Field Summary
FieldsModifier and TypeFieldDescriptionThe CellIds that form the Unionprivate static final byte
private static final long
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptiondouble
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
Approximate this cell union's area by summing the average area of each contained cell's average area, usingS2Cell.averageArea()
.cellId
(int i) Convenience methods for accessing the individual cell ids.cellIds()
Direct access to the underlying vector for iteration .clone()
boolean
This is a fast operation (logarithmic in the size of the cell union).boolean
Return true if the cell union contains the given cell id.boolean
contains
(S2CellUnion that) Returns true if this cell union containsthat
.boolean
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
(InputStream input) Decodes an S2CellUnion encoded with Encode().void
denormalize
(int minLevel, int levelMod, 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
(OutputStream output) Writes a simple lossless encoding of this cell union to the given output stream.boolean
Return true if two cell unions are identical.double
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 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.Return a bounding spherical cap.void
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
Initializes this cell union to the intersection of the two given cell unions.static void
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.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
(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
(ArrayList<S2CellId> cellIds) Populates a cell union with the given S2CellIds, and then calls normalize().void
initFromIds
(List<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
(ArrayList<S2CellId> cellIds) Populates a cell union with the given S2CellIds.void
initRawIds
(List<Long> cellIds) Populates a cell union with the given 64 bit cell ids.void
initRawSwap
(List<S2CellId> cellIds) Like the initFrom*() constructors, but does not call normalize().void
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
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.iterator()
Enable iteration over the union's cells.long
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
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
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()
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
LOSSLESS_ENCODING_VERSION
private static final byte LOSSLESS_ENCODING_VERSION- See Also:
-
cellIds
The CellIds that form the Union
-
-
Constructor Details
-
S2CellUnion
public S2CellUnion()
-
-
Method Details
-
initFromCellIds
Populates a cell union with the given S2CellIds, and then calls normalize(). This directly uses the input list, without copying it. -
initFromIds
Populates a cell union with the given 64-bit cell ids, and then calls normalize(). -
initSwap
Populates a cell union with the given S2CellIds. The input list is copied, and then cleared. -
initRawCellIds
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
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
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
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 invalid input: '<'= maxId.
-
initFromBeginEnd
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 invalid input: '<'= end.
-
size
public int size() -
cellId
Convenience methods for accessing the individual cell ids. -
iterator
Enable iteration over the union's cells. -
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
Returns true if the given four cells have a common parent.Requires the four cells are distinct.
-
denormalize
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
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
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
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
This is a fast operation (logarithmic in the size of the cell union). -
intersects
Return true if this cell union intersectsunion
. -
getUnion
Sets this cell union to the union ofx
andy
. -
getIntersection
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
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
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
Initiaizes this cell union to the difference of the two given cell unions. -
getDifferenceInternal
-
indexedBinarySearch
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
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
-
getCapBound
Description copied from interface:S2Region
Return a bounding spherical cap.- Specified by:
getCapBound
in interfaceS2Region
-
getRectBound
Description copied from interface:S2Region
Return a bounding latitude-longitude rectangle.- Specified by:
getRectBound
in interfaceS2Region
-
mayIntersect
This is a fast operation (logarithmic in the size of the cell union).- Specified by:
mayIntersect
in interfaceS2Region
-
contains
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
Return true if two cell unions are identical. -
hashCode
public int hashCode() -
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
Likenormalize()
, but works directly with a vector of S2CellIds. -
encode
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:
IOException
- there is a problem writing to the underlying stream
-
encode
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:
IOException
-
decode
Decodes an S2CellUnion encoded with Encode(). Returns true on success.- Throws:
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
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:
IOException
-