NNX07AV81G



Framework For Fast Spatial Searches Using The Hierarchical Triangular Mesh

Year 1 Progress Report





Progress on the different work packages is described below.



WP0:

Regions are made up of unions of convexes, which are intersections

of halfspaces. This is what we call the normal form of describing arbitrary

shapes, areas of interest on the surface of the sphere.

For example, STC Regions, Hubble Deep Field footprints are made up of

overlapping polygons consisting of hundreds of regions. Previous versions of

HTM used a simplistic approach for computing trinagles that were later

discarded because they were completely covered by unions of overlapping

convexes. A set of useful tools comprising the Spherical Library was

designed to manipulate regions defined in this normal form. Besides precise

compuations of areas of complex overlapping regions, it further provides the

calculation of the outline of the region making it possible to construct

the HTM cover of a region more efficiently than before. The outline itself is 

the collection of arcs that make up the edges of NON_OVERLAPPING patches

(slices of pie-shaped sections of  a halfspace).



The SphericalHTM library is modified to expoit the benefits offered by the

capabilities of the aforementioned Spherical Library.



WP1: C# Implementation

Both the SphericalLib and SphericalHTM Libraries have been implemented and

tested, are available for use now. Unit testing harnesses are included for 

both packages. We have invented an algorithm that computes only the OUTER

edges of pathes so that arcs that are shared by two adjacent patches are

eliminated. This is significant, because the current implementation can be

improved by reducing the number unnecessary arcs for HTM Cover computation

making the cover calculation even faster.



WP2: C++ Port

WP3: Java port

Java and C++ ports are moved to year 2 to allow adequate testing of the

new outline generation functions and verify the implementation with a unit test

harness that contains both hand-made examples of extreme and ill-conditioned

cases as well as very complex masks from the ACS footprint.



WP6: Footprint services (N/A for year 1)

WP7: Visualization tools

     Web applications as well as stand-alone applications are available

     and are used extensively for development and as a verification tool.

     

WP8: Web site

     http://skyserver.org/HTM/index.html reflects the current condition

     of the HTM and Spatial libraries and includes tutorials and primers

     for their use.

     (though the date of most recent update is wrong, probably)

- - - -