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° | | |
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
- 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 user-supplied 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 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 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]