- HTM

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


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
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
We also define the opening angle of a constraint:
          phic = arccos(d)
Examples: {v = (0,0,1) ; d = 0.5 } defines the cap north of 30o latitude north. {v = (0,0,-1); d = -0.5 } defines everything but the same cap.


We define a convex as the logical AND of constraints, i.e. the intersection of caps on the sphere:

          x := c1  &&  c2  &&  ···   &&  cn                 n in N+
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 great-circle 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     ci  all negative or zero
               zero         ci  all zero
               positive     ci  all positive or zero
               mixed}       at least one positive and one negative constraint
The sign will be important when we actually calculate the intersections with the HTM.


We define a domain to be logical OR of convexes:
d := x1  ||  x2  ||   ···       ||  xn            n in  N+ 
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.


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 c1 and c2 with opening angles varphic1 and varphi c2 respectively. Define the angle between them as
          ->   ->
          vc1· vc2 = cos(theta c1 c2) 
  • If both constraints are non negative, we can drop c2 if
          varphic1 >= varphi c2 + theta c1c2 
  • If both constraints are negative or zero, we can drop c2 if
          varphi c2 >= varphi c1 + thetac1c2 
  • And we can drop the whole convex if
          varphic1 + varphic2 <= thetac1c2}
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. v1 = -v2 . Zero-convexes 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 ci, i=0.
2. Get the intersection points with convex cj , j not in L and j not= i, which for zero constraints are given by the cross product of the two constraint vectors
          ->       ->  ->
          W1,2 = ±|vi X vj|
3. Check whether any of the two intersection points lies inside all the other constraints, i.e. if
          ->   -> 
          W1,2· vk  > 0              k not= i,j
4. If one of the points w1,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 ci . Test for one of the already known points in P whether it is inside ci (if P is empty, just continue and come back to this constraint later). If it is inside, drop ci, 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.

William O'Mullane
Last Modified :Tuesday, March 30, 2004 at 6:59:43 PM , $Revision 1.2 $