[Kstars-devel] Ideas for Adding a Spatial Index to KStars

[Jason Harris]

Hi James,

It's my bedtime, so a detailed reply will have to wait until  
tomorrow.  Just a few notes here.  This looks really good, BTW.

On Jun 19, 2006, at 11:18 PM, James Bowlin wrote:
> Notes:
>  1) I don't know if the QList<> syntax above is correct.  Even if  
> it is
>     correct I'm not certain a QList<> is the best structure to use  
> here.
>     The key point is that these routines return iterators that return
>     SkyRegions.
>
It's correct.  Don't know if it's the best choice either, but I think  
it will be easy to switch to other container types and test them out.

>  2) I've resisted the temptation to have any add() methods in SkyIndex
>     that would combine looking up the index of an object and adding  
> that
>     object to a SkyRegion in one step.  The SkyIndex doesn't know  
> anything
>     about what is in the sky expect for the SkyRegions it returns  
> and the
>     SkyPoints it gets sent that contain the [ra, dec] coordinates  
> it needs
>     to find the regions.
>
>  3) I don't know if the "index" prefix is the best name for the  
> routines
>     above.  Other possibilities are "find", "findIndex", and  
> "intersect".
>     I welcome suggestions for what to name things.
>
index is an ok prefix for me; I'll let you know if I think of  
something else.

>  4) The setView() and getView() functions do the same things as the
>     indexCircle() function but in two separate steps.  The idea is  
> that
>     setView() would be called once to generate a list of all regions
>     that are at least partially visible on the screen then the  
> SkyComponents
>     would all call getView() to get a list of all the objects they  
> need to
>     draw.
>
Not sure I'm completely following this yet, but I'm sure It'll be  
clear soon enough :)

>     QLinkedList<SolarSystemComponent *> ????;
>
There's no SolarSystemComponent; we actually have two base classes to  
deal with: SolarSystemSingleComponent and SolarSystemListComponent

> Notes:
>  1) I realize it is unusual to have public data members.  If you would
>     prefer, we can add public accessors for all of these data members
>     but I don't see that we would gain anything by doing that.
>
I agree, no point in doing that.  We could also make them private  
members and use the "friend" keyword to specify classes that are  
allowed to access these members.

>  2) The lists don't need to be the same.  In the example above the  
> stars
>     member is a list of actual StarObject objects while the others are
>     lists of pointers.  The SkyRegion is just a container.  All the  
> lists
>     can be different. Each component can use a list that best suits  
> its
>     needs.
>
Why do you want a list of actual StarObjects?

> One drawback I see with this approach is that it will create a  
> little header
> file hell.  The SkyRegion header depends on the SkyComponent  
> headers of all
> the SkyComponents it contains.  But all of those SkyComponents will  
> depend
> upon the SkyRegion header thus a change to any one of these header  
> files will
> cause all of the indexed SkyComponents to need to be recompiled.   
> We could
> get around this by using void* pointers and a lot of type casting  
> but I don't
> think that is a good idea here.
>
Actually, I'm pretty sure you can avoid this by putting forward class  
declarations in the headers, and putting the #includes in the source- 
code files.  This may require that the QLists contain pointer types,  
IIRC.

> Putting it all together
> -----------------------
>
> There are two major operations the spatial index is involved with:  
> adding
> objects to the index and the drawing of objects.  It could also be  
> useful
> for finding objects near the cursor, or all the objects on the  
> screen but
> those operations are simpler than drawing (I think) and their  
> implementation
> should be obvious.
>
> Every indexed SkyComponent class will need to know about SkyRegions  
> and
> also needs to contain a pointer to the SkyIndex.  I think the simplest
> thing is to have the SkyIndex pointer be a static class member in the
> SkyComponent classes.
>
>
> Adding objects to the index
> ---------------------------
>
> The code to add an object to the index, like most of the other code  
> that
> uses the index, would reside inside the SkyComponent cpp file for that
> particular kind of object.  For example, the current code for creating
> a new StarObject is:
>
>     StarObject *o = new StarObject( ... );
>     o->EquatorialToHorizontal( data()->lst(), data()->geo()->lat() );
>     objectList().append( o );
>
> This would change to something like:
>
>     StarObject *o = new StarObject( ... );
>     o->EquatorialToHorizontal( data()->lst(), data()->geo()->lat() );
>     SkyRegion *region = skyIndex->indexPoint( o->ra(), o->dec() );
>     region->append( o );
>
I'm kind of missing why we are keeping the SkyComposite hierarchy  
here.  Your SkyRegions have a simple, flat scheme for storing the  
objects in its own type-specific lists.  So there would seem to be no  
point in having the SkyMapComposite at all.  An alternative would be  
for each SkyRegion to have its *own* SkyMapComposite.  Basically, use  
the existing hierarchical object-storing scheme instead of your  
simple flat storage scheme.  I don't see the need to keep both, but  
it's late so maybe I'm missing it :)

Anyway, I need to be unconscious :).  More tomorrow...

regards,
Jason