s2sphere

S2Region is an abstract interface representing a two-dimensional region on the unit sphere. It is designed to allow complex regions to be approximated by simpler ones.

Core Methods:

• S2Region* Clone() const: Returns a deep copy. Use down_cast<T*> to narrow to a specific subtype.
• S2Cap GetCapBound() const: Returns a bounding spherical cap (not guaranteed to be exact).
• S2LatLngRect GetRectBound() const: Returns a bounding latitude-longitude rectangle (not guaranteed to be tight).
• bool Contains(S2Cell const& cell) const: Returns true if the region completely contains the cell.
• bool MayIntersect(S2Cell const& cell) const: Returns false if the region definitely does not intersect the cell.
• virtual bool VirtualContainsPoint(S2Point const& p) const: Returns true if the point is in the region. For performance, use the non-virtual Contains(S2Point const& p) if calling on a specific known subtype.
• void Encode(Encoder* const encoder) const / bool Decode(Decoder* const decoder): Used for serialization. DecodeWithinScope can be used for faster decoding by pointing directly into the decoder's buffer (valid only for the lifetime of the decoder).

An S2Polygon is an S2Region representing a collection of loops acting as "shells" (outer boundaries) and "holes". A point is considered inside the polygon if it is contained by an odd number of loops.

Polygon Restrictions

To maintain validity, polygons must adhere to these rules:

1. No Crossing Loops: A loop's boundary cannot intersect both the interior and exterior of another loop.
2. No Shared Edges: If a loop contains edge AB, no other loop may contain edge AB or BA.
3. Area Limit: No single loop may cover more than half the area of the sphere (to prevent ambiguity between a loop and its complement).

Hierarchy and Traversal

Loops in an S2Polygon are organized in a nesting hierarchy. When initialized via Init(vector<S2Loop*>* loops), the polygon reorders loops using a preorder traversal. This means a parent loop is immediately followed by its descendants in the hierarchy.

• Finding Children: To find the immediate children of loop k, iterate from k+1 to GetLastDescendant(k) and select loops where depth == loop(k)->depth() + 1.
• Parent/Child Navigation:
  • GetParent(int k): Returns the index of the parent loop, or -1 if it is a shell.
  • GetLastDescendant(int k): Returns the index of the last loop contained within loop k.

Key Methods

• GetArea(): Returns the total area of the polygon interior (0 to 4*Pi).
• GetCentroid(): Returns the true centroid multiplied by the polygon area.

// Initializing a polygon with loops
std::vector<S2Loop*> loops = { shell_loop, hole_loop };
S2Polygon poly;
poly.Init(&loops); // poly now owns the loops and reorders them

// Accessing hierarchy
int parent_idx = poly.GetParent(1);
int last_desc = poly.GetLastDescendant(0);

You can traverse the hierarchy of cells using iterator-style methods on S2CellId.

Iterating Children

To iterate through the immediate children of a cell, use child_begin() and child_end(). Note that you must use the .next() method to advance the iterator to avoid confusion with incrementing the underlying 64-bit integer.

for(S2CellId c = id.child_begin(); c != id.child_end(); c = c.next()) {
    // Process child c
}

Global and Level-based Iteration

• Begin(int level) / End(int level): Iterates through all cells at a specific level across all 6 faces of the cube.
• child_begin(int level) / child_end(int level): Iterates through children at a specific level.

Navigation

• next() / prev(): Moves to the next/previous cell at the same level along the Hilbert curve. These do not wrap around between faces.
• next_wrap() / prev_wrap(): Moves to the next/previous cell and does wrap around between faces. Do not use these for standard iteration with child_begin()/child_end().
• advance(int64 steps) / advance_wrap(int64 steps): Moves a specific number of steps along the curve.

// Iterating children
for(S2CellId c = id.child_begin(); c != id.child_end(); c = c.next()) {
    // ...
}

// Iterating all cells at a specific level
for(S2CellId c = S2CellId::Begin(10); c != S2CellId::End(10); c = c.next()) {
    // ...
}

The S2EdgeIndex class allows you to quickly find which edges in a set $S$ might intersect or touch a query edge $(a, b)$.

Implementation

To use it, you must subclass S2EdgeIndex and implement three virtual functions:

1. num_edges()
2. edge_from()
3. edge_to()

Optimization Tip: Instead of using the virtual edge_from() and edge_to() in your query loop, implement a non-virtual GetEdge(int index, S2Point const** from, S2Point const** to) in your subclass to avoid virtual function overhead.

Usage Pattern

Use the GetCandidates(a, b) iterator to retrieve potential matches.

MyS2EdgeIndex edge_index; // Your subclass
MyS2EdgeIndex::Iterator it(&edge_index);
S2Point const *from, *to;

// GetCandidates returns edges that might touch or cross (a, b)
for (it.GetCandidates(a, b); !it.Done(); it.Next()) {
    edge_index.GetEdge(it.Index(), &from, &to);
    // Perform robust crossing check here
}

Performance Tuning

If you know how many times you will call GetCandidates, use PredictAdditionalCalls(n) to help the index decide when to build its internal quad tree, preventing wasted time on brute-force searches.

MyS2EdgeIndex edge_index;
MyS2EdgeIndex::Iterator it(&edge_index);
S2Point const* from;
S2Point const* to;
for (it.GetCandidates(a, b); !it.Done(); it.Next()) {
  edge_index.GetEdge(it.Index(), &from, &to);
  // ... RobustCrossing(a,b, from,to) ...
}