Multi-touch gesture classification
Time limit2sMemory limit256 MB
From two side-by-side touch images, extract finger blobs and centers, pair the touches, and report pan, zoom, or rotation with its direction.
- Level
Medium6 of 10
- Topics
- Simulation, Geometry, Brute force
- Solved
- No attempts yet
Problem
Touch screen interfaces forced software designers to rebuild every control around finger gestures. The first step in reading a gesture is deciding which gesture it is. That step is harder than it sounds, because a finger leaves a blob of pixels instead of one exact point, and gestures involve movement.
A touch is a connected set of pixels. Two pixels belong to the same touch when they are horizontally or vertically adjacent. The touch point of a touch is the average position of every pixel in the set.
A grip is the set of all touch points of one image. The grip point is the average position of all touch points in the grip. The touch vector of a touch point is the vector from the grip point to that touch point.
A gesture is a pair of grips, an initial grip and a final grip, and both grips hold the same number of touches. The touches of the two grips are paired one to one. Among all pairings, use the pairing that minimizes the sum of squared distances between paired touch points.
There are three kinds of gesture: pan, zoom, and rotation. Each kind has a distance.
- The pan distance is the distance between the two grip points.
- The grip spread is the average distance between each touch point and the grip point.
- The zoom distance is the absolute difference between the two grip spreads.
- The touch rotation of a paired touch point is the signed angle in radians from its initial touch vector to its final touch vector. It is zero when either touch vector has length zero.
- The grip rotation is the average touch rotation.
- The rotation distance is the arc length of the grip rotation along a circle whose radius is the grip spread of the initial grip.
Classify the gesture as the kind whose distance is greatest.
Input
The input is one pair of images, printed side by side. Both images are 15 rows by 30 columns of pixels. Each of the 15 lines holds the 30 pixels of the initial image, one space, then the 30 pixels of the final image. A pixel is X when it belongs to a touch and a period (.) when it does not. The two images hold the same number of touches, from 1 to 5.
Output
Print the number of touches and the type of the gesture on one line, separated by a single space. The type is pan, zoom, or rotate.
For a zoom, print the direction after the type. It is in when the grip spread of the final grip is smaller than the grip spread of the initial grip, and out otherwise. For a rotate, print clockwise or counter-clockwise after the type. The direction is the one seen on the screen, where the first line of an image is the top row.
Every distance comparison that decides the answer is robust against numerical error of .