Project 2: They do it with mirrors.

The respected architectural firm of Benny, Binny, Bonny, Bunny and Wolf have retained you as a consultant. Their latest designs, which have received rave reviews in the press, are extremely popular. Their designs involve building rooms in unusual polygonal shapes. The sides of the rooms are either windows, walls or mirrors. With the latest materials available, the windows are perfectly transparent and very thin (meaning that there is negligible displacement of light due to refraction). The mirrors are perfectly reflective. The walls are opaque and black, i.e., totally nonreflective. Ceilings and floors are also opaque and black.

It seems that they have been having trouble lighting the rooms. Because of the unusual shapes and angles involved, either the room is lit in an unbalanced way, or too much lighting is needed for the given area.

Your job is to write a computer program to recommend a placement of lights for a given room. You cannot adjust the dimensions of the room, nor the combinations of walls, windows and mirrors chosen by the architects. You can, however, adjust the number of light fittings, the power of each light fitting, and the positions of the light fittings inside the room.

For the purposes of this class, we'll think of it as a two dimensional problem in a horizontal plane within the room. Light emanates from a light fitting equally in all directions, and diminishes according to the inverse square of the distance from the fitting. The intensity of light output is proportional to the power (measured in watts) of the light fitting. Let us suppose that one watt generates 1 unit of brightness at a distance of 1 meter.

At any point $P$ in the room, the illumination is the sum over all rays $R$ emanating from all fittings $F_i$ and impinging on $P$, of the brightness of the ray. The ray $R$'s brightness is $P/d_R^2$, where $d_R$ is the length of ray $R$. Rays may bounce of mirrors and trasmit straight through windows according to the usual optical rules. Note that a ray going through a window leaves the room, but it may later re-enter the room through another window. (We are optimizing for night illumination, so there's no additional light entering the windows.)

The mathematical description given above does not tell you how to compute intensities, since there are infinitely many possible rays that each could travel for a long time. (Think of an all-mirror room!) To compute intensities, you will need to approximate. For example, once a ray has travelled a long way (how long is long?) its contribution to the overall intensity is likely to be small, and could be ignored. A reasonable way to simulate the lights would be to generate a bunch of ``photons'' shooting out in random directions. The room could be divided up into small square cells (say the size of a pixel if you're thinking about a screen display) with the photon contributing to the brightness of the cell if the ray passes within the cell. Note that a ray can contribute to a cell at most once, since if we were to place an object at the cell to actually measure the illumination, the ray would be blocked from making extra passes through the cell.

When optimizing the light fittings, we will optimize according to the following metric. Electricity costs about $50 per megawatt hour, say. Budgeting the cost of 9 years of electricity at this price, with 6 hours per day of use, each watt costs one dollar. Each fitting costs, say $100 for hardware and installation. You want to minimize the total number of dollars spent.

The optimization problem to solve is as follows:

Place fittings so that $p$ percent of the room is above a minimum illumination threshold $t$, minimizing the dollar cost.

$p$ and $t$ are input parameters.

We will provide software that verifies the correctness of a solution, displays its cost, and shows a visualization of the lighting of the room. The provided software includes some algorithmic components for determining illumination that you may want to re-use within your optimization code.

It is your job to develop an algorithm to select and place the light fittings. The final result should be displayed using the provided software. (If your algorithm proceeds by choosing different configurations over time, it would be interesting to display those intermediate configurations as they are considered.)

A room is described by a file of the following form:

# simple room
0 0 m
0 1 w
1 1 t
1 0 w

Each line of the file corresponds to a corner of the room. The first two columns are the x and y coordinates, which may be floating point numbers. The third column indicates the kind of edge to the subsequent point: m=mirror, w=wall, t=transparent (i.e., window). The final point wraps back to the initial point. You may assume that the room you are given is non-overlapping, and does not have holes. The interior of the room is always to the right as you follow the points in the given order. The small file above corresponds to a square room of size 1 square meter, with two parallel horizontal walls, a mirror at one end, and a window at the other. Comments can occur anywhere in the file, on a line beginning with a ``#'' character.

We will have competitions for each of the two categories of optimization described above. Some rooms will be supplied, but you will also be asked to come up with interesting rooms. For example, what would be the consequences of creating a sequence of mirrors to approximate a parabolic reflector? Can you think of a kind of room where the optimal light placement would include a light fitting outside of the room? We will try to examine a range of room geometries and complexities.

Here's a puzzle to get you thinking about room design. We've said that rooms can't have holes. How would you design a room that was, both geometrically and optically, essentially equivalent to a rectangular room with an opaque internal triangular box sitting inside it?

One clarification: since light may exit a room through a window, then hit an exterior wall, we shall assume that the exterior of a mirrored wall is also mirrored, and the exterior of an opaque wall is also opaque.

I suggest using double precision for illumination measurements, to minimize numerical underflow. Note the following special case of our problem: If we set the illumination threshold $t$ to a very small positive number, and the percentage $p$ to 100%, the problem amounts to positioning the fittings so that every point in the room is illuminated by some light fitting.