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

[Thomas Kabelmann]

Hi James,

thank you for your informative explanation.

<snip>
> Let me give you a little background.  The cost of determining which regions
> are at least partially visible can be significant.  In my tests, when the
> user is full zoomed out it takes between 1 and 10 milliseconds to get the
> list of regions. I don't think we want to do that calculation more than
> once if we don't have to.
Agreed. This should be done one time before updating all components. Then we 
could send an update() message with the SkyIndex object. Or every component 
knows the SkyIndex object.

> But that's okay, I think we can still implement your idea (2) above if we
> are willing to keep the SkyIndex and SkyRegion classes separate.  Better
> yet, we could get rid of the SkyRegion class entirely!  The idea here is
> that the SkyIndex class would return lists of actual indices instead of
> lists of SkyRegions.  Each SkyComponent would need to keep its own array
> of "regions", which would just be an array of QLists.  I would imagine
> that this array would be a static class member.
Why should this be a static member? Every component should only know it's own 
data. StarComponent should only know the stars, CometsComponent only the 
comets and so on.

Currently we have in most situations a QList for storing data. From memory 
point of view there is no difference if you have 100 regions with 10 
(component) lists (numbers are just samples) or you have 10 components with 
100 regions.

I can imagine that every component has a structure which contains an array 
(QVector perhaps) which stores the regions in lists (QList). For an easy 
implementation I suggest a templated class RegionList, so every component can 
instantiate a list of the object type it needs:

template <typename T, int regions> class RegionList
{
	public:
		// add the object in the right region list
		void add(T object, SkyIndex index);
		// return an iterator for the structure using the indices
		Iterator<T> iterator();
		...
	private:
		QVector <QList <T>> list(regions);
		skyIndex *indices;
}

For traversing the RegionList we should implement an iterator. This iterator 
needs to know, what type of objects are stored (templated class), the indices 
of the regions and in special cases like the StarComponent the magnitude 
level. So we can easily traverse in all components like this:

Iterator<StarObject> it = regionList.iterator();
for (it.begin(); it.end(); it.nex())
{
	// drawing code
}

> I'll try to explain why I think we will no longer need the SkyComposites
> when we use the index/region model in a separate message.
I don't see the reason why we don't need composites anymore. The 
composite/component modell allows us to delegate the messages. It's a 
hierarchical organized structure, so we just need to know the top level 
composite and send all messages to this object, without knowing the 
underlying structure.

One simple optimization I see, is to update just the components which are 
visible by option. If the component is disabled, the update() call can be 
done in draw() using a dirty flag which the component stores. The update() 
call just sets the dirty flag in this case.

Regards,
Thomas