Your job in this project is to find the largest two-dimensional polygon that can make it through a given obstacle course of polygons. The field of operation is a region of size 4 units by 1 unit. The start square is the leftmost 1x1 subregion of the field. Your polygon must fit inside this square. The end square is the 1x1 subregion at the right end of the field. Neither the start square nor the end square contain obstacles.
The intervening 2x1 region contains obstacles that are also polygons. (All polygons in this problem are simple, i.e., non-overlapping polygons. Polygons may be concave, and may have an arbitrary number of faces.) You need to design a polygon that can move from the start square to the end square, through the intervening space, without overlapping any of the obstacles. You are permitted to translate your polygon an arbitrary distance in any direction. You are also permitted to rotate your polygon by an arbitrary amount in either direction. At all times, your polygon must stay within the 4x1 field.
The following diagram shows an example field.
The dashed line shows a possible path through the obstacle field. (What kind of shape would fit along that path? What rotations would be necessary? Is this the ``best'' path?)
In its full generality, this is a difficult problem, and unlikely to be solved exactly. For example, consider the diagram below.
The right-angled corner seems amenable to a semicircular shape, or, for the purposes of this project, a close polygonal approximation to a semi-circle. Just push the semicircle along the horizontal corridor, rotate it 90 degrees anticlockwise, and push through the vertical corridor. This works fine, but it turns out that there are even larger shapes that work, including shapes similar to the top one in the diagram above. As far as I know, even just the problem of determining the largest shape that will make it around a right-angled corner like this has not been solved mathematically (i.e., with rigorous proof).
The input to your program will be a sequence of polygons. The coordinate system starts at (0,0) in the lower left corner, and (4,1) at the upper right corner. All obstacles will be within the rectangle bounded by (1,0) and (3,1). The output from your program is a polygon situated within the start square, together with a series of translation and rotation instructions. The sequence of instructions must take your polygon from the start square to the end square without overlapping any of the obstacles, and without leaving the 4x1 field. We'll provide software that executes the moves and verifies these conditions, but the code to determine the polygon and the path is to be written by you. The precise format for the inputs and outputs will be specified later. Your goal is to find the largest possible polygon that meets the conditions.
In some cases, such as when you're trying to approximate a curve, you may be tempted to use huge numbers of facets to get every little bit of area. To avoid such issues, and to keep the object manipulation simple, we'll put a limit of 100 sides on all polygons, including the obstacles.
We'll run a tournament at the end of the project, using some standard obstacle courses, and using some that you haven't seen before. You should also think yourselves about designing courses that will provide interesting tests of your programs.