canstellation search engine

This simple project allows you to search photgraphed constellations on the sky map. It is not that simple as described, but presented here algorithm and its implementation allow to search any given graph on the provided map of points.

It will find scaled and rotated graph with no more than specified error.

More implementation details can be found in the blog line.

Here is a short demo:

Sky walker in action

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) at 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.

Algorithm itself is quite simple – it selects a vector in the searched graph and rotates coordinates according to it, then it iterates over every possible vector in the original map (O(N*N) complexity) and checks if there are points, which correspond to the transformed parametrized coordinates of the searched graph (O(M) to check each coordinate of the searched graph and O(log2(N)) to check if point with calculated coordinates exists).

Here are main formulas:

cos_a = (e->x - c->x) / vector_len;
sin_a = (e->y - c->y) / vector_len;

p->sin_b = ((a->y - c->y) - (a->x - c->x)*sin_a/cos_a)/(p->len * (cos_a - sin_a*sin_a/cos_a));
p->cos_b = ((a->x - c->x)/p->len - sin_a*p->sin_b)/cos_a;

x = c->x + len * (cos_a*p->cos_b + sin_a*p->sin_b);
y = c->y + len * (sin_a*p->cos_b + cos_a*p->sin_b);

Check source for the details (requires gtk2).