Configuration Space

I took a class called Algorithms for Robotics in the school. The class was interesting, except that I messed up the finals. Anyway, the assignments included finding the configuration space of a 2D robotic arm, Simultaneous Localization & Mapping, etc. I thought of writing something about it here.

The configuration space of a robot allows it to calculate the possible motions it can take, given the locations of the obstacles.  The above picture represents the two angles of a 2D arm robot. Each goes from 0 to 360 degrees. The red shade indicates obstacles and the white space indicates the free space. The real-world coordinates are translated by the algorithm into the above representation to make things much easier. I wrote the program in Java. It was an interesting solution since I did not use any open-source libraries.

Sample input


3 11
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
3 2
3 3
4 3
1 2 6 5
3 4 8 7
9 10 11
3 0
2 2

Program link