Programming with Python (lab classes)

Vedran Šego, vsego.org

Content:

  1. PIL

Problem 1. Write a module with a function spiral(im, box, r, dx, dy, phi=0, color) that draws a spiral inside the PIL.Image object im, defined by the box box (4-member tuple), with r revolutions, starting at the angle phi. The parameters dx and dy represent how much do the x and the y radius change in each revolution.

For example, the code

im = Image.new("RGB", (400, 300), "white")
spiral(im, (0,150,200,300), 7, 13, 7, color="red")
spiral(im, (400,0,200,150), 17, 2, 4, color="navy")

should produce the following image:

Hint: A spiral can be drawn as a sequence of short line segments.

Problem 2. Write a module for drawing chess board configurations. For example, the image of the final configuration of the Immortal game should look like this: Final configuration of the Immortal game Choose some appropriate input format and data structures to hold all the needed information. The images for the pieces can be found in the internet (for example, the ones in the Wikipedia's article can be downloaded as big as $2000{\rm px} \times 2000{\rm px}$). The module should handle resizing of the pieces' images to any user-given dimensions.

Include an argument that will change from whose perspective the board is drawn (from the perspective of White, the bottom row is 1 and the top one is 8, while Black views from the opposite direction, seeing the row 8 at the bottom and the row 1 at the top).

A module like that could be used to draw the whole games (as a series of images or as a single big one) or to make a GUI application for either playing or analyzing chess.

Problem 3. Make a program that loads the name of an image file and creates an image containing both the loaded image and its histograms for each of its color components (red, green, and blue). The histogram should be saved as "original_filename-hist.original_extension" and displayed on the screen. Here is a sample of what it should look like for this image:

Image with histagram

Hint: A Matplotlib figure can be directly converted to a PIL drawing (search the internet to find out how), allowing you to directly merge the original image and its histograms into a single image. A less elegant solution is to save the histograms figure as an image, and then open it with PIL to add the original image on top of it.

Problem 4. Make a program that will generate a random labyrinth with a given number of rows and columns, and draw it with and without a solution (two images), like this:

Alternatively, you can add a background image:

How to generate a random labyrinth?

While this may seem like a very hard problem, it can be done fairly easily with a bit of help from the graph theory and Python's NetworkX module.

To create a random labyrinth with r rows and c columns, first create a grid graph with $r \times c$ nodes, assigning each of the edges a random weight, like this: Basic graph as a grid The nodes represent the blocks in the labyrinth, while the edges represent the possible locations for the walls or the openings.

Then compute its minimum spanning tree $T$ using one of these NetworkX functions: Spanning tree; the edges define halls Notice that the spanning tree defines the halls of our labyrinth.

The random weights ensure that we get different minimum spanning trees for different graphs, and the fact that we are using trees ensures that there are no cycles while the graph/labyrinth remains connected (i.e., there is exactly one path between each pair of blocks).

All that we need to do now is draw this as a labyrinth, using PIL's ImageDraw.Draw.rectangle function. You can also use the ImageDraw.Draw.line function, but this will give you less control over how the walls are drawn.

Note that we need to draw the walls of the labyrinth, while our tree contains its halls, i.e., we need to draw the walls corresponding with the grey edges on the previous image. This means that we need to draw a wall between neightbour blocks $(f,t)$ if and only if $(f,t)$ is not and edge in $T$. This might seem like a job for a complement graph (implemented as networkx.complement), but it is not, because the complement graph would also contain the edges between the non-neighbour nodes. However, a simple if edge not in tree.edges() does the trick.

How to solve the labyrinth?

Finally, to generate the solution of the labyrinth, choose two blocks for the enterance and the exit, and find the path between them inside the tree $T$. This path is unique, but NetworkX doesn't have a "find the unique path in a tree" functon. However, it does have various shortest path functions which will do the job. For our example, such path looks like this: Minimum path, defining the solution

Again, all that is left is drawing this solution on the previously drawn image of the labyrinth.

Note: In order to print these images easily, PIL can save them directly as PDF files.