1 Division of the Sky into recursive Cells (quadtree)
The routines provided in this module all deal with "qboxes".
The qboxes are a way to split the celestial sphere in zones
of approximately same surfaces and extension.
The dichotomic procedure uses the projections (X,Y) of the
directions on the 6 faces of a cube
numbered 1 (z=1), 2 (y=1), 3 (x=1),
4 (x=–1), 5 (y=–1) and 6 (z=–1).
Each cube face is then divided into 4 areas; each area is further
divided into four pieces, etc. The schematic repreentation is:
++
 ^ 
  
 1+>
 (N) x 
 
+++++
 ^  ^   
     (P)  (Q) 
 5+> 3 +> 2+> 4+>
 (R) x  (O) x  x  x 
   v  v 
+++++
 ^ 
 x 
<+ 
 6(S) 
 
++
Illustrations are given in the Aitoff or Zenital
projections.
The number of valid qboxes is

Level Lower qbox# Number of qboxes Max rad. Min rad.
Mean sizeImages
1 0 1 180.00000 180.00000 200° 
0 9 6 54.73561 45.00000 83°
AZ
1 36 24 30.36119 21.79319 41°
AZ
2 144 96 16.40309 9.61290 20°
AZ
3 576 384 8.63959 4.55775 10°
AZ
4 2304 1536 4.44936 2.21341 5° 
5 9216 6144 2.25967 1.08995 150' 
6 36864 24576 1.13891 0.54074 75' 
7 147456 98304 0.57176 0.26930 40' 
8 589824 393216 0.28646 0.13438 20' 
9 2359296 1572864 0.14338 0.06713 10' 
10 9437184 6291456 0.07173 0.03355 5' 
11 37748736 25165824 0.03587 0.01677 150'' 
12 150994944 100663296 0.01794 0.00838 75'' 

where level is a number which can be changed at any time using
qbox_set(level) procedure.
The present implementation assumes that level <=6,
corresponding to a maximum of 16 bits in the qbox number;
this condition can be removed with a redefinition of the
QBOX_BITS definition in this module;
constants can be obtained by compiling the program with the DEBUG
option set to 1.
For a level 6, the qbox number is a short integer with bits
(from left to right)
1ppp xyxy xyxy xyxy.
The leftmost `1' bit allows the recognition of the level;
bits p represent the face number (1 to 6),
x and y the position, expressed with level bits,
along the axises defined above for the face. Going down the hierarchy
therefore just means a left shift of two bits, and adding (or or'ing)
the terminal values 0, 1, 2 or 3.
Qboxes may be edited either as numbers (e.g. 1.300000 which represents,
the cell close to the North Pole with RA between 0 and 6hr in level=6),
or with letters NPOQRS for faces (N=North, O=0h, P=6h, Q=12h, R=18h,
S=South), followed by letters a to p for
2level aggregations, and terminated by a number 0 to 3
if the level is odd.
In this scheme, the names Nmaa and 1.300000 represent
the same cell.
The qbox_next routine is aimed to list all subqboxes
making up a qbox of an upper level.
It must be called a first time with the value of a qbox
(e.g. 9 for a qbox at level 0, or a number in the
range 9216—15359 for level 5); it returns the number of the
first qbox within the "superqbox" (e.g. 36864 for level 6),
and continues the list when the argument to qbox_next is zero.
The selection of valid qboxes makes usage of an `action routine',
a user–supplied function which is called after the tests
and has synopsis routine(qbox_no, status)
where status may take the values
 QBOX_NONE: no object in qbox_no can meet
the position requirements.
 QBOX_ANY: any object in qbox_no meets
the position requirements; there is therfore no need for a test.
 QBOX_SOME: objects in qbox_no may meet
the position requirements; individual tests must be performed.
2 List of Functions
2.1 Projections (gnomonic) onto the 6 faces of a cube
 int tr_pu6(double proj[2], double u[3], int face_no)

converts the projection values to the unit vector u components
 int tr_up6(double u[2], double proj[3], int face_no)

converts the unit vector u into the projection values on the face
of a cube
2.2 Basic Cell Setup
 int qbox_set(int level)

defines the level of the laeves in the quadtree.
By default, the level is set to the deepest level (currently 12)
It returns the currently set level.
 int qbox_get(void)

returns the currently set level.
 int qbox_o(double opos[2])

from a position, expressed in degrees, returns the qbox number
where the position is located.
 int qbox_u(double u[3])

from a position, expressed as his unit vector u,
returns the qbox number where the position is located.
 int qbox__o(int level, double opos[2])

from a position, expressed in degrees, returns the qbox number
at the specified level where the position is located.
 int qbox__u(int level, double u[3])

from a position, expressed as his unit vector u,
returns the qbox number at the specified level
where the position is located.
2.3 Explain Cell Characteristics
 char *qbox2a(int qboxno)

edits the value of a qbox number in ascii form, in an
internal buffer.
 int qbox_a(char *text)

interprets a qbox in ascii form .
 int qbox_level(int qboxno)

returns the level (in range 0..12) implied by the qbox number.
 int qbox_face(int qboxno)

returns a value between 1 and 6 representing
the face of the cube implied by the qbox number.
 int qbox_co(int qboxno, double o_qbox_center[2])

computes into o_qbox_center
the center of a given qbox (degrees)
 int qbox_cu(int qboxno, double u_qbox_center[3])

computes into u_qbox_center
the center of a given qbox as its direction vector u
 double qbox_radius(int qboxno)

returns an upper limit (in degrees) of the radius of a circle
(centered on o_qbox_center returned by qbox_co routine),
which contains the specified qbox.
 double qbox_size(int qboxno)

returns an upper limit (in degrees) of the side of a square
(centered on o_qbox_center returned by qbox_co routine),
which contains the specified qbox.
 double qbox_surf(int qboxno)

returns the surface of the specified qbox.
2.4 Select a set of Cells
The selection of a set of qboxes is done via an action routine,
which has to be passed (via qbox_act). The selection routines,
e.g. qbox_or, are in turn calling this action routine:
 at the leaf (deepest) level when the intersection of
the qbox with the target surface is not void
(status has the value QBOX_ANY or QBOX_SOME)
 at any level level when the intersection of the qbox with the
target surface is void (status has then the value
0 or QBOX_NONE).
The list of selection functions are as follows:
 QBOX_ActionRoutine qbox_act(QBOX_ActionRoutine
fct(int qboxno, int status))

for letting kow what to do with selected qboxes;
the function returns the previously set action routine.
This usersupplied function fct is called with the arguments
qboxno, the number of the qbox selected, and
a status which can be
 0 or QBOX_NONE: there is normally nothing to do.
 QBOX_ANY: any object lying in this qbox matches
the constraints — it is therefore not necessary
to perform further checks from the actual positions
 QBOX_SOME: accurate check from the actual positions
are to be performed on each object lying in this qbox
 int qbox_or(double o[2], double radius)

for a selection around the specified center (in degrees),
within the circle of specified radius
 int qbox_ur(double u[3], double radius)

for a selection around the center specified by its
direction cosines (u),
within the circle of specified radius
 int qbox_ob(double o[2], double box_dim[2])

for a selection around the specified center (in degrees),
within a box of dimensions box_dim[0] along xaxis
(to East) and box_dim[10] along yaxis.
Note that the full sizes of the box are given.
 int qbox_obrot(double o[2], double box_dim[2],
double togal_matrix[3][3])

similar to qbox_ob, but with a rotation matrix.
For instance, a box oriented along galactic coordinates
can be chosen by putting gal_2000 as the third argument.
 int qbox_ra(double ra_range[2])

for a selection between two limits in the first angle
(right ascension) expressed in degrees.
Note that the order of the 2 numbers is important, the
selection [359°1°] covering an interval of 2°,
while [1°359°] covers an interval of 358°
 int qbox_dec(double dec_range[2])

for a selection between two limits in the second angle
(declination) expressed in degrees.
The order here between the 2 numbers does not matter.
 int qbox_lon(double lon_range[2], double togal_matrix[3][3])

for a selection between two limits in a longitude expressed
in a frame which is rotated according to the specified
matrix. The matrix is assumed to provide the transformation
of basic position into the desired longitude:
for instance, a selection in a range of galactic longitude
requires the matrix gal_2000 which converts the equatorial
unit vector into the galactic one.
As for qbox_ra, the order of the 2 numbers matters.
 int qbox_lat(double lat_range[2], double togal_matrix[3][3])

similar to qbox_lon, but for the latitude part.
 int qbox_radec(double ra[2], double dec[2])

for a selection between two limits in the first angle
(right ascension) combined with limits in declination
 int qbox_lonlat(double lon[2], double lat[2], double rm[3][3])

for a selection between two limits in longitude
combined with limits in latitude
3 Example of a Program using Cells
The following short program (qboxtest.c) shows how to use the selection in
a circle around a center:
#include <qbox.h>
#include <stdio.h>
static int my_action(int qboxno, int status)
{
double qbox_center[2] ;
if (!status) /* Cell not selected at all... */
printf("....The qbox %d (%s) is to be ignored\n",
qboxno, qbox2a(qboxno)) ;
else {
qbox_co(qboxno, qbox_center) ;
printf("====The qbox at %010.6f%+010.6f %d (%s) is %s\n",
qbox_center[0], qbox_center[1], qboxno, qbox2a(qboxno),
status == QBOX_ANY ? "(ANY)" : "(to check)") ;
}
return(0) ;
}
main()
{
double radius, center[2] ;
qbox_set(9) ; /* 1.5 million qboxes... */
qbox_act(my_action) ; /* What I do with selected qboxes... */
center[0] = 1.234; center[1] = 78.912 ; /* That's my target */
for (radius=0.01; radius < 100; radius *= 10) {
printf("\n====Select around (%010.6f%+010.6f), radius=%g (hit Ret)",
center[0], center[1], radius) ;
getchar() ;
qbox_or(center, radius) ;
}
}
4 Hierarchical immediate usage
The qbox values are a simple quadtree, i.e.
if qb designates some qbox at a level m,
it includes the the 4 qboxes qb1=qb<<2,
qb1+1, qb1+2 and qb1+3
at level m+1.
Conversely, qboxes may be grouped into the upper cell computed with
qb>>2.
As a simple example, the following program just lists all
qboxes touched by a target defined by its position and radius:
#include <qbox.h>
#include <stdio.h>
/* Target definitions */
static double target_center[2] = { 180., 10. } ; /* 12h, +10deg */
static double target_radius = 0.25; /* 15' radius */
static double target_u[3] ; /* Dir. cosines of Center */
int show_boxes(int boxid)
/*++++++++++++++++
.PURPOSE This function recursively lists all boxes at deepest level.
.RETURNS Number of printed boxes
*/
{
int n, i, qb, u ;
double uc[3], maxr ;
n = 0 ;
if (boxid <= 0) { /* Whole Sky */
for (i=9; i<15; i++) n += show_boxes(i) ;
return (n);
}
qbox_cu(boxid, uc) ; /* Box Center */
maxr = qbox_radius(boxid) + target_radius ;
/* The box has no intersection with the target when the distance
target_center/box_center is larger than the added radiuses */
if (dist_u(uc, target_u) >= maxr) return (0) ;
/* At deepest level, the boxid is matched */
if (qbox_level(boxid) >= qbox_get()) {
printf("OK for %d\n", boxid) ;
return(1) ;
}
/* Recursively find all boxes */
for (qb = boxid<<2, i=4, n=0; i>=0; qb++) n += show_boxes(qb) ;
return(n) ;
}
/* The main program */
main()
{
qbox_set(8) ; /* About 400,000 boxes... */
tr_ou(target_center, target_u) ; /* Get direction cosines */
show_boxes(0) ;
}
5 Header file
<! **Error Opening File: /usr/users/francois/src/as4/qbox.h >
[missing file: /usr/users/francois/src/as4/qbox.h]