
Geometrical Querying
We want to have a generic possibility to intersect the HTM with any
given surface on the sphere. For a certain area, we want to get all
HTM nodes of a given depth that are either completely or partially
covered by it. We would like to know for each triangle which category
it falls into  completely contained in the area, partially contained
or not at all. In this section, we give the geometry primitives that
can be used to define any area on the sphere. These primitives can
easily be intersected with the HTM nodes to decide into which category
they fall. We give the outline of the algorithms that can be used to
deduce the HTM category for any area composed of the geometry
primitives.
Geometry Definition
Constraints
The constraint is our basic geometry primitive. It is
a cap on the unit sphere. We get a constraint by slicing it
off the sphere with a plane. Any constraint can be characterized
by the direction of the plane \vv and its distance d from the origin:
> >
c := { v ; d } v = 1 ; 1 < d < 1
(6)
We allow for 'negative' constraints d<0, which cover more than half of the
spherical surface. They look like 'holes' on the sphere. The sign of the
constraint is defined to be the sign of d:
sign(c) := negative d < 0
zero d = 0
positive d > 0
(7)
We also define the opening angle of a constraint:
phi_{c} = arccos(d)
(8)
Examples: {v = (0,0,1) ; d = 0.5 } defines the cap north of 30^{o}
latitude north. {v = (0,0,1); d = 0.5 } defines everything but the
same cap.
Convexes
We define a convex as the logical AND of constraints, i.e. the
intersection of caps on the sphere:
x := c_{1} && c_{2} && ··· && c_{n} n in N^{+}
(9)
Such a geometry is a convex in 3D but not necessarily a convex area on
the spherical surface.
As an example, the convex { (0,0,1) ; 0.01} && { (0,0,1)
; 0.01} defines a narrow strip around the equator. It is not even
true that convexes are always a contiguous area on the sphere. Imagine
the convex given by the intersection of two greatcircle strips that are
not in the same plane  the resulting convex is given by two disjoint
areas where the strips meet.
Consider as another example a cube centered
around the origin whose corner points are barely outside the unit
sphere. Then the corresponding convex on the sphere is given by the 8
segments just around the cube corners. Note that all these convexes
are composed of negative constraints.
However, convexes that are composed entirely of positive and zero constraints always define a convex area on the sphere, which are easier to handle. Thus, it makes sense to define a sign for the convexes too:
sign(x) := negative c_{i} all negative or zero
zero c_{i} all zero
positive c_{i} all positive or zero
mixed} at least one positive and one negative constraint
(10)
The sign will be important when we actually calculate the
intersections with the HTM.
Domains
We define a domain to be logical OR of convexes:
d := x_{1}  x_{2}  ···  x_{n} n in N^{+}
(11)
Thus a single domain can represent any complicated area on the sphere.
If we devise a generic method to intersect domains with the HTM triangles,
we have a powerful indexing tool at hand.
Simplifications
Convexes and domains may contain redundant constraints that can be
localized and eradicated. The most trivial cases are the following:
Consider a convex made out of two constraints c_{1} and c_{2} with
opening angles varphi_{c1} and varphi_{ c2}
respectively. Define the angle between them as
> >
v_{c1}· v_{c2} = cos(theta_{ c1 c2})
(12)
 If both constraints are non negative, we can drop c_{2} if
varphi_{c1} >= varphi_{ c2} + theta_{ c1c2}
 If both constraints are negative or zero, we can drop c_{2} if
varphi_{ c2} >= varphi_{ c1} + theta_{c1c2 }
 And we can drop the whole convex if
varphi_{c1} + varphi_{c2} <= theta_{c1c2}}
These simplifications are true even if there are more than two
constraints in the convex, we can check each pair of convexes for the
above cases.
For zero convexes, where all constraints are great circles, we can
easily do more simplifications. The above cases only would apply if
we have two exactly opposing half spheres, i.e. v_{1} = v_{2} .
Zeroconvexes can be drawn as a polygon on the
sphere. The corners of the polygon can be localized using the
following algorithm (Nomenclature : L is a list containing all
constraints that have been already processed, P is a list of
the polygon corners that are determined one by one):
 1. Assume there are n constraints in the convex.
Start with constraint c_{i}, i=0.
 2. Get the intersection points with convex c_{j} ,
j not in L and j not= i, which for zero constraints
are given by the cross product of the two constraint vectors
> > >
W_{1,2} = ±v_{i} X v_{j}
 3. Check whether any of the two intersection points lies inside all
the other constraints, i.e. if
> >
W_{1,2}· v_{k} > 0 k not= i,j
 4. If one of the points w_{1,2} does lie within all
constraints, append it to the list of polygon corners P, insert
i into the list of visited constraints L and continue at
point 2 with i=j.
 5. If a constraint i does not fulfill point 4, i.e. there are no
intersection points to be found that lie within all other convexes, it
means that the polygon of the convex lies completely inside or
completely outside of c_{i} . Test for one of the already known points
in P whether it is inside c_{i} (if P is empty, just
continue and come back to this constraint later). If it is inside,
drop c_{i}, if it is outside, drop the entire convex.
 6. If there are no j not in L to be found, we are
done, P contains an ordered list of all polygon corners.
