[Kstars-devel] HTM questions

[James Bowlin]

On Sun October 14 2007, you wrote:
> > > 2) get neighbours of trixel in defined distance (ie get all
> > > objects in distance from point)
> >
> > This is done by creating an index of the objects.  For point
> > objects, the index is an array (or hash) of lists of pointers to
> > the objects. The trixels are the index of the array.
>
> So if I understand correctly, there is no math function for getting
> neigbourh trixels,  

I don't know.  We never needed it so I didn't look.

> you are just using precallculated tables? 

For the stars (in kstars/skycomponents/starcomponent.cpp) there is
a data member called m_starIndex.  The size of this array is the number
of trixels.  Each element of the array is a list of pointers to star
objects.  The list contains all of the stars that are in a given
trixel.  In a relational database you would use a table linking
trixels to stars with a one (trixel) to many (stars) relationship.

We find all of the stars within a circular aperture by using the
HTM to get a list of all of the trixels needed to cover the aperture
and then for each trixel in that list we use the m_starIndex array to
get all of the stars in that trixel.

If your are using a level-10 mesh then the use of an array might
be impractical since it would have to have 8M elements.  We left
the mesh level as a free (compile time) parameter and then tuned it
to optimize for speed (smaller was faster).  But maybe the problem
you are working on is significantly different from ours.  Our primary
use of the index was to speed up the display of the sky by culling
out objects that cannot possibly be on-screen.

We only use point lookups when we create our indexes.  When we
query the indexes we _always_ use the HTM to find the trixels that
cover a circular aperture, and then process the list of trixels
returned, even when looking for objects close to a point.  One
reason for this is that the index is never 100% accurate due to
both refraction and proper motion of the stars.  Using a circle
instead of a point allows us to add a safety factor to compensate.
But even without these inaccuracies, I would recommend always using
a circle when you do queries otherwise you will run into situations
where the point you are interested is right near a border but you
are ignoring objects that aren't in its trixel.

-- 
Peace, James