About TODO Blog RSS Old blog Projects Gallery Notes

Sun, 11 Nov 2007

I completed sky walker prorgamm.

This is a name for my 2d point matching algorithm.
It gets number of points as a map and number of points to find on the given map. It should find them even if graph made of those points is rotated or scaled.

One can find result on this animated gif:



It uses too big error value (i.e. maximum difference between points to say that they are equal, it is needed because of heavy math usage (actually a bit of trivial school trigonometry) with resulted error) to show how it works. There are 400 randomly generated points at the left parts and graph to be found at the right, you can see that it was found 7 times being rotated and scaled.

Algorithm is quite heavy - it requires O(N*N*log2(N)*M) in the worst case, where N is number of points on the original map and M is number of points on the searched graph. But application is highly parallelable - it is possible to stop searching and then later resurrect it from given position or from any other inside the whole map, it is possible that several threads or nodes in cluster can search in the diferent areas of the sky.
Complexity can be greatly reduced with introduction of luminocity.

Main application is to search photographed constellations on the huge sky map.

Sources (requires gtk2) and details can be found on the homepage.

/devel/sky :: Link / Comments (0)