Alex Szalay, Gyorgy Fekete, Tamas Budavari, Jim Gray, Adrian Pope, Ani Thakar, August 2003
The Problem
The spectroscopic survey will consist of about 2000 circular Tiles, about 1.5
degrees radius each, which contain the objects for a given spectroscopic observation. They will have overlaps, where the efficiency of the tiling is higher. At the same time, objects are not targeted/tiled uniformly over the plate; there are rectangular regions on the sky, tiBoundaries, which enclose the regions where objects were tiled. Some tiBoundaries are positive, others are negative (masks or holes.) These form rather complex intersections.
Definitions: Sectors, Regions and Nodes

Convex is the intersection of one or more circles, with a depth: the
number of circles involved. If we have two intersection circles, A and B, then
both (A) and (B) are a convex of depth 1, their intersection (A) (B) is also a
convex, but of depth 2. We call these simple convexes wedges.
 Region is the union of convex areas.
 Sector is a plate wedge modified by intersections with overlapping
tiBoundary regions. If the tiBoundary regions are complex (multiple
convexes) or if they are holes (isMask=1), then the resulting sector is also
complex (a region of multiple convexes). As such a sector is just a single
convex. Tiling boundaries do not add any depth to the sectors; they just
truncate them to fit in the boundary.
Figure 1 (left). A has a blue
boundary, B has the red boundary, both Regions of depth 1. Their intersection
is yellow, a Region of depth 2. The crescent shaded in blue and green are the
two Sectors of depth 1, and the yellow area is a Sector of depth 2. Nodes are
purple dots.
Figure 2 (right). This schematic
figure shows how the tiles and tilling rectangles can intersect to form
Sectors. On the figure we have a layout that has sectors of various depths,
depth 1 is gray, depth 2 is light blue, depth 3 is yellow and depth 4 is
magenta. The sectors are also clipped by the boundary.
Algorithm
We really want the sectors, but it is easier to compute wedges first, then
sectors, then sectors minus tiBoundary masks. In doing this we have some
very useful tools at our disposal:
Regions can be described in many ways but here are the two we use:
 CIRCLE J2000 ra dec radiusArcMin
  this is the Equatorial easy form of a circle.
 REGION CONVEX [ x y z c]+4
  this is the normal form
Corresponding SQL functions:
 fHtmToNormalForm(region)
 > simplified region
If the region is empty, this is just the string "REGION CONVEX"
This routine discards useless edges, so it is a very useful
routine.
 fNormalizeString(region)
 > region
squeezes out blanks, trailing zeros, and converts 0.0 to 0.0
Ignoring optimizations (which are in the code in the appendix) the algorithm
first builds the wedges table by keeping
a #Tile table of all the processed tiles in a tiles table.
A #TileWedge table that records which tiles are "parents" of each wedge
A #wedge table that has the definition of a wedge (its circles)
For each tile T in the Tiles table
Subtract all tiles in #Tile from T and add that sector to #wedge
Now for each wedge W in #wedge, add WT with depth+1
and add WT with depth to the wedge table,
and delete W from the wedge table.
Now simplify all the new wedges and discard the empty one
using the fHtmToNormalForm function
Along the way, maintain the #TileWedge table.
Add T to #Tile
Great, we have the wedges and they are added to the Region, and Convex table. The depth is kept in the stripe column.
Now to compute the sectors, we do more or less the same thing.
For each wedge, call fGetOverlappingRegions(wedge,'TIGEOM',0)
These are all the regions that overlap this wedge.
Intersect this wedge with each region that has isMask=0
to create a sset of new wedges
Call fHtmToNormalForm function on each of these and discard the null ones.
Intersect each of the surviving wedges with the NEGATIVE of each
overlapping region that has isMask=1.
Call fHtmToNormalForm function on each of these and discard the null ones.
Great, we have the sectors and they are added to the Region, and Convex table.
