Special Project: Visual Search Routines
In this project we will design some primitives for performing the sort
of visual searches discussed in Shimon Ullman's Visual Routines
paper.
Radial Search
A radial search sweeps a ray clockwise or counterclockwise from a
starting point until the ray either intersects an object or reaches a
termination point. A radial search can be used to find a "leftmost"
object, or the object "just to the right" of another object, from the
agent's point of view. From this polar perspective, "leftmost" does
not necessarily correspond to something like "minimum x coordinate".
Point radialSearch(const Point &origin, const Point &startPt, const Point &endPt, Sketch sketch);
ShapeRoot radialSearch(ShapeRoot &origin, const Point &startPt, const Point &endPt, const UnaryShapePred &pred);
 origin is the place from which the search ray emanates.
 startPt and endPt are points hit by the ray at the start and end of the search,
respectively.
 sketch is a sketch to be searched until the ray hits a nonzero value.
 pred is s unary shape predicate. In the second form of
radialSearch, where origin is a shape, that shape's shapespace
is searched for a shape that satisfied pred.
Contour Tracing Search
A contour tracing search sweeps an attentional spotlight along a
contour until the spotlight intersects something of interest, or the
end of the contour is reached. A contour tracing search can be used
to answer questions such as "does this curve intersect more than one
X"? See Ullman's figures 11 and 17 for examples.
Project Steps
Step 1
 Comment on the radialSearch method specification. Has anything been omitted?
What is the best algorithm to use for each of the two forms of this method?
 Flesh out the contour tracing search idea. As for radial search,
we want one version that works on sketches and another that works on
shapes. What arguments should each method take? What is the best
algorithm to use for each method?
Step 2
 Implement your own versions of the radialSearch and contourTrace
methods, and test them on some representative examples.
 Prepare a brief (12 page) writeup describing the approach you took,
any limitations or drawbacks you can identify, and your results.
 Due by Friday, March 8. (People leaving town should hand this in
by the 7th.)
Dave Touretzky
Last modified: Fri Mar 1 04:54:24 EST 2013
