Date: 1997-02-11
From: John
Subject: Re: Tape Ahoy

Did you happen to offer any clever suggestions for programming assignments for my C++ class?

My Dear Mr. Duk:

I did babble on for a few minutes about possible programming projects, but all I really came up with was two general areas of interest (to me): fractals and neural nets. You indicated that this project would probably not have much of a visual component (so much for richly textured Alexander maps), but both of those areas offer plenty of abstract, purely computational challenges, and both could involve some interesting data structrures.

The drawback is that in both cases you might expend most of your limited time doing basic research (which would be fun and rewarding but perhaps not good for your GPA bottom line). The trick here, it seems to me, is to find a very, very simple task.

Hmmmm.   *long pause*   **sound of wheels turning**

Here's one. Given an arbitrarily-shaped polygon and a single point, write a function to determine if that point is INSIDE or OUTSIDE the polygon. The polygon would be represented as a linked list of connected points, in which point 1 is connected to point 2 by a straight line, point 2 to point 3, ... , and point n is connected back to point 1. Given that the polygon could be weirdly convex or concave, determining the "insidedness" of the mystery point is non-trivial. (Actually, there are three possible return values for the function: INSIDE, OUSIDE, or RIGHT-ON-THE-EDGE).

This is a golden-oldie, but I do have my ulterior motives for mentioning it. This function could also be used to answer a question of interest to Alexander fans: "What continent does city X reside in?"

Yours in haste,