[Kstars-devel] HTM questions

[James Bowlin]

On Sun October 14 2007, Jan Kotek wrote:
> 1) convert area (ellipse, pollygon) to set of trixels

In kstars/kstars/htm/HTMesh.cpp there is code that does this for
circles, lines, triangles and quadrilaterals.  For higher order
polygons and segmented lines there are crude methods in
kstars/skycomponents/skymesh.cpp that make repeated calls to
the above HTMesh methods, storing the resulting trixels in a QHash.

The higher order polygon code could probably be vastly improved.
If you come up with a better way to handle non-convex polygons,
please let us know about it.  Also, I think the code in HTMesh.cpp
that handles single line segments could also be improved.

This code is working for us for now but it may need to be tweaked
before it can work for you.  It is not yet a general purpose solution.

We had no need for ellipses so I didn't explore for a solution.
I suggest simply using a circle that contains the ellipse.  This
is fast even though it might include a few extra trixels.  In
general, the gains from the HTM index are so great that a few
extra trixels here and there are no big deal.  Our higher order
polygon code also generates extra trixels for non-convex polygons
but the extremely minor benefits from fixing this didn't seem
to warrant the extra coding effort.  

In KStars, after initialization, the only HTM actions we perform
are point and circle lookups which are both very fast.  This is
why we didn't put in a lot of effort into optimizing the more
complicated indexing.


> 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.  You use the HTM to get a list
of trixels in a circle and look up each trixel in the index.
This is well explained (I hope) in an almost tutorial fashion in
the file kstars/skycomponents/README.indexing. Feedback on the 
documentation would be welcome.


> 3) convert trixel to ra dec coordinates (ie inverse function).

An example of this exists at the bottom of skymesh.cpp which looks
up the (ra, dec) coordinates of the vertices of trixels and then
plots the outlines.  You can get KStars to draw the outlines by 
uncommenting some lines near the bottom of SkyMapComposite::draw()
in the file

kstars/skycomponents/skymapcomposite.cpp

N.B.: Almost all of the comments for the code are in the header files,
not the cpp files so I suggest you look at the header files first to
get an overview before diving into the code.


Thanks for the HEALPix link.  It's GPL'ed which is sweet.  I think
the documentation (and probably the code) is better than the HTM
library we are currently using.  The HTM library seems to be
working well for us so ATM there is no compelling reason for us
to put in the effort needed to convert.  Nonetheless, it is good
for us to know of another library that could be used.

Do you have any idea of how the HEALPix performance compares
with that of HTM?  The equal area property of HEALPix is pretty
but does not provide us with any benefit.  Unless something goes
horribly wrong with the HTM, I think the only reason we would have
for switching would be to boost performance (which really isn't
an issue for us now).


-- 
HTH, James