TweetFollow Us on Twitter

Jun 99 Challenge

Volume Number: 15 (1999)
Issue Number: 6
Column Tag: Programmer's Challenge

Jun 99 Challenge

by Bob Boonstra, Westford, MA

Tetraminx

The last Challenge I entered as a contestant was the Rubik's Cube Challenge, where entries had to solve a scrambled Rubik's cube. While that Challenge was difficult enough to cause me to retire from competition after winning, I've stayed interested in puzzles. Some time ago I ran across Meffert's World Of Puzzles, an online puzzle vendor at http://www.mefferts-puzzles.com/mefferts-puzzles/catalog.html, and ordered a few of their puzzles. The Tetraminx is perhaps the least difficult puzzle, much simpler than the Cube, but still interesting enough that I thought it might make a good Challenge without driving any contestants into retirement.

The Tetraminx is formed by four hexagonal faces, each consisting of six triangles, joined in the shape of a tetrahedron, plus four triangles to complete the solid, as depicted at http://www.mefferts-puzzles.com/pictures/tetramix.jpg.

Scrambled Tetraminx

Your Challenge is to come up with a sequence of moves that will return the puzzle to the goal state, where each of the hexagonal faces consist of triangular facelets of a single color.

The prototype for the code you should write is:

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

typedef enum {
   kYellow=1,kBlue,kRed,kGreen
} PieceColor;

typedef enum {
   kLeftClockwise=1,kRightClockwise,
      kBottomClockwise,kBackClockwise,
   kLeftCounterClockwise,kRightCounterClockwise,
     kBottomCounterClockwise,kBackCounterClockwise
} Move;

typedef enum {
   /* single triangular faces named after the opposite hexagonal face */
   kLeft,kRight,kBottom,kBack,
   /* edge faces named kXY, where X is the hexagonal face they are part of, 
      and Y is the adjacent hexagonal face */
   kBR,kRK,kKB,
   kLB,kBK,kKL,
   kKR,kRL,kLK,
   kLR,kRB,kBL,
   /* corner faces named cXY, where X is the hexagonal face they are part of, 
      and Y is the hexagonal face opposite the adjacent single triangle */
   cRL,cKL,cBL,
   cLR,cBR,cKR,
   cRB,cLB,cKB,
   cLK,cRK,cBK 
} PieceType;

typedef struct {
   PieceType piece;
   PieceColor color;
} PieceState;

long /* numberOfMoves */ Tetraminx (
   PieceState state[28],      /* initial state of the 28 pieces */
   Move moves[],              /* moves you generate */
   long maxMoves              /* maximum storage in move array */
);

#if defined (__cplusplus)
}
#endif

The puzzle is manipulated with four pairs of 120-degree rotation moves that we will call kLeftXXX, kRightXXX, kBottomXXX, and kBackXXX, corresponding to the four hexagonal faces of the Tetraminx. The moves are named for the hexagonal face that remains fixed during the move.. Opposite each of those hexagonal faces are the single triangular faces whose positions remain fixed for all moves (except for rotation). Each move pair consists of a clockwise move and a counterclockwise move, as viewed from the opposite single facelet, through the Tetraminx, at the face for which the move is named.

The PieceType enum names the 28 triangular facelets. Facelets come in three types, and it is important to understand the naming convention for the facelets. The first type consists of the single triangular faces, and those are named kLeft, etc., for the move that rotates the piece, and for the opposite hexagonal face. The second type is an "edge" facelet, one with a single adjoining triangle, and those are named kXY, where X (L, R, B, or K) is the hexagonal face containing the piece, and Y (also L, R, B, or K) contains the adjacent facelet. Finally, "corner" facelets have three adjacent triangles, two of them on the same hexagonal face, and one a single triangular face. These are named kXY, where X is the hexagon containing the piece, and Y is the single triangular face.

This is probably impossible to understand without a picture, so I've included one. A color version of the picture is available at http://www.mefferts-puzzles.com/mefferts-puzzles/pictures/tetrmi5b.gif. The blue, red, yellow, and green faces are the left, right, bottom, and back faces, respectively. The face comprised of the single center (yellow) triangle is the kBack facelet. Starting with the blue triangle next to the kBack facelet, and moving clockwise around the blue face, are the cLK, kLB, cLR, kLK, cLB, and kLR facelets.

The kBackClockwise move rotates the yellow kBack facelet in a clockwise direction, moving the kLR piece (Blue-Red) to where the kRB piece (Red-Yellow) is, and the kRB piece to where the kBL piece (Yellow-Blue) is.

If the nomenclature for facelets and moves seems confusing, the test code available via the Challenge mailing list will make it clearer. Alternatively, for those of you that are into group theory, the four clockwise moves perform the following permutations on the facelets:

kRightClockwise:     (kKL, kLB, kBK) (kLK, kBL, kKB) (cLR, cBR, cKR)
kLeftClockwise:      (kRK, kKB, kBR) (kKR, kBK, kRB) (cRL, cKL, cBL)
kBottomClockwise:    (kKR, kRL, kLK) (kRK, kLR, kKL) (cRB, cLB, cKB)
kBackClockwise:      (kLR, kRB, kBL) (kRL, kBR, kLB) (cLK, cRK, cBK)

Tetraminx Facelets

Your code should place the moves needed to solve the puzzle in moves and return the number of moves generated, or return zero if you cannot solve the puzzle in maxMoves moves.

Instructions for solving the Tetraminx are available at http://www.mefferts-puzzles.com/mefferts-puzzles/tetrasol.html. Since you probably don't have a Tetraminx handy, test code will be available to help you see the effects of the moves you make to solve the puzzle. The winner will be the solution that solves the puzzle in the fewest number of moves, with a 10% penalty added for each second of execution time.

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

Three Months Ago Winner

Congratulations once again to Randy Boring for submitting the winning solution to the March Terrain Traversal Challenge. The March Challenge required contestants to process sets of 3-dimensional input points, convert them into non-overlapping triangles, and then navigate across those triangles from pairs of starting points and ending points. The score for a solution was based on the distance traveled, with a penalty for the change in elevation along each segment of the solution, and an additional 10% penalty for each second of execution time. The winning solution minimized the solution score and the total elevation change, but it took the greatest amount of execution time to do so, and generated solution paths that were longer than those of the 3rd place solution.

Some of the contestants and members of the Challenge mailing list mentioned the possible use of Delaunay triangles http://www.ics.uci.edu/~eppstein/gina/delaunay.html in solving this Challenge. A collection of Delaunay triangles has the property that, for each edge in the collection, there is a circle containing the edge's endpoints but not any other endpoints. The idea was that these triangles would be "best" in some sense for finding optimal paths from pairs of points. However, none of the submitted solutions actually implemented this approach.

The top two scoring solutions both tried a straightforward approach to defining triangles, one that I hadn't anticipated when I defined the problem (although I probably should have). These two solutions selected an anchor point, sorted the remaining points by the angle they formed from the anchor point, and formed triangles from the anchor point to the Nth and N+1st points in angle from the anchor. This approach has the feature that there is a two-segment path between any pair of points, one from the first point to the anchor, and one from the anchor to the second point. Randy's winning solution chose the anchor to be a point in the center of the set of points, while the second-place entry of Jared Selengut chose the point arbitrarily. Randy's solution looked for a path that was better than this initial two-segment path, an enhancement that did find a better solution in one of my tests. Jared's solution was much quicker, but it found longer paths with greater elevation change than Randy's winning solution.

Ernst Munter's solution actually found the shortest solutions, although the elevation change was greater. Ernst's approach was to build the triangles in progressively widening circles around a central point. The paths produced by his solution had many more segments than the other two solutions, resulting in a more direct path between the endpoints, but the total elevation change was greater than that generated by either of the other two solutions.

The test scenarios consisted of a total of 18 test cases using 3 data sets of 2500 points each. The table below lists, for each of the solutions submitted, the total execution time for all test cases, the total horizontal distance and elevation change for the paths generated, the total score for all test cases, and the code and data size of each solution. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name Time (msec) Horizontal Distance Elevation Change Score Time Code Size Data Size
Randy Boring (83) 3947.17 71710.96 3207.75 118109.99 9952 1MB
Jared Selengut 142.63 73702.69 6282.39 137171.56 2044 72
Ernst Munter (430) 1729.30 65972.19 18157.13 261376.67 9312 264

Top Contestants

Listed here are the Top 20 Contestants for the Programmer's Challenge. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

  1. Munter, Ernst 205
  2. Saxton, Tom 99
  3. Boring, Randy 66
  4. Rieken, Willeke 47
  5. Maurer, Sebastian 40
  6. Heithcock, JG 37
  7. Murphy, ACC 34
  8. Lewis, Peter 31
  9. Mallett, Jeff 30
  10. Cooper, Greg 27
  11. Nicolle, Ludovic 27
  12. Brown, Pat 20
  13. Day, Mark 20
  14. Hostetter, Mat 20
  15. Hewett, Kevin 10
  16. Jones, Dennis 10
  17. Selengut, Jared 10
  18. Smith, Brad 10
  19. Varilly, Patrick 10
  20. Webb, Russ 10

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place20 points
2nd place10 points
3rd place7 points
4th place4 points
5th place2 points
finding bug2 points
suggesting Challenge2 points

Here is Randy's winning Terrain Traversal solution:

FindAPath.c
Copyright © 1999 Randy Boring

/*
 *    Simple solution: two-part path!
 *    make radial design triangles to a central point
 *    solve by traversing to center, then to destination
 */

#include "FindAPath.h"
#include <fp.h>
#include <MacMemory.h>   // for NewPtr, etc.

#pragma mark == Top ==
#define INPUT_IS_SORTED   0
#define MYDEBUG 0

#if MYDEBUG
   #define kGarbage   (0xA3A3A3A3)
   #define kGarbage2   (0xA3A5A4A3)
   #define kGarbage3   (0xA5A5A5A5)
   #define ASRT_TYPE 1
   #if ASRT_TYPE == 2
      #include <assert.h>
      #define ASSERT(cond)   assert(cond)
   #else
      #define ASSERT(cond)   if (cond) ; else DebugStr("\p assert failed!")
   #endif
#else
   #define ASSERT(cond)
#endif

// skew the weight of the z (height) axis, since it is skewed
//   in the scoring of our Solutions.
#define kHeightWeight      (8.0)   // should be up around 100.0 since it's squared
#define kTwoPi            (pi * 2.0)
#define IdxOfPt(pt,ptarray)   ((pt) - (ptarray))
#define kNoTriangle         (-1)
#define kMaxPoints         (32 * 1024L)

// globals
static long gCenterIdx;   // index of center point

#if INPUT_IS_SORTED
// 'fix' the numbering of points (off by one)
#define PtNumToIdx(n)      ((n) - 1)
#define IdxToPtNum(p,i)      ((i) + 1)
#else
// 'fix' the numbering of points (create mapping of number to index!)
static long gPtNumToIdxMap[kMaxPoints];

#define PtNumToIdx(n)   (gPtNumToIdxMap[(n) - 1])
#define IdxToPtNum(p,i)   ((p)[i].thePointNum)

static void
MakePtNumToIdxMap(const Point3D p[], long pCount)
{
   long i;
   for (i = 0; i < pCount; i++)
      gPtNumToIdxMap[p[i].thePointNum - 1] = i;
}

static void
DisposePtNumToIdxMap(void)
{
   DisposePtr((Ptr) gPtNumToIdxMap);
}
#endif

Dist
// Return a measure of the distance, given the deltas, but 
//   weight the height (z) axis most, as this has the most
//   weight in our Solution's score.
static double
Dist(double dx, double dy, double dz)
{
   return (dx * dx + dy * dy + dz * dz * kHeightWeight);
}

FindMiddleDotIdx
// Return the index of the middle-most point
static long
FindMiddleDotIdx(const Point3D p[], long numPoints)
{
   double totX = 0.0, totY = 0.0, totH = 0.0;
   double aveX, aveY, aveH;
   double denom = 1.0 / numPoints;
   double bestDX, bestDY, bestDH, closestDist;
   long i, besti;
   
   // find average x, y, ht
   for (i = 0; i < numPoints; i++)
      {
      totX += p[i].thePoint.x;
      totY += p[i].thePoint.y;
      totH += p[i].ht;
      }
   aveX = totX * denom;
   aveY = totY * denom;
   aveH = totH * denom;
   bestDX = aveX - p[0].thePoint.x;
   bestDY = aveY - p[0].thePoint.y;
   bestDH = aveH - p[0].ht;
   besti = 0;
   closestDist = Dist(bestDX, bestDY, bestDH);
   
   // find lowest distance to average
   for (i = 1; i < numPoints; i++)
      {
      double dH, dX, dY, thisDist;
      dX = aveX - p[i].thePoint.x;
      dY = aveY - p[i].thePoint.y;
      dH = aveH - p[i].ht;
      thisDist = Dist(dX, dY, dH);
      if (closestDist > thisDist)
         {
         closestDist = thisDist;
         besti = i;
         }
      }
   return besti;
}

RadiansBetweenOld
// Absolute radians of the vector from point c to point i
static double
RadiansBetweenOld(long c, long i, const Point3D p[])
{
   double dx = p[i].thePoint.x - p[c].thePoint.x;
   double dy = p[i].thePoint.y - p[c].thePoint.y;
   double angle = atan2(dy, dx);
   return angle;
}

RadiansBetween
// Absolute radians of the vector from point 0 to point 1
static inline double
RadiansBetween(double x0, double y0, double x1, double y1)
{
   double dx = x1 - x0;
   double dy = y1 - y0;
   double angle = atan2(dy, dx);
   return angle;
}

MakeRadialConnection
// Add the two points, c and pointi, to a proto-Triangle
//   (The other leg will be added after sorting by angle)
static void
MakeRadialConnection(const Point3D p[], 
   long pointi, long c, 
   Triangle t[], long ti)
{
   double *angle = (double *) &(t[ti].thePoints[1]);
   *angle = RadiansBetween(p[c].thePoint.x, p[c].thePoint.y, 
         p[pointi].thePoint.x, p[pointi].thePoint.y);
//   t[ti].theTriangleNum = ti;   // filled in later
   t[ti].thePoints[0] = IdxToPtNum(p, pointi);
}

Cmp
static int   // positive if right less then left, zero if equal
Cmp(const void *left, const void *right)
{
   Triangle *lt = (Triangle *) left;
   Triangle *rt = (Triangle *) right;
   double *ltval = (double *) &(lt->thePoints[1]);
   double *rtval = (double *) &(rt->thePoints[1]);
   double diff = *ltval - *rtval;
   if (diff > 0.0)
      return 1;
   else if (diff < 0.0)
      return -1;
   else
      return 0;
}

SortTriangles
#include <stdlib.h>
/* void qsort(void *base, size_t nmemb, size_t size,
      int (*compare) (const void *, const void *)) */
/* this requires linking with MSL Std C Lib */
static void
SortTriangles(Triangle t[], const long tCount)
{
   qsort(t, tCount, sizeof(Triangle), Cmp);
}

ConcaveAngle
// Return true if the angle difference, diff, represents
//   a Concave angle, i.e., < 180 degrees (pi radians)
static Boolean
ConcaveAngle(double diff)
{
   if (diff < -pi)
      return true;
      
   /* Bob guaranteed that this case would not occur:
      'The situation where a point lies exactly along an 
       edge between two other points will not arise.' */
   ASSERT(diff != 0.0);
   
   if (diff <= 0.0)
      return false;
   if (diff < pi)
      return true;
   return false;
}

Perimeter Point List
#pragma mark == Perimeter Point List ==

// This structure is for keeping track of the diminishing
//   list of points that make up the 'perimeter' around the
//   triangles.
// As the 'concavities' are filled up, points in this list
//   are no longer on the perimeter and so are removed.
// The process stops when the perimeter is convex
// The 'un-const' Point3DPtr is still treated as 'const' by me,
//   but I couldn't figure out how to make the compiler let
//   me make const pointers into the point array otherwise.
typedef Point3D * Point3DPtr;
typedef struct {
   Point3DPtr   *plist;
   Point3DPtr   *plast;
   long      size;
   } PointList;

//----//----//----//----//----//----//
static void
MakeListOfEdgePoints(Triangle t[], long tCount, void *vp, 
      const long badIndex, PointList *list)
{
   long i;
   Point3DPtr p = (Point3DPtr) vp;
   Point3DPtr *pp;
   list->plist = pp = (Point3D **) NewPtr(tCount * sizeof(Point3D));
   if (list->plist == nil)
      DebugStr("\p couldn't allocate point list!");
   list->size = tCount;
   for (i = 0; i < badIndex; i++)
      *pp++ = &(p[PtNumToIdx(t[i].thePoints[0])]);
   if (badIndex != -1)
      {
      *pp++ = &(p[PtNumToIdx(t[i].thePoints[0])]);
      *pp++ = &(p[gCenterIdx]);
      list->size++;
      i++;   // i == badIndex has been processed
      }
   for (; i < tCount; i++)
      *pp++ = &(p[PtNumToIdx(t[i].thePoints[0])]);
   list->plast = pp;
}

static void
DisposeList(PointList *list)
{
   DisposePtr((Ptr) list->plist);
#if MYDEBUG
   list->plist = (struct Point3D **) kGarbage;
   list->plast = (struct Point3D **) kGarbage2;
   list->size = kGarbage3;
#endif
}

#define GetEdgePointCount(l)   ((l)->size)
#define SetEdgePointCount(l,s)   ((l)->size = (s))
#define RemoveEdgePoint(l,p)   (*(p) = nil)

//----//----//----//----//----//----//
// Find first non-nil ptr in array
static Point3DPtr *
GetFirstEdgePoint(PointList *list)
{
   Point3DPtr *p = list->plist;
   while (*p == nil)
      ++p;
   ASSERT(p < list->plast);
   return p;
}

//----//----//----//----//----//----//
// Starting at p, find next non-nil ptr in array
// Returns nil if no more, else
// Returns pointer to array element containing the non-nil ptr
static Point3DPtr *
GetNextEdgePoint(PointList *list, Point3DPtr *p)
{
   Point3DPtr *stop = list->plast;
   Point3DPtr *found = nil;
   while (++p < stop)
      if (*p != nil)
         {
         found = p;
         break;
         }
   ASSERT(p < stop);
   return found;
}

//----//----//----//----//----//----//
// Return true if, when looking from p1 to p3, p2 is on the left
// This means that a triangle can be constructed of these
//   points, making the perimeter more convex (removing a concavity).
static Boolean
Concave(const Point3D *p1, const Point3D *p2, const Point3D *p3)
{
   double r21 = RadiansBetween(p2->thePoint.x, p2->thePoint.y, 
         p1->thePoint.x, p1->thePoint.y);
   double r23 = RadiansBetween(p2->thePoint.x, p2->thePoint.y, 
         p3->thePoint.x, p3->thePoint.y);
   double diff = r23 - r21;   // angle (in radians) at point 2
   return ConcaveAngle(diff);
}

static void
AddTriangle(Triangle t[], long tidx, 
   Point3DPtr p1, Point3DPtr p2, Point3DPtr p3)
{
//   t[tidx].theTriangleNum = tidx;   // filled in later
   t[tidx].thePoints[0] = p1->thePointNum;
   t[tidx].thePoints[1] = p2->thePointNum;
   t[tidx].thePoints[2] = p3->thePointNum;
}

//----//----//----//----//----//----//
// Create more triangles by going around the perimeter once
//   and connecting edge points that can 'see' each other.
// Returns how many more were created
static long
Convexify(PointList *list, Triangle t[], long tCount)
{
   Point3DPtr *firstpt, *pt1, *pt2, *pt3;
   long edgePtCount = GetEdgePointCount(list);
   long moreTriangles = 0;
   firstpt = pt1 = GetFirstEdgePoint(list);
   pt2 = GetNextEdgePoint(list, pt1);
   ASSERT(pt2 != nil);
   do   {
      pt3 = GetNextEdgePoint(list, pt2);
      ASSERT(pt3 != nil);
      if (Concave(*pt1, *pt2, *pt3))
         {
         AddTriangle(t, tCount, *pt1, *pt2, *pt3);
         tCount++;
         moreTriangles++;
         RemoveEdgePoint(list, pt2);
         pt1 = pt3;
         if (-edgePtCount > 2)
            pt2 = GetNextEdgePoint(list, pt1);
         }
      else {
         pt1 = pt2;
         pt2 = pt3;
         }
      } while (-edgePtCount > 2);
   // last two wrap around, putting p1 into p3 and p2 positions
   if (*pt2 == nil)   // last triangle was concave
      {
      pt2 = firstpt;
      pt3 = GetNextEdgePoint(list, firstpt);
      if (Concave(*pt1, *pt2, *pt3))
         {
         AddTriangle(t, tCount, *pt1, *pt2, *pt3);
         tCount++;
         moreTriangles++;
         RemoveEdgePoint(list, pt2);
         }
      }
   else {
      pt3 = firstpt;
      if (Concave(*pt1, *pt2, *pt3))
         {
         AddTriangle(t, tCount, *pt1, *pt2, *pt3);
         tCount++;
         moreTriangles++;
         RemoveEdgePoint(list, pt2);
         }
      else {
         pt1 = pt2;
         pt2 = pt3;
         pt3 = GetNextEdgePoint(list, pt2);
         if (Concave(*pt1, *pt2, *pt3))
            {
            AddTriangle(t, tCount, *pt1, *pt2, *pt3);
            tCount++;
            moreTriangles++;
            RemoveEdgePoint(list, pt2);
            }
         }
      }
   // reduce the count of points on the perimeter by the number
   //   of triangles we created this pass
   SetEdgePointCount(list, 
               GetEdgePointCount(list) - moreTriangles);
   return moreTriangles;
}

//----//----//----//----//----//----//
// Interconnect more 'edge' points into triangles
// Returns new triangle count
static long
MakeMoreTriangles(Triangle t[], long tCount, 
   const Point3D p[], PointList *listp)
{
#pragma unused (p)
   long moreTriangles = 0;
   do   {
      moreTriangles = Convexify(listp, t, tCount);
      tCount += moreTriangles;
      } while (moreTriangles > 0);
   DisposeList(listp);
   return tCount;
}
//----//----//----//----//----//----//
// Note: If the set of points can form a convex polygon,
//   (or the mid-most point is on the outside for any reason), 
//   then this algorithm would produce an "overlapping triangle" 
//   because one of its angles is greater than 180 degrees (i.e., 
//   it is upside down) without the ConcaveAngle check.
// Returns how many triangles were made.  This should be
//   tCount, unless there was an inverted triangle, in which case
//   it will be tCount - 1
static long
MakePerimeterConnections(Triangle t[], const long tCount, 
      const Point3D p[], const PointNum cnum, PointList *listp)
{
   long i, badIndex = -1;
   double angleLast = *(double *)&t[0].thePoints[1];
   double angleLastOriginal = angleLast;   // save for wraparound test
   double angleNext;
   for (i = 0; i < tCount - 1; i++)
      {
      angleNext = *(double *)&t[i + 1].thePoints[1];
      if (ConcaveAngle(angleNext - angleLast))
         {
         t[i].thePoints[2] = t[i + 1].thePoints[0];
         t[i].thePoints[1] = cnum;
         angleLast = angleNext;
         }
      else {
         /* we can have only ONE inverted triangle to skip */
         ASSERT(badIndex == -1);
         badIndex = i;
         }
      }
   // wrap around to the beginning
   angleNext = angleLastOriginal;
   if (ConcaveAngle(angleNext - angleLast))
      {
      t[tCount - 1].thePoints[2] = t[0].thePoints[0];
      t[tCount - 1].thePoints[1] = cnum;
      }
   else
      badIndex = tCount - 1;
   MakeListOfEdgePoints(t, tCount, (void *) p, badIndex, listp);
   // account for possible bad triangle
   if (badIndex != -1)
      {   // shift all triangles above badIndex down one
      BlockMoveData((Ptr) &t[badIndex+1], (Ptr) &t[badIndex], 
            (tCount - 1 - badIndex) * sizeof(Triangle));
      return tCount - 1;
      }
   return tCount;
}

//----//----//----//----//----//----//
// Make the triangles that connect each point with the center point
// Return the number of triangles created (pCount - 1 or 2)
static long
MakeRadialTriangles(long center, const Point3D p[], long pCount, Triangle t[])
{
   long i, tCount;
   PointList list;
   for (i = 0; i < center; i++)
      MakeRadialConnection(p, i, center, t, i);
   // don't connect center with itself!
   for (i = center + 1; i < pCount; i++)
      MakeRadialConnection(p, i, center, t, i - 1);
   tCount = pCount - 1;
   SortTriangles(t, tCount);
   tCount = MakePerimeterConnections(t, tCount, p, 
         IdxToPtNum(p, center), &list);
   tCount = MakeMoreTriangles(t, tCount, p, &list);
   return tCount;
}

#if MYDEBUG
static void
DbgWriteTriangles(long c, const Point3D p[], Triangle t[], 
         long tCount)
{
   FILE *dbgf = fopen("triangles.out", "w");
   long i;
   const Point2D *pt = &(p[c].thePoint);
   fprintf(dbgf, "center = %d (%f, %f)\n\n", c, pt->x, pt->y);
   fprintf(dbgf, 
         "\n tri   \tp0   \tp1   \tp2   \t(x, y) of p0\n");
   for (i = 0; i < tCount; i++)
      {
      const Point2D *pt0;
      PointNum pnum0 = t[i].thePoints[0];
      pt0 = &(p[PtNumToIdx(pnum0)].thePoint);
      fprintf(dbgf, "%d   \t%d   \t%d   \t%d   \t(%f, %f)\n", 
               i, pnum0, t[i].thePoints[1], t[i].thePoints[2], 
            pt0->x, pt0->y);
      }
   fclose(dbgf);
}
#endif

Neighbor Mapping
#pragma mark == Neighbor Mapping ==

// This mapping helps iterate over the neighbors of a point

#define kEndOfNeighborList   (-1)
#define kMaxSmallNeighbors   (3)   // later 5-7
#define kExtraNeighborBytes   (2)   // later 32 (bytes = 16 more neighbors)
#define kLastSmallNeighbor   (kMaxSmallNeighbors - 1)

typedef struct NMap {
   short**   moreNeighborsH;   // excess neighbors (more than kMaxSmallNeighbors)
   short   nCount;         // count of neighbors
   short   smallNeighbors[kMaxSmallNeighbors];
   } NeighborMap;

static NeighborMap gNeighborMap[kMaxPoints];
static long gpCount;

static void
ClearNeighborMap(const long pCount)
{
   long i;
   gpCount = pCount;   // for deallocating later
   for (i = 0; i < pCount; i++)
      {
      gNeighborMap[i].moreNeighborsH = nil;
      gNeighborMap[i].nCount = 0;
#if MYDEBUG
      gNeighborMap[i].smallNeighbors[0] = kGarbage;
#endif
      }
}

//----//----//----//----//----//----//
// add pt2 to pt1's neighborlist
static void
Add1Neighbor(short pt1, short pt2)
{
   long i, count = gNeighborMap[pt1].nCount;
   short *np = gNeighborMap[pt1].smallNeighbors;
   long stop = (count > kMaxSmallNeighbors) 
                                 ? kMaxSmallNeighbors : count;
   short **h;
   for (i = 0; i < stop; i++)
      if (np[i] == pt2)
         return;   // already a neighbor
   
   if (count < kMaxSmallNeighbors)
      {   // there is room in the small neighbor list
      gNeighborMap[pt1].smallNeighbors[count] = pt2;
      gNeighborMap[pt1].nCount = count + 1;
      return;
      }
   else if (count == kMaxSmallNeighbors)
      {   // time to allocate Handle for more neighbors
      ASSERT(gNeighborMap[pt1].moreNeighborsH == nil);
      h = (short **) NewHandle(kExtraNeighborBytes);
      if (h == nil)
         DebugStr("\p couldn't allocate extra neighbors handle");
      gNeighborMap[pt1].moreNeighborsH = h;
      **h = pt2;
      gNeighborMap[pt1].nCount = count + 1;
      return;
      }
   
   ASSERT(GetHandleSize((Handle) gNeighborMap[pt1].moreNeighborsH) 
         >= 2 *(count - kMaxSmallNeighbors));
   np = *gNeighborMap[pt1].moreNeighborsH;
   stop = count - kMaxSmallNeighbors;
   for (i = 0; i < stop; i++)
      if (np[i] == pt2)
         return;   // already a neighbor
   
   // didn't find pt2 in neighbor list, we'll have to add it
   h = gNeighborMap[pt1].moreNeighborsH;
   // check to see if we need to resize handle
   ASSERT(stop * 2 <= GetHandleSize((Handle) h));
   if (stop * 2 == GetHandleSize((Handle) h))
      {
      SetHandleSize((Handle) h, stop * 4);
      if (GetHandleSize((Handle) h) != stop * 4)
         DebugStr("\p couldn't resize handle for more neighbors!");
      }
   // add to handle list
   *((*h) + stop) = pt2;
   gNeighborMap[pt1].nCount = count + 1;
}

//----//----//----//----//----//----//
// add pt2 to pt1's neighborlist and pt1 to pt2's
static void
AddNeighbors(short pt1, short pt2)
{
   Add1Neighbor(pt1, pt2);
   Add1Neighbor(pt2, pt1);
}

static void
LockNeighborHandles(void)
{
   long i;
   for (i = 0; i < gpCount; i++)
      if (gNeighborMap[i].nCount > kMaxSmallNeighbors)
         {   // must have handle when we have more neighbors
         ASSERT(gNeighborMap[i].moreNeighborsH != nil);
         HLock((Handle) gNeighborMap[i].moreNeighborsH);
         }
      else   // no handle when neighbors fit in small array
         ASSERT(gNeighborMap[i].moreNeighborsH == nil);
}

//----//----//----//----//----//----//
// Ignores center point because our algorithm will first use 
//   the center to find an initial solution.  Therefore no 
//   around-the-edge solution will need to go through the center.
static void
MakeNeighborMap(const Triangle t[], const long tCount,
                           const long pCount)
{
   long i = -1;
   ClearNeighborMap(pCount);
   while (t[++i].thePoints[1] == gCenterIdx)
      AddNeighbors(PtNumToIdx(t[i].thePoints[0]), 
            PtNumToIdx(t[i].thePoints[2]));
   for (; i < tCount; i++)
      {
      AddNeighbors(PtNumToIdx(t[i].thePoints[0]), 
            PtNumToIdx(t[i].thePoints[1]));
      AddNeighbors(PtNumToIdx(t[i].thePoints[1]), 
            PtNumToIdx(t[i].thePoints[2]));
      AddNeighbors(PtNumToIdx(t[i].thePoints[0]), 
            PtNumToIdx(t[i].thePoints[2]));
      }
   LockNeighborHandles();
}

static void
DisposeNeighborMap()
{
   long i;
   for (i = 0; i < gpCount; i++)
      if (gNeighborMap[i].nCount > kMaxSmallNeighbors)
         DisposeHandle((Handle) gNeighborMap[i].moreNeighborsH);
}

static inline long
FirstNeighbor(long pti)
{
   ASSERT(gNeighborMap[pti].nCount > 0);
   return gNeighborMap[pti].smallNeighbors[0];
}

//----//----//----//----//----//----//
// returns next neighbor's point index
// searches for previous neighbor in list and returns the next one
// or kEndOfNeighborList (-1) if there is no next one
static long
NextNeighbor(long pti, long neighbor)
{
   long i, count = gNeighborMap[pti].nCount;
   short *np = gNeighborMap[pti].smallNeighbors;
   long stop = (count > kMaxSmallNeighbors) ? 
                           kMaxSmallNeighbors : count;
   short **h;
   for (i = 0; i < stop; i++)
      if (np[i] == neighbor)
         break;   // found neighbor
   if (i < stop)
      {   // found neighbor in small list
      if (i + 1 < stop)   // there are more in the small list
         return gNeighborMap[pti].smallNeighbors[i + 1];
      // else, there are no more in the small list
      if (i + 1 < kMaxSmallNeighbors)   // was there room for more?
         return kEndOfNeighborList;   // then, that was the last one!
      // else, found at end of a full small list
      if (i + 1 < count)   // are there more neighbors?
         {   // next neighbor is the first in the Handle
         h = gNeighborMap[pti].moreNeighborsH;
         ASSERT(h != nil);
         return **h;
         }
      // else, no more at all
      return kEndOfNeighborList;
      }
   // not found in small list
   if (count == kMaxSmallNeighbors)   // there are no more
      return kEndOfNeighborList;
   // have to search the handle's entries
   np = *gNeighborMap[pti].moreNeighborsH;
   stop = count - kMaxSmallNeighbors;
   for (i = 0; i < stop; i++)
      if (np[i] == neighbor)
         break;   // found neighbor
   ASSERT(i < stop);   // otherwise neighbor wasn't found! (misuse of this routine)
   // check to see if we are at end of neighbor list
   if (i + 1 < stop)   // there are more in handle's list
      return np[i + 1];   // next neighbor
   else            // found neighbor was the last one
      return kEndOfNeighborList;
}

InitTerrainMap
// Interconnect the points into triangles of my choosing
// My strategy is to make thin triangles from every point to
//   a central point.  This way there is always a two-step (max)
//   path between any two points, and that path won't have much
//   elevation change.
// Then I improve that set by filling in the edges so that
//   the perimeter is concave.  This way, alternate paths may
//   be found between some pairs that are shorter than going
//   through the center.
long /*numTriangles*/ 
InitTerrainMap(
   const Point3D thePoints[],
   long numPoints,
   Triangle theTriangles[])
{
   long i, numTriangles;
   long center;
#if !INPUT_IS_SORTED
   MakePtNumToIdxMap(thePoints, numPoints);
#endif
   center = FindMiddleDotIdx(thePoints, numPoints);
   gCenterIdx = center;
   numTriangles = MakeRadialTriangles(center, thePoints, 
         numPoints, theTriangles);
#if MYDEBUG
   DbgWriteTriangles(center, thePoints, 
            theTriangles, numTriangles);
#endif
   // now number the triangles
   for (i = 0; i < numTriangles; i++)
      theTriangles[i].theTriangleNum = i;
   MakeNeighborMap(theTriangles, numTriangles, numPoints);
   return numTriangles;
}

TermTerrainMap
// release anything allocated in initialization
void 
TermTerrainMap(void)
{
#if !INPUT_IS_SORTED
   DisposePtNumToIdxMap();
#endif
   DisposeNeighborMap();
}

ContainsPoint
// Return true if the point (x,y) is one of the points
static Boolean
ContainsPoint(const Point3D p[], const PointNum pn[3], 
   double x, double y)
{
   long j;
   for (j = 0; j < 3; j++)
      {
      long pti = PtNumToIdx(pn[j]);
      if (p[pti].thePoint.x == x &&
         p[pti].thePoint.y == y)
         return true;
      }
   return false;
}

FindTriangleContaining
// Return the index of the triangle containing both
//   point 1 (x1, y1) and point 2 (x2, y2)
static long
FindTriangleContaining(const Point3D p[], 
   const Triangle t[], long tCount, 
   double x1, double y1,    // point 1
   double x2, double y2)      // point 2
{
   long i;
   if (x1 == x2 && y1 == y2)
      return kNoTriangle;   // points are the same
   for (i = 0; i < tCount; i ++)
      if (ContainsPoint(p, t[i].thePoints, x1, y1) &&
         ContainsPoint(p, t[i].thePoints, x2, y2))
         return i;
   DebugStr("\p didn't find the triangle!");
   return -2;   // failure!
}

FindPtIdx
// Find the index of the point with coordinates (ptx, pty)
// This is a linear search through the point list, don't do
//   it very often!
static long
FindPtIdx(const Point3D p[], long pCount, 
      double ptx, double pty)
{
   long i;
   for (i = 0; i < pCount; i++)
      if (p[i].thePoint.x == ptx &&
         p[i].thePoint.y == pty)
         return i;
   DebugStr("\p point not found anywhere!");
   return -1;
}

CostBetween
// returns the cost between two points
// computed as per Challenge Statement: the distance between
//   the two (2D) points plus ten times the height difference
//   (as an absolute value).
static double
CostBetween(long ptAi, long ptBi, const Point3D p[])
{
   double dx, dy, dht;
   dht   = p[ptAi].ht;
   dx      = p[ptAi].thePoint.x;
   dy      = p[ptAi].thePoint.y;
   dht   -= p[ptBi].ht;
   dx      -= p[ptBi].thePoint.x;
   dy      -= p[ptBi].thePoint.y;
   dht   *= 10.0;
   dx      *= dx;
   dy      *= dy;
   if      (dht < 0.0)
      dht = -dht;
   return sqrt(dx + dy) + dht;
}

CostOfSegmentPath
// returns cost of whole path (given as list of Segments)
// computed by adding cost between the startingPoint and the
//   endingPoint of each Segment.
static double
CostOfSegmentPath(Segment s[], long sCount, 
      const Point3D p[], const long pCount)
{
   double total = 0.0;
   long i;
   long ptAi = FindPtIdx(p, pCount, 
         s[0].startingPoint.x, s[0].startingPoint.y);
   for (i = 0; i < sCount; i++)
      {
      long ptBi = FindPtIdx(p, pCount, 
            s[i].endingPoint.x, s[i].endingPoint.y);
      total += CostBetween(ptAi, ptBi, p);
      ptAi = ptBi;
      }
   return total;
}

Search Queue & Paths
#pragma mark == Search Queue & Paths ==
// This structure is the heart of my depth-first-search
// It is both a search queue element and a path element
typedef struct QE {
   struct QE *      nextSearchSQ;    // 32K max (+ 2 sentries)
//   short         ptIdx;            // 32K max
   unsigned short   nextPathQEi;     // 32K max (+ 2 sentries)
   short         refCount;           // path points are shared
   double         costSoFar;         // total cost of folowing this path
   } SearchQueueElem, *SearchQueue, *Path, **SearchQueuePtr;
#define IdxOfPath(p)      ((p) - gQ)
#define IdxOfSQ(q)         ((q) - gQ)
#define CostOfPath(p)      ((p)->costSoFar)
#define Idx2Path(ptidx)      (&(gQ[ptidx]))
#define Idx2SQ(qidx)      (&(gQ[qidx]))
#define NextSQOf(q)         ((q)->nextSearchSQ)
#define NextSQIdxOf(q)      (IdxOfSQ(NextSQOf(q)))
#define SetNextSQOf(q,nq)   (NextSQOf(q) = (nq))
#define NextPathIdxOf(p)   ((p)->nextPathQEi)
#define NextPathOf(p)      (Idx2Path(NextPathIdxOf(p)))
#define SetNextPathOf(p,np)   (NextPathIdxOf(p) = IdxOfPath(np))
#define RefCountOf(p)      ((p)->refCount)
#define kMaxQE         (kMaxPoints)
#define kLastValidQEi   (kMaxQE - 1)
#define kLastPath      (kMaxQE + 1)
#define kLastQE         (kMaxQE + 2)
static SearchQueueElem gQ[kMaxQE + 3];
// Sentry values (not nil, so I can tell whether an element is
//   in a path or queue, even at the end of it)
static const SearchQueue gkLastSQ = &gQ[kLastQE];
static const Path gkLastPath = &gQ[kLastPath];
//----//----//----//----//----//----//
static void
InitSearchQueue(SearchQueuePtr qp, const long pCount)
{
   long i;
   for (i = 0; i < pCount; i++)
      {
      gQ[i].nextSearchSQ = nil;
      gQ[i].refCount = 0;
#if MYDEBUG
      gQ[i].nextPathQEi = kGarbage;
      gQ[i].costSoFar = (double) kGarbage;
#endif
      }
   *qp = gkLastSQ;
}

//----//----//----//----//----//----//
static void
DeInitSearchQueue(SearchQueuePtr qp)
{
#pragma unused(qp)
}
IsEmptySearchQueue
static inline Boolean
IsEmptySearchQueue(SearchQueuePtr qp)
{
   ASSERT(qp != nil);
   ASSERT(*qp >= &gQ[0]);
   ASSERT(*qp <= gkLastSQ);
   ASSERT(*qp != gkLastPath);
   return (*qp == gkLastSQ);
}

//----//----//----//----//----//----//
static inline Boolean
AlreadyInSearchQueue(Path p)
{
   ASSERT(p != nil);
   ASSERT(p != gkLastSQ);
   ASSERT(p != gkLastPath);
   return (nil != NextSQOf(p));
}

//----//----//----//----//----//----//
// Add to search queue in sorted order (least cost at front)
static void
AddToSearchQueue(SearchQueuePtr qp, Path p)
{
   double pCost;
   SearchQueue q, lastq;
   ASSERT(qp != nil);
   ASSERT(*qp != gkLastPath);
   ASSERT(p != nil);
   ASSERT(p != gkLastSQ);
   ASSERT(p != gkLastPath);
   if (*qp == gkLastSQ)
      {
      *qp = p;
      SetNextSQOf(p, gkLastSQ);
      return;
      }
   lastq = nil;
   q = *qp;
   pCost = CostOfPath(p);
   while (q != gkLastSQ && CostOfPath(q) < pCost)
      {
      lastq = q;
      q = NextSQOf(q);
      }
   if (lastq == nil)
      *qp = p;   // add p to head of list
   else               // insert p after lastq
      SetNextSQOf(lastq, p);
   SetNextSQOf(p, q);
}

//----//----//----//----//----//----//
// Remove from the queue the least cost path
// Hint: it's at the front!
// Does NOT remove it from path NOR releases it
// DOES set nextSQ to nil
static inline Path
RemoveBestElem(SearchQueuePtr qp)
{
   Path p = *qp;
   ASSERT(p != nil);
   ASSERT(p != gkLastSQ);
   ASSERT(p != gkLastPath);
   *qp = NextSQOf(p);
   SetNextSQOf(p, nil);
   return p;
}

//----//----//----//----//----//----//
// Remove from the queue the given path
// Does NOT remove it from path NOR releases it
// DOES set nextSQ to nil
static void
RemoveFromSearchQueue(SearchQueuePtr qp, Path p)
{
   Path seek, seekLast;
   ASSERT(qp != nil);
   ASSERT(*qp != gkLastSQ);
   ASSERT(*qp != gkLastPath);
   ASSERT(p != nil);
   ASSERT(p != gkLastSQ);
   ASSERT(p != gkLastPath);
   seekLast = nil;
   seek = *qp;
   while (seek != p)
      {
      seekLast = seek;
      seek = NextSQOf(seek);
      ASSERT(seek != nil);
      ASSERT(seek != gkLastSQ);
      }
   if (seekLast == nil)   // p was first in list
      *qp = NextSQOf(p);
   else   // make the node before p point to the one after p
      SetNextSQOf(seekLast, NextSQOf(p));
   SetNextSQOf(p, nil);
}

//----//----//----//----//----//----//
static Path
MakeFirstPath(long pointIdx)
{
   Path p = Idx2Path(pointIdx);
   ASSERT(p >= gQ);
   ASSERT(p <= &(gQ[kLastValidQEi]));
   SetNextPathOf(p, gkLastPath);
   SetNextSQOf(p, nil);
   RefCountOf(p) = 64;   // anomoly to prevent loops at beginning
   CostOfPath(p) = 0.0;
   return p;
}

//----//----//----//----//----//----//
static inline void
AddPath(Path oldp, Path newp, double newTotalCost)
{
   ASSERT(oldp != nil);
   ASSERT(newp != nil);
   ASSERT(newTotalCost > CostOfPath(oldp));
   ASSERT(RefCountOf(newp) == 0);
   SetNextPathOf(newp, oldp);
   CostOfPath(newp) = newTotalCost;
   RefCountOf(oldp)++;      // oldp becomes interior node
}

//----//----//----//----//----//----//
static void
ReleasePath(Path p)
{
   ASSERT(p != nil);
   ASSERT(p != gkLastSQ);
   if (p == gkLastPath)
      return;
   if (RefCountOf(p) == 0)
      ReleasePath(NextPathOf(p));
   else
      RefCountOf(p)-;
}

//----//----//----//----//----//----//
// Returns the number of segments, i.e., jumps between path nodes
static long
PathLength(Path p)
{
   long len = -1;
   ASSERT(p != nil);
   ASSERT(p != gkLastPath);
   ASSERT(p != gkLastSQ);
   do   {
      p = NextPathOf(p);
      ++len;
      } while (p != gkLastPath);
   return len;
}

//----//----//----//----//----//----//
// Record the segments that make of this (newer) better path
// The path is from end to start, so work backwards
// NOTE: this will fail if the path is size zero
static void
RecordPath(Segment s[], long *sCount, Path path, 
      const Point3D p[], const Triangle t[], const long tCount)
{
   double xE, yE, xS, yS;
   long len = *sCount = PathLength(path);
   long triNum;
   xE = p[IdxOfPath(path)].thePoint.x;
   yE = p[IdxOfPath(path)].thePoint.y;
   ASSERT(len > 0);
   do   {
      path = NextPathOf(path);
      len-;
      xS = p[IdxOfPath(path)].thePoint.x;
      yS = p[IdxOfPath(path)].thePoint.y;
      triNum = FindTriangleContaining(p, t, 
         tCount, xS, yS, xE, yE);
      ASSERT(triNum != kNoTriangle);
      s[len].theTriangleNum   = triNum;
      s[len].startingPoint.x   = xS;
      s[len].startingPoint.y   = yS;
      s[len].endingPoint.x   = xE;
      s[len].endingPoint.y   = yE;
      xE = xS;
      yE = yS;
      } while (len > 0);
}

#if MYDEBUG
static long
FindPtInTriangle(const Point3D p[], const PointNum pn[3], 
   double x, double y)
{
   long j;
   for (j = 0; j < 3; j++)
      {
      long pti = PtNumToIdx(pn[j]);
      if (p[pti].thePoint.x == x &&
         p[pti].thePoint.y == y)
         return pn[j];
      }
   DebugStr("\p couldn't find point in triangle!");
   return -1;
}

static void
PrintPath(Segment s[], long sCount, const Point3D p[], const Triangle t[])
{
   long i;
   for (i = 0; i < sCount; i++)
      {
      long triNum, ptNumFrom, ptNumTo;
      triNum = s[i].theTriangleNum;
      ptNumFrom = FindPtInTriangle(p, t[triNum].thePoints, 
            s[i].startingPoint.x, s[i].startingPoint.y);
      ptNumTo   = FindPtInTriangle(p, t[triNum].thePoints, 
            s[i].endingPoint.x,   s[i].endingPoint.y);
      printf("seg %d \t%d \t%d \t%d", 
            i, triNum, ptNumFrom, ptNumTo);
      printf(" cost=%f\n", 
   CostBetween(PtNumToIdx(ptNumFrom), PtNumToIdx(ptNumTo), p));
      }
}
#endif

EvaluateFinishedPath
// Deal with a path to the end point
// If it is a better path,
//      record it, release the old best path, and return the new value
//   otherwise
//      release the path (it wasn't better), and return the old value
// Return the current best path in *bestPath
static double
EvaluateFinishedPath(Segment s[], long *sCount, 
      const Point3D p[], const Triangle t[], const long tCount, 
      Path path, Path *bestPath, double bestCost)
{
   double newCost;
   newCost = CostOfPath(path);
   if (newCost < bestCost)
      {   // found a better path to end!!
      RecordPath(s, sCount, path, p, t, tCount);
#if MYDEBUG
      printf("better path:\n");
      PrintPath(s, *sCount, p, t);
#endif
      bestCost = newCost;
      ASSERT(bestPath != nil);
      if (*bestPath != nil)
         ReleasePath(*bestPath);
      *bestPath = path;
      }
   else
      ReleasePath(path);
   return bestCost;
}

ExpandSearch
// Expand the search from the given path endpoint 'path'
// Expand by following each node that is neighbor to 'path'
// Expand just one level, then return.
static void
ExpandSearch(SearchQueuePtr qp, const Point3D p[], 
      Path path, long pathIdx, double bestCost)
{
   long follow;
   // expand search from partial path ending at 'path'
   for (follow = FirstNeighbor(pathIdx);
         follow != kEndOfNeighborList;
         follow = NextNeighbor(pathIdx, follow))
      {
      double newCost;
      Path followPath = Idx2Path(follow);
      ASSERT(follow != pathIdx);
                     // don't go back on yourself (problem with neighbor logic)
      if (RefCountOf(followPath) > 0)
         {         // it's an interior node, 
         ASSERT( !AlreadyInSearchQueue(followPath) );
                  // should not be in search path
         continue;   // skip it
         }
      newCost = CostOfPath(path) + CostBetween(pathIdx, follow, p);
      if (newCost < bestCost)
         {   // survived cutoff
         if (AlreadyInSearchQueue(followPath))
                     // follow exists in another path already
            if (newCost >= CostOfPath(followPath))
                     // new path not an improvement
               continue;
            else   // remove to add in proper (sorted) place
               RemoveFromSearchQueue(qp, followPath);
         AddPath(path, followPath, newCost);
         AddToSearchQueue(qp, followPath);
         }
      }
}

SearchAlternatePath
// Search for a better path from start to end than the 
//   through-the-center route already in theSegments
// If found, fill in theSegments and return its length
//   else, just return the old length (sCount)
static long
SearchAlternatePath(Segment s[], long sCount, 
      const Point3D p[], const long pCount, 
      const Triangle t[], const long tCount,
      long ptIdxStart, long ptIdxEnd)
{
   double bestCost = CostOfSegmentPath(s, sCount, p, pCount);
   SearchQueue q;
   Path pathStartPtr, bestPath = nil;
   InitSearchQueue(&q, pCount);
   pathStartPtr = MakeFirstPath(ptIdxStart);
   AddToSearchQueue(&q, pathStartPtr);
   do   {
      Path path = RemoveBestElem(&q);
      long pathIdx = IdxOfPath(path);
      if (pathIdx == ptIdxEnd)   // found a path to end!
         bestCost = EvaluateFinishedPath(s, &sCount, 
               p, t, tCount, path, &bestPath, bestCost);
      else
         ExpandSearch(&q, p, path, pathIdx, bestCost);
      } while (!IsEmptySearchQueue(&q));
   DeInitSearchQueue(&q);
   return sCount;
}

FindAPath
// Find a minimal cost path between the two points
// First: 
// Connect the start to the middle
// Connect the middle to the end
// Then:
// Do a breadth-first search from start
// Use the simple through-the-center path as an optimizing cutoff
long /*numSegments*/ 
FindAPath(
   const Point3D thePoints[],
   long numPoints,
   const Triangle theTriangles[],
   long numTriangles,
   const Point2D pathStart,
   const Point2D pathEnd,
   Segment theSegments[]
) {
#pragma unused (numPoints)
   double x1, y1, xc, yc;
   long numSegments = 0;
   long triNumStart, triNumEnd;
   PointNum ptIdxStart, ptIdxEnd;
   x1 = pathStart.x;
   y1 = pathStart.y;
   xc = thePoints[gCenterIdx].thePoint.x;
   yc = thePoints[gCenterIdx].thePoint.y;
   triNumStart = FindTriangleContaining(thePoints, theTriangles, 
         numTriangles, x1, y1, xc, yc);
   if (triNumStart != kNoTriangle)
               // triNum == kNoTriangle means pathStart IS center
      {
      theSegments[0].theTriangleNum   = triNumStart;
      theSegments[0].startingPoint   = pathStart;
      theSegments[0].endingPoint.x   = xc;
      theSegments[0].endingPoint.y   = yc;
      numSegments = 1;
      }
   ptIdxStart = FindPtIdx(thePoints, numPoints, x1, y1);
   x1 = pathEnd.x;
   y1 = pathEnd.y;
   triNumEnd = FindTriangleContaining(thePoints, theTriangles, 
         numTriangles, x1, y1, xc, yc);
   if (triNumEnd != kNoTriangle)
               // triNum == kNoTriangle means pathEnd IS center
      {
      theSegments[numSegments].theTriangleNum   = triNumEnd;
      theSegments[numSegments].startingPoint.x   = xc;
      theSegments[numSegments].startingPoint.y   = yc;
      theSegments[numSegments].endingPoint       = pathEnd;
      numSegments++;
      }
#if MYDEBUG
   printf("starting point: %f, %f\n", pathStart.x, pathStart.y);
   printf("ending point:   %f, %f\n", pathEnd.x,   pathEnd.y);
   printf("initial path through center:\n");
   PrintPath(theSegments, numSegments, thePoints, theTriangles);
#endif
   if (numSegments > 1)   // can't improve a path of length one
      {
      ptIdxEnd = FindPtIdx(thePoints, numPoints, x1, y1);
      numSegments = SearchAlternatePath(theSegments, numSegments, 
            thePoints, numPoints, 
            theTriangles, numTriangles, 
            ptIdxStart, ptIdxEnd);
      }
   // else SearchAlternatePath is unnecessary (and fails!)
   return numSegments;
}
 
AAPL
$524.94
Apple Inc.
+5.93
MSFT
$40.01
Microsoft Corpora
-0.39
GOOG
$536.10
Google Inc.
-20.44

MacTech Search:
Community Search:

Software Updates via MacUpdate

VMware Fusion 6.0.3 - Run Windows apps a...
VMware Fusion allows you to create a Virtual Machine on your Mac and run Windows (including Windows 8.1) and Windows software on your Mac. Run your favorite Windows applications alongside Mac... Read more
Tweetbot 1.5.1 - Popular iOS twitter cli...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
Mac DVDRipper Pro 4.1.7 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more

Latest Forum Discussions

See All

Have a Special Dead Trigger 2 Easter Bas...
Have a Special Dead Trigger 2 Easter Basket Full of Goodies, Courtesy of Madfinger Games Posted by Rob Rich on April 18th, 2014 [ permalink ] Dead Trigger 2 | Read more »
Almost All of Playdek’s Library is on Sa...
Almost All of Playdek’s Library is on Sale Right Now, and You Should Check it Out Posted by Rob Rich on April 18th, 2014 [ permalink ] Playdek has released quite a few great iOS ports of board and card games over the years, and now most of them... | Read more »
Zynga Launches Brand New Farmville Exper...
Zynga Launches Brand New Farmville Experience with Farmville 2: Country Escape Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
David. Review
David. Review By Cata Modorcea on April 18th, 2014 Our Rating: :: MINIMALISTIC IN A DIFFERENT WAYUniversal App - Designed for iPhone and iPad David is a minimalistic game wrapped inside of a soothing atmosphere in which the hero... | Read more »
Eyefi Unveils New Eyefi Cloud Service Th...
Eyefi Unveils New Eyefi Cloud Service That Allows Users to Share Media Across Personal Devices Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
Tales from the Dragon Mountain: The Lair...
Tales from the Dragon Mountain: The Lair Review By Jennifer Allen on April 18th, 2014 Our Rating: :: STEADY ADVENTURINGiPad Only App - Designed for the iPad Treading a safe path, Tales from the Dragon Mountain: The Lair is a... | Read more »
Yahoo Updates Flickr App with Advanced E...
Yahoo Updates Flickr App with Advanced Editing Features and More Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
My Incredible Body - A Kid's App to...
My Incredible Body - A Kid's App to Learn about the Human Body 1.1.00 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1.00 (iTunes) Description: Wouldn’t it be cool to look inside yourself and see what was going on... | Read more »
Trials Frontier Review
Trials Frontier Review By Carter Dotson on April 18th, 2014 Our Rating: :: A ROUGH LANDINGUniversal App - Designed for iPhone and iPad Trials Frontier finally brings the famed stunt racing franchise to mobile, but how much does its... | Read more »
Evernote Business Notebook by Moleskin I...
Evernote Business Notebook by Moleskin Introduced – Support Available in Evernote for iOS Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Free HopTo 2.2 Helps Enhance Your Productivit...
The HopTo app helps you do more on your iPad by providing more and easier adaccess to files and documents. Version 2.2 adds Egnyte and HopTo’s Mac OSX File Connector. If you already have the hopTo... Read more
National Distracted Driving Awareness Month:...
As the country recognizes National Distracted Driving Awareness Month, Sprint is reminding wireless consumers to focus on driving while behind the wheel, to not text or email while driving, and to... Read more
13-inch 2.4GHz Retina MacBook Pro available f...
Abt has the 13″ 2.4GHz 128GB Retina MacBook Pro available for $1229 including free shipping. Their price is $70 off MSRP. Read more
iMacs on sale for up to $160 off MSRP this we...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
iPad Airs on sale this weekend for up to $100...
Best Buy has WiFi iPad Airs on sale for $50 off MSRP and WiFi + Cellular iPad Airs on sale for $100 off MSRP on their online store for a limited time, with prices now starting at $449. Choose free... Read more
Apple restocks refurbished Mac minis starting...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Hyundai Brings Apple CarPlay To The 2015 Sona...
Hyundai Motor America has announced it will bring Apple CarPlay functionality to the 2015 Sonata. CarPlay is pitched as a smarter, safer and easier way to use iPhone in the car and gives iPhone users... Read more
Updated iPads Coming Sooner Than We Had Thoug...
MacRumors, cites KGI securities analyst Ming Chi Kuo, well-respected as an Apple product prognisticator, saying that Apple will introduce an upgraded iPad Air and iPad mini in 2014/Q3, meaning the... Read more
Toshiba Unveils New High And Low End Laptop M...
Toshiba has announced new laptop models covering both the high-end and low-end of the notebook computer spectrum. Toshiba 4K Ultra HD Laptop Toshiba’s new Satellite P55t features one of the world’s... Read more
Save up to $270 with Apple refurbished 13-inc...
The Apple Store has Apple Certified Refurbished October 2013 13″ Retina MacBook Pros available starting at $1099, with models up to $270 off MSRP. Apple’s one-year warranty is standard, and shipping... Read more

Jobs Board

*Apple* Automotive Parts Department position...
Apple Automotive is one of the fastest growing dealer…and it shows. Consider making the switch to the Apple Automotive Group today! At Apple Automotive, we Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.