# Quad-sphere Bins

*
Note that since the text and image below were created we have
switched to using quadsphere level-6 bins for searches. Each
level-6 bin covers the same area as 4 level-7 bins.
*

The specification of geographical areas of interest in the ocean color browser is done in terms of equal area bins defined using the quad-sphere binning scheme at level 7. These bins are roughly 72 kilometers across.

The example image below has been marked with the quad-sphere,
level-7 bin boundaries to give you a better idea of their
size.

Some programs that search for satellite data granules implement
their geographical searches in terms of corner coordinates or
coordinate extrema (i.e. maximum and minimum latitude and longitude).
Such searches will often yield more "false positive"
results than this interface. The reason for this is explained
by the image below. (Clicking on the image will download a larger version.)

Sometimes a scene such as A2006067152000.L2_LAC (shown above)
will be considered within a user's area of interest (red outline)
if its coverage is defined by its coordinate extrema (blue outline);
note that the blue and red outlines overlap. The same scene will
be considered outside the user's area of interest, however, if both
area of interest and scene coverage are defined in terms of quadsphere
level-6 bins (dark green and dark brown outlines). The
https://oceancolor.gsfc.nasa.gov/cgi/browse.pl interface implements
scene searches using this latter method and therefore may not always
return as many matches as searches based on the former method.

A more formal definition of the quad-sphere binning scheme follows.

ROUTINE TO COMPUTE QUAD-SPHERE BIN NUMBER FROM LATITUDE AND LONGITUDE Program logic generated by: Frederick S. Patt / General Sciences Corporation March 6, 1992 Quad Sphere The Earth's surface is projected onto the faces of an inscribed cube using a curvilinear projection which preserves area. The sphere is divided into six equal areas which correspond to the faces of the cube. The vertices of the cube correspond to the cartesian coordinates defined by |x|=|y|=|z| on the unit sphere. The cube is oriented with one face normal to the North Pole and one face centered on the Greenwich meridian. The faces of the cube are divided into square bins, where the number of bins along each edge is a power of 2, selected to produce the desired bin size. Thus the number of bins on each face is 2**(2*N), where N is the binning level, and the total number of bins is 6*2**(2*N). For example, a level of 10 gives 1024x1024 bins on each face and 6291456 (6*2**20) total bins, and on the Earth's surface the bins are 81 km**2 in size. The bins are numbered serially, and the bin numbers are determined as follows. The total number of bits required for the bin numbers at level N is 2*N+3, where the 3 MSBs are used for the face numbers and the remaining bits are used to number the bins within each face. The faces are numbered 0-5 with 0 being the North face, 1 through 4 being equatorial with 1 corresponding to Greenwich, and 5 being South. Thus at level 10, face 0 has bin numbers 0-1048575, face 1 has numbers 1048576-2097151, etc. Within each face the bins are numbered serially from one corner (the convention is to start at the "lower left") to the opposite corner, with the ordering such that each pair of bits corresponds to a level of bin resolution. This ordering in effect is a two-dimensional binary tree, which is referred to as the quad-tree The conversion between bin numbers and coordinates is straightforward. The maximum practical bin level is 14, which uses 31 bits in a 32-bit integer and results in a bin size of 0.32 km**2. The quad sphere limits the allowable bin sizes by requiring the bin dimenension of the cube face to be a power of 2, due to the binary indexing scheme. The advantage is that the bin numbering allows the resolution to be changed (by factors of two) simply by adding or deleting LSBs. This is particularly useful if it is desired to increase the bin size, for example to compare maps with different resolutions. This is performed simply by dividing the bin numbers by four for each factor of two increase in bin size. The quad sphere faces can be displayed individually without remapping, with moderate distortion in the corners of the faces. The quad sphere has an advantage in that the binary numbering scheme allows contiguous subsets of bins (either whole faces or quadrants of faces) to be accessed by simply specifying a range of bin numbers. High-Level Logic: 1. Compute cartisian coordinates from LAT and LON 2. Determine face number and select coordinates for projection 3. Compute face coordinates (u,v) from cartesian coordinates 4. Compute pixel number from face coordinates using level number Detailed Logic: 1. COMPUTE CARTESIAN COORDINATES (X,Y,Z) FROM LAT AND LON X = COS(LAT)*COS(LON) Y = COS(LAT)*SIN(LON) Z = SIN(LAT) 2. DETERMINE FACE NUMBER AND SELECT COORDINATES (Q,R,S) FOR PROJECTION; FACES ARE NUMBERD SUCH THAT Z AXIS IS NORMAL TO FACE 0 AND X AXIS IS NORMAL TO FACE 1; PROJECTION COORDINATES ARE CHOSEN SUCH THAT Q IS NORMAL TO CUBE FACE. IF ((ABS(Z).GE.ABS(X)).AND.((ABS(Z).GE.ABS(Y)) THEN IF (Z.GT.0.) THEN IFACE = 0 Q = Z R = Y S = -X ELSE IFACE = 5 Q = -Z R = Y S = X ELSE IF (ABS(X).GE.ABS(Y) THEN IF (X.GT.0.) THEN IFACE = 1 Q = X R = Y S = Z ELSE IFACE = 3 Q = -X R = -Y S = Z ELSE IF (Y.GT.0.) THEN IFACE = 2 Q = Y R = -X S = Z ELSE IFACE = 4 Q = -Y R = X S = Z END IF 3. COMPUTE FACE COORDINATES (U,V) FROM CARTESIAN COORDINATES PROJECTION EQUATIONS ASSUME KNOWLEDGE OF LARGER OF (R,S) IF (ABS(R).GE.ABS(S)) THEN COMPUTE (U,V) FROM (Q,R,S) U = SQRT((1.-Q)/(1.-1./SQRT(2.+(S/R)**2))) V = U*(12./PI)*(ATAN(S/ABS(R))-ASIN(S/SQRT(2.*(R*R+S*S)))) U = U*SIGN(R) ELSE COMPUTE (V,U) FROM (Q,S,R) V = SQRT((1.-Q)/(1.-1./SQRT(2.+(R/S)**2))) U = V*(12./PI)*(ATAN(R/ABS(S))-ASIN(R/SQRT(2.*(R*R+S*S)))) V = V*SIGN(S) END IF 4. COMPUTE PIXEL NUMBER FROM FACE COORDINATES USING LEVEL NUMBER Convert (U,V) from range of (-1,+1) to (0,2**LEV-1) IU = 2**LEV*(U+1.)/2. IV = 2**LEV*(V+1.)/2. Perform edge check to protect against invalid bin numbers IF (IU.GE.2**LEV) IU = 2**LEV - 1 IF (IV.GE.2**LEV) IV = 2**LEV - 1 IF (IU.LT.0) IU = 0 IF (IV.LT.0) IV = 0 Use lookup table to convert indices (IU,IV) to bin number on face Note that table array is used twice (for low and high bits) IU1 = IU/128 IU2 = IU - IU1*128 IV1 = IV/128 IV2 = IV - IV1*128 BIN = TAB(IU1)*16384 + TAB(IU2) + TAB(IV1)*32768 + TAB(IV2)*2 Add face number as high order bits BIN = BIN + IFACE*2**(2*LEV) END DETAILED LOGIC INCLUDE ARRAY TAB(128) USED BY PROGRAM FOR BIN NUMBER COMPUTATION The entries in this table are generated by taking the binary representations of integers 0 to 127 and inserting an extra 0 bit between each pair of binary bits. This allows the U and V coordinate indicies to be merged into a single bin number by multiplying the V index by 2 and adding them together. Note that array elements whose index is a power of 2 are equal to the index squared. Thus, TAB(0) = 0 TAB(1) = 1 TAB(2) = 4 TAB(3) = 5 TAB(4) = 16 TAB(5) = 17 TAB(6) = 20 TAB(7) = 21 TAB(8) = 64 . . . TAB(125) = 5457 TAB(126) = 5460 TAB(127) = 5461 END INCLUDE