March 1999 Programmer's Challenge

Terrain Traversal

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Monday, 1 March 1999

You're on foot with cargo to deliver, and a mountain range between you and your destination. You have no map, nothing except a set of elevation readings provided by a meticulous surveyor that you met at a pub in the last town. And oh, how you hate to climb. Fortunately, this month's Challenge comes to the rescue once again with an efficient and labor saving solution to your problem.

The prototype for the code you should write to solve this Challenge is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef long PointNum, TriangleNum;

typedef struct Point2D {
  double x; /* x coordinate */
  double y; /* y coordinate */
} Point2D;

typedef struct Point3D {
  PointNum thePointNum;  /* point number */
  Point2D thePoint;      /* x and y coordinates */
  double ht;             /* point height (z coordinate) */
} Point3D;

typedef struct Triangle {
  TriangleNum theTriangleNum;  /* triangle number */
  PointNum thePoints[3]; /* numbers of points comprising triangle */
} Triangle;

typedef struct Segment {
  TriangleNum theTriangleNum;  /* segment is part of triangle with this number */
  Point2D startingPoint;   /* x,y coordinates of segment start */
  Point2D endingPoint;     /* x,y coordinates of segment end */
} Segment;

long /*numTriangles*/ InitTerrainMap(
  const Point3D thePoints[],  /* input points */
  long numPoints,             /* number of input points */
  Triangle theTriangles[]     /* output triangles constructed from thePoints */
);

long /*numSegments*/ FindAPath(
  const Point3D thePoints[],  /* input points (input to InitTerrainMap) */
  long numPoints,           /* number of input points */
  const Triangle theTriangles[], /* input triangles (from InitTerrainMap) */
  long numTriangles,        /* number of input triangles */
  const Point2D pathStart,  /* input starting point x,y */
  const Point2D pathEnd,    /* input ending point x,y */
  Segment theSegments[]     /* output segments from pathStart to pathEnd */
);

void TermTerrainMap(void);

#if defined(__cplusplus)
}
#endif

Your InitTerrainMap routine is provided a set of points (thePoints), numbered between 1 and numPoints, that define the terrain to be traversed. It is required to divide the terrain into a set of non-overlapping triangles (theTriangles) that will be provided to FindAPath and return the number of triangles created. InitTerrainMap can divide the terrain into any set of triangles, provided that each of thePoints is a member of at least one triangle, and that none of thePoints is strictly inside of any triangle, measured in the x-y plane. Thus, given points (0,1), (1,-1),(-1,1), and (0,0), the triangle formed by (0,1),(1,-1), and (0,0) would be legal, but the triangle formed by (0,1), (1,-1), and (-1,-1) would not be allowed, because (0,0) is strictly inside the latter.

After InitTerrainMap is called, FindAPath will be called an average of 5 times to generate a sequence of theSegments that traverse a route from pathStart to pathEnd. FindAPath is provided the same set of thePoints given to InitTerrainMap, as well as theTriangles produced by InitTerrainMap. Each segment created by FindAPath crosses from a point along one edge of a triangle to another point along an edge of the same triangle. The startingPoint and endingPoint of each segment must be inside or on the boundary of the same triangle (theTriangleNum). The startingPoint of segment 0 must be pathStart, the endingPoint of segment j must be identical to the startingPoint of segment j+1, and the endingPoint of the last segment must be pathEnd. The starting and ending points pathStart and pathEnd will be in the set of thePoints given to InitTerrainMap, and therefore will be vertices in at least one of theTriangles.

After traversal of some number of paths across the terrain, TermTerrainMap will be called, where you should dispose of any dynamically allocated storage.

Unfortunately, the surveyor who provided us with thePoints in our terrain map was not considerate enough to put them on a regular x-y grid. However, he was limited in the amount of storage he had with him on his mapping expedition, so we know that there will be no more than 32K points in any given terrain map.

The winner will be the solution that minimizes the amount of work required to reach the destination, where work is a combination of distance traveled and elevation change. Specifically, the total work is the sum of the work expended on each segment, which is calculated as the distance traveled in the x-y plane, plus ten times the absolute value of the elevation change from the starting and ending points of the segment. In addition, there will be a penalty of 10% for each second of execution time required to compute a solution. There is no storage constraint for this Challenge, except that your solution must run on a 128MB machine.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".