Sphere Partitioning Algorithm

The following describes how the Sphere Partitioning Algorithm generates a tree data structure for a given set of polygons on a sphere. This tree structure allows to easily search all cells in the given data set that overlaps with another given cell or point (set of cells or points).

Generation of tree structure

to partition a set of polygons on the sphere the following data structure can be constructed:

• c = center of sphere
• S = set of all points

Description for a routine that generates the tree

recurspart(P, v, t)

1. Set p to balance point of P
2. Compute great circle L with base plane collinear to |c p| and orthogonal to v
3. Partition data
   1. Set I to subset of S intersecting L
   2. Set T to subset of S/I with positive scalar product to normal vector of L
      • Ti = recurspart(T, norm(L)) if |T| > threshold t else Ti = list(T)
   3. Set U to subset of S/I with negative scalar product to normal vector of L
      • Ui = recurspart(U, norm(L)) if |U| > threshold t else Ui = list(U)
4. return node(list(I), Ti, Ui, L, alpha=angle over L containing I)

Observations

• I, T, U and form a partition of S
• first L is orthogonal to equator, i.e. a longitude circle
• initial call: recurspart(S, (0,0,1), t)

Searching in the tree structure

Description for a routine that searches for a list of cells

search(n, p)

1. if n is leaf
   1. P = search_list(n, p)
2. else
   1. P = {}
   2. if p in n.alpha
      • P = P united search_list(n.I, p)
   3. if p * norm(n.L) > 0
      • P = P united search(n.Ti, p)
   4. else if p * norm(n.L) < 0
      • P = P united search(n.Ui, p)
3. return P

Observations

• returns list of matching polygons