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

[Jason Harris]

Hi,

James Bowlin wrote:
> I feel like we are close to converging here.  You have won me over to keeping
> the component/composite model.  But I would dearly love to change those long
> and fairly redundant names.  Perhaps XyzComponent and XyzComposite could
> become either simply Xyz and XyzIndex, or a bit longer: XyzItem and XyzIndex.
> Or, for constellation lines and the Milky Way, the components could become
> ConstellationLinesPolygon and MilkyWayPolygon since is what they are. The
> COMPonent and COMPosite names make my head swim a bit and requires me to
> think twice every time I tab-complete a filename.  
> 
I understand your point...but there are reasons not to rename the 
classes, other than inertia.  One is that the Composite/Component model 
is a well-known design pattern, and programmers reading the code will 
recognize instantly what the SkyComposite code means just from the 
classnames.  A wise programmer once said, "code is written once, but 
read many times"  So, it makes sense to give a lot more preference to 
readable code over easy-to-write code.  XyzItem and XyzIndex could work, 
but it might be confusing, since we're talking about adding a SkyIndex 
class handling HTM  stuff, that is unrelated to the C/C model.  Also, 
"StarItem" sounds like it encapsulate a single star, not the ensemble of 
all stars.  StarComponent is more indicative of this.

> I think it would be appropriate to change the class names one at a times
> as we move components over to the indexing model
> 
Actually, I'd rather decide on a renaming scheme and do it all at once, 
if we're going to do it.  If people really want the name change, I'd 
suggest maybe changing "Composite" to "Group" and leaving "Component" 
alone.  I'd like to hear what Thomas thinks though.

> Scheme 1) SkyRegion index
>   The index is stored in a single array of SkyRegion objects.  Each
>   SkyRegion contains a QList (or other list) for every type of object
>   drawn.  This scheme would probably require the least changes to the
>   current code base.  The draw() methods would become static class
>   methods in the component classes.  the composite classes go away.
> 
> Scheme 2) Static component class indices
>   Each component stores its own index in a static class data member.
>   The draw routines remain static class methods.  The composite classes
>   go away.
> 
No, the composites can't go away.  Have a look at the README file in the 
skycomponents dir.  We either have the C/C hierarchy or not.  Without 
the Composites, we lose just about all of the benefits of the design 
pattern.

> Scheme 3) Composite instance (now index) indices
>   The indices and draw methods move from the the component classes to the
>   composite (now index) instances.  The benefit of the scheme is that we
>   retain the message passing of the c/c model.
> 
> I must say I am a little concerned about all of the extra dereferencing
> required in schemes (2) and (3).  I realize that processors have
> instructions to do this quickly, my concern is that it is going to make
> it impossible for the processors to cache our data.
> 
> This leads me to propose a fourth scheme where the index is returned to
> an array of SkyRegions in the SkyIndex, but moves the draw routines to
> the composites.  This would give us the message passing benefits of the
> c/c model but give us the data coherency of the original scheme I proposed:
> 
> Scheme 4) SkyRegion Index, composite drawing
> 
> I'd be willing to start out with either scheme (3) or scheme (4).  They
> are very similar and I cannot predict if there would be a substantial
> speed difference between the two.  If there is a speed difference, I don't
> know which one would be faster.  Both schemes retain the current c/c model
> but I would dearly love to change the names of the files and the classes.
> 
> 
It doesn't make sense to move code to the Composites.  They are just 
containers that pass messages to their child Components.


I believe this is what we are iterating toward based on your second email:

Scheme 5) Each Component[1] stores its objects in a QHash (or other 
container), indexed by HTM ID numbers.  Each element of the QHash is a 
QList containing the objects in that particular HTM region.  We don't 
need a SkyRegion class.

[1]: except Components which only contain one object, of course.  For 
them we only need an int member to store the ID number of the HTM region 
containing the object.

Pseudocode (with exaggerated function names for clarity):

void SkyComponent::init() {
   //read lines from the data file to get the RA, Dec and other info
   //needed to instantiate the SkyObject
   for each line in datafile {
     parse_data_line( type, ra, dec, mag, name );
     SkyObject *o = new SkyObject( type, ra, dec, mag, name );

     int htmIndex = get_HTM_index_from_coords( ra, dec );

     objectHash[ htmIndex ].append( o );
   }
}

void SkyComponent::draw( QList<int> &visibleIndexes ) {
   foreach( int index, visibleIndexes )
     foreach( SkyObject *o, objectHash[ index ] )
       o->draw();
}