Some of the changes in refactoring branch since my latest blog entry are worth mentioning. Python support is getting more stable. Support for plugins written in python has been added. Interface for vector providers gets improved. And yesterday QGIS libraries got spatial indexing using R-trees.

Besides some bugfixing effort for 0.8 release I'm doing also development in refactoring branch. Main reasons for that is some custom work I got recently. I should create an utility for processing some GIS data so I've decided that this might be a great challenge for QGIS libraries and python bindings as that might show the weaknesses and lacking functionality.

Python

QGIS is now able to handle plugins written in Python. This might help to motivate new users and developers to create some great plugins. C++ is surely a good language, but for implementing stuff like plugins is beaten by Python (or other dynamic language) because of Python's simplicity and syntax sugar. I've created a small tutorial on creating plugins in python, hoping that everyone starts to develop plugins :-)

Python wrappers have been also improved a bit as I hit some problems from time to time when writing something in Python. On python bindings wiki page I try to put some examples from time to time so users will get the idea how to use the libraries.

Vector providers

Besides this, I've been working also towards a better and simpler provider interface. The interface got many cleanups and now should be easier to understand and use (and implement). This involved quite a lot of work to update all providers to this new interface, I hope that I haven't broken anything.

Spatial indexing

One of the problems (when developping my utility) was a lack of fast access to features: when searching for nearest features from a point you had to go through all of them - this is pretty inefficient (as my utility needs to work with several millions of features). This can be solved only with indexing, in our case spatial indexing like the one used in spatial databases. Spatial indexing can't be done with classic data structures (like trees or B-trees) as they must be indexes by two (or more) dimensions at the same time and these structures just can't do it effectively. For purposes of graphical applications (CAD, GIS, ...) a number of data structures have been designed as a rescue - Quadtrees, BSP-trees, R-trees and others including many modifications.

For GIS purposes I think that R-tree is a good choice as it can handle all types of geometry and that it is used with success in geospatial databases (e.g. Oracle, Postgis, GRASS). I've found a very nice GPLed spatial indexing library in C++ by Marios Hadjieleftheriou. It supports several query methods, can store data either in memory or on disk, bulk loading and much more. Thus I've added a lighter version to QGIS core library together with a QGIS-ish wrapper class QgsSpatialIndex. Currently supports only limited functionality, more will be added if needed.

The usage is pretty simple:

// create index
QgsSpatialIndex* index = new QgsSpatialIndex();

// insert features
index->insertFeature(feat);

// get features that intersect specified rect
QList featureIds = index->intersects(QgsRect(10, 10, 20, 20));

// get five nearest features from specified point
QList featureIds2 = index->nearestNeighbor(QgsPoint(10,10), 5);

// finish
delete index;

And performance results? In the python utility I've been searching 1000-times for nearest feature in a database of 3500 polylines. This originaly took about 90 seconds. With spatial index it's done in about half a second, that's fairly good performance. I must not forget: many thanks to the developer of the library for making it freely available!