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 size|Images| |-1 |0 |1 |180.00000 |180.00000 |200° ||| |0 |9 |6 |54.73561 |45.00000 |83° |A|Z| |1 |36 |24 |30.36119 |21.79319 |41° |A|Z| |2 |144 |96 |16.40309 |9.61290 |20° |A|Z| |3 |576 |384 |8.63959 |4.55775 |10° |A|Z| |4 |2304 |1536 |4.44936 |2.21341 | ||| |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 2-level 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


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:

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 user-supplied function fct is called with the arguments qboxno, the number of the qbox selected, and a status which can be

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 x-axis (to East) and box_dim[10] along y-axis. 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 , 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]