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

[Thomas Kabelmann]

Well, I see we talked on cross purposes. I was talking on the base of 
StarComponent and you were talking on base of MilkyWayComponent/Composite. No 
I understand your problem :-)

There are 2 common ways to optimize the components/composites. First way is to 
put all objects in 1 component, as we did in StarComponent, DeepSkyComponent 
etc. Second way is to put some additional logic in the composite. This means 
that instead of simply sending each subcomponent a draw message the composite 
knows which objects really have to draw on the map.

For StarComponent we decided to put all stars in 1 component, because we have 
some thousand stars and this would mean we would have some thousand objects. 
The milkyway.dat has 135 lines, as you wrote in a cross post. I think each 
line represents 1 component. If so, I think it's ok in the modell if the code 
will easier to read and maintain. Now there is an performance hit in drawing. 
So if we decide to leave the current modell, we have the make the composite a 
little bit smarter for drawing. This means we add an addtional indexed list 
to the composite which can be used to send draw messages to the visible 
components. It still remains the problem of setting pen and color in each 
component. This can be solved in moving some common drawing code in the 
composite. Here is some pseudo code to sketch the idea:

Composite::draw()
{
	setPen();
	setColor();
	foreach (visibleComponent v) v.draw();
}

The next thing is the implementation of the index list. We are now so far that 
we want to use a QHash of QLists. Currently we use a pure QList for storing 
all data of a component (stars, deep sky objects). This will replaced by the 
hash of lists. I've proposed the idea of having a templated RegionList class 
which hides the details of the implementation. We use iterators for 
traversing this list. As C++ gives us templated classes, why not use this 
feature? We are just having 2 additional classes.

There will be no measurable loss of speed in this implementation. The big 
advantage is, that we don't need to add to every component or composite the 
hash of lists. We just add the region list. All code for storing and 
accessing objects is in this class. We can easily change the implementation 
from a hash of lists to a vector of lists or whatever we want to try without 
touching the components/composites anymore. Perhaps for one component is a 
hash of lists perfect, for another component a vector of lists is perfect. 
This we can test then.

I will summarize the current situation were we agree:
- components like starcomponent still remain
- components/composites like milkyway need to be changed
  + we have 1 component with all data
  + or we have 1 smart composite which draws visible components
  + we should decide for every single case what the best solution is

I think we come finally to a solution.

Regards,
Thomas