s2intersect

Documentation

Overview

Package s2intersect efficiently finds common areas shared by sets of S2 CellUnions. Use this package instead of s2.CellUnionFromIntersection when there are 3 or more CellUnions to compare and all intersections are required, as the brute force alternative is exponential in time.

Benchmarks show that direct comparison of a pair of CellUnions is more efficient with respect to both time and memory when using the standard s2.CellUnionFromIntersection function. The benefits of s2intersect arise as the number of potential intersections grows; for n CellUnions, there are 2^n - n - 1 possible intersections (power set excluding single-member sets and the empty set).

Index

• type Intersection
  • func Find(cus []s2.CellUnion) []Intersection

Types

type Intersection

type Intersection struct {
	// Indices refer to the slice of CellUnions passed to Find().
	Indices      []int
	Intersection s2.CellUnion
}

An Intersection describes the intersection of a set of CellUnions.

Intersections returned by Find() are disjoint; i.e. if the Indices of one are a sub set of the Indices of another, the sub-set Intersection will NOT include the CellIDs that are included in the super-set Intersection; for details, see Find() re disjoint Intersections.

func Find

func Find(cus []s2.CellUnion) []Intersection

Find returns the set of all disjoint intersections of the CellUnions. The ordering of the output is undefined.

Whereas the naive approach of finding pairwise intersections is O(n^2) for n CellUnions, and a naive multi-way search is O(2^n), Find() is O(max(i log i, c)) for c Cells constituting i intervals on the Hilbert curve (contiguous Cells form a single interval).

Find calls Normalize() on all CellUnions, the efficiency of which is not considered in the previous calculations.

Note that returned Intersections are disjoint; Cells are only counted towards the most comprehensive Intersection. For example, the intersection of regions A and B will NOT include the area in which regions A, B, _and_ C intersect because {A,B,C} is a super set of {A,B}. Correcting this requires iterating over the power set of all resulting Intersections and "decomposing" them into constituent parts (power sets are O(2^n) for a set of size n).

Consider the following CellUnions, shown as their corresponding intervals on the straightened Hilbert curve. Cells are denoted as = and grouped into 4 for ease of viewing (i.e. the pipes | have no meaning). The resulting Intersections are denoted with the letters X–Z and the disjoint nature of the output is such that Y and Z will not include the Cells that are instead reported in X, even though the respective CellUnions do indeed intersect there. Analogously, each area of the Venn diagram of regions can receive only one label.

0: |====|  ==|    |
1: |==  |   =|=== |
2: |====|====|  ==|
    XXYY   YX   Z

X: {0,1,2}
Y: {0,2}
Z: {1,2}