Introduction to the Problem

Starry Night is a graphic pattern matching problem, algorithmically challenging, but allowing a natural gradation on the degree of completion of the solution.

The task description is easy to understand. Outlining a solution is also not too difficult.

However, due to the multiple orientations of the clusters and their irregular shapes, the algorithmic details of any solution get very complex. So, considering the time constraints, it is hard to develop a complete solution for this problem.

Algorithms

Overall description

Any full solution requires the development of the following two main algorithms.

• Cluster detection: This amounts to the classical problem of detecting the connected components of a graph;
• Cluster comparison: Two clusters ~A~ and ~B~ are compared according to the ~8~ possible combinations of rotation/reflection

Cluster comparison

The best way to perform the comparison of cluster ~A~ with cluster ~B~ is to associate, successively, ~8~ different coordinate systems with cluster ~A~. Clusters may depict irregular shapes. Hence, it is also necessary to compute the ~8~ starting stars of cluster ~A~ where the comparison with cluster ~B~ must start for each of the ~8~ orientations. A brute force approach would try every star in cluster ~A~ as a candidate starting point for the comparison with cluster ~B~.

There are alternative methods for comparing cluster ~A~ with cluster ~B~. For example, it is possible to copy cluster ~B~ to a separate buffer and change successively its orientation in order to compare it with cluster ~A~. This method is slower and algorithmically more laborious.

The program does not need to keep a record for every cluster in the map. In fact, while scanning the map, it is enough to record one representative cluster for each distinct shape that comes across. The clusters that are not representative are simply marked with the low case letter corresponding to their shape.