CS 1025 Computer Science Fundamentals I
Assignment 4

Department of Computer Science
University of Western Ontario
Given: November 6, 2012
Due: November 19, 2012

This assignment is out of a total of 60 points. By answering the bonus questions, you can get up to 120 points out of 60. These bonus points can be used to make up for points missed on other assignments (other assignments in this course only, however).


A hypothetical multi-touch device, the TouchTab 2020, is able to handle touch input from up to three fingers simultaneously. Its low-level drivers provide the x and y position values for each touch and a pressure.

Your task is to take the values reported by the hardware and produce higher-level data structures representing multi-touch traces. A multi-touch trace will be given as an array of long values, with each long encoding up to three touch points at a given instant in time. Since the input touches are sampled at a known freqency, the array then provides the sequence of positions of the touches as they move over time.

The touches at each instant are encoded in the 64 bits of a long value as follows. At each moment, there are n = 0,1,2 or 3 touches. The x, y and pressure for the touches are given as (x1,y1,p1), (x2,y2,p2) and (x3,y3,p3) when the touches are present. The device is wider than it is tall, so each x value is reported as a 9 bit integer (between 0 and 511) and each y value is reported as an 8 bit integer (between 0 and 255). The pressures are reported as 3 bit values (between 0 and 7). The number of points reported, n, will be between 0 and 3 and is represented with 2 bits. The bits are stored in the long integer out as follows:

For each of the questions below, hand in

Question 1. Static Methods and Bit Fiddling (30 points)

Create a class called MultitouchStatusOperations that has no data fields and provides only static methods to do low-level bit operations on long integers, as follows.

The class should have four operations, each encoding a number of reported points. There is one method to construct long for 0 points, one for 1 point, one for 2 points and one for 3 points.

    public static long makeStatusWord();

    public static long makeStatusWord(int x1, int y1, int p1);

    public static long makeStatusWord(int x1, int y1, int p1, 
                                      int x2, int y2, int p2);

    public static long makeStatusWord(int x1, int y1, int p1, 
                                      int x2, int y2, int p2,
                                      int x3, int y3, int p3);

The class should also have operations to extract the number of encoded points as well as each of the x, y and pressure values:

    public static int numberOfPoints(long statusWord);
    public static int x1(long statusWord);
    public static int y1(long statusWord);
    public static int x2(long statusWord);
    public static int y2(long statusWord);
    public static int x3(long statusWord);
    public static int y3(long statusWord);

You should write a test program that uses these methods and convincingly shows they are working properly for the required ranges of inputs. You will find it useful in testing to know that long integer values can be written using an "L" suffix, e.g. 1L << 40 or 5000000000000L.

Question 2. Multi-Touch Traces (30 points)

Write a class MultitouchTrace that represents a sequence of multi-touch status words as an array of long integers. There should also be a field to keep track of how much of the array is used. The array should start off having size 20, and should double in size whenever necessary to add more points.

There should be a constructor that makes an empty trace:

    public MultitouchTrace();

There should be a method to say how many points are in a trace:

    public int length();

There should be a method to add a point (set of touches) at the end of a trace:

    public void addPoint(int[] data);

Here the argument data is an integer array whose fields are:

There should also be methods to get the information about the i-th data word in the trace:

    // Return the number of touches reported at the i-th time.
    public int numberOfPointsAt(int i);

    // Return the value x[j] at time i.
    public int getXAt(int i, int j);

    // Return the value y[j] at time i.
    public int getYAt(int i, int j);

    // Return the value p[j] at time i.
    public int getPAt(int i, int j);

Question 3 [BONUS -- Easy]. Arc Length (15 points)

Write a method

    public double[] getLengths();
that returns an array of up to 3 numbers. If there are always n contact points in each of the multi-touch data words, then the value returned by getLengths should be an array of n numbers. Each of the n numbers should be the length of the polygonal line traced out by the corresponding contact point. You can use the Pythagorean theorem to calculate the distance between subsequent points and add up the results.

Question 4 [BONUS -- Medium]. The Zoom Gesture (15 points)

Write two methods

    public boolean isZoom();
    public double  zoomFactor();
that examine a MultitouchTrace to determine whether it is a "zoom gesture", and if so how much zooming is desired.

A zoom gesture is a trace with

If the trace is a zoom gesture, then the zoom factor is the ratio of the initial distance to the final distance between the two contact points.

Question 5 [BONUS -- Hard]. Trace Rendering (30 points)

Write a Swing component that draws a multitouch trace, showing the correct number of line segments. For full marks, presure should be indicated by the width of the line segments.