Programming Assignment 4 - Bubble Chamber Traces

Advanced Programming II, Fall 2003

Due Date

This assignment is due by 2:00 p.m. on Thursday, 20 November.

See the assignment turn-in page (last modified on 3 November 2003) for instructions on turning in your assignment.

A bubble chamber is a device for detecting sub-atomic particles by the tracks they leave as they pass through a liquid. A bubble-chamber photograph can be described as set of triples (x, y, s) where x and y are the integer coordinates of a bubble and s is a positive integer giving the size of the bubble.

A particle trace is a non-empty set of bubble coordinates x (without bubble size). A particle trace describes a shape, but not necessarily a position in a bubble-chamber photograph; that is, the bubble coordinates in a particle trace may have to be scaled, translated, or rotated to match a configuration of bubbles in a bubble-chamber photograph (however, the bubble coordinates will always be integers).

For example, the particle trace { (0, 0), (1, 1), (1, 0) } matches the following bubbles in a bubble-chamber photograph under the given transformations:

Transformed Trace	Transformation
{ (0, 0), (1, 1), (1, 0) }	none
{ (2, -1), (3, 0), (3, -1) }	translation (by (2, -1))
{ (0, 0), (-2, -2), (-2, 0) }	scaling (by -2)
{ (0, 0), (1, -1), (0, -1) }	rotation (by 90 degrees clockwise)

All transformations are uniform; rotations are about the origin.

The Problem

Write a program that reads from std-in a bubble-chamber photograph and a set of particle traces and writes to std-out the locations of the traces in the photograph.

You can find my answer to the assignment in the assignment directory

/export/home/class/cs-509/pa4

Remember, the objective of this assignment is to find tracks in bubble-chamber photographs; the objective is not to faithfully reproduce the behavior of my solution. If my solution's wrong and you copy the error, you're going to lose points.

Input

Input consists of a bubble-chamber photograph followed by a list of particle traces.

The bubble-chamber photograph is a sequence of zero or more integer triples x y s ; successive integers are separated from each other by at least one space character.

A particle trace consists of a trace name followed by one or more integer pairs x y . The trace name is a sequence of one or more letters (that is, any character for which isalpha() is true), case doesn't matter.

Example input:

1 2 1 2 1 4 2 4
3 3 2 1 4 1 5 4 3 2 
alpha 1 1 3 1 2 4 decayedBeta
1 3 4 3 6 1 7 
5

Output

Output is a list of information about the particle traces found in the bubble-chamber photograph. Each input particle trace should result in output of the following form

trace-name occurs n times in the photograph.
The most obvious trace is bubble coordinates

If a particle trace occurs more than once in a photograph, the most-obvious trace is the one with the largest average bubble size. If there is more than one most-obvious trace, then any one will do. If a particle trace appears less then two times in a photograph, there will be no most obvious trace.

Example output (given the example input above):

alpha occurs 2 times in the photograph.
The most obvious trace is 1 2 4 1 4 3

decayedBeta occurs 0 times in the photograph.