ISE 390 -- Programming Challenges -- Week 12 Notes

This Week's Goals: 

	To review some basic principles of computational geometry.

Geometric Primatives

	The most elementary geometric primitive, testing whether two
	line segments intersect, is still surprisingly complicated due
	to special cases (parallel line segments, intersecting at an
	endpoint, etc.)

	This can be done in a clumsy ad hoc manner, or more cleanly by
	using a primative to test if three ordered points turn in a
	counterclockwise direction or not.

	The programs below have been lifted from Sedgwick:


struct point { int x, y; char c; };
struct line { struct point p1, p2; };
struct point polygon[Nmax];
 
int ccw(struct point p0, 
        struct point p1, 
        struct point p2 )
  {
    int dx1, dx2, dy1, dy2;
    dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;
    dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;
    if (dx1*dy2 > dy1*dx2) return +1;
    if (dx1*dy2 < dy1*dx2) return -1;
    if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
    if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) 
                                        return +1;
    return 0;
  }

int intersect(struct line l1, struct line l2)
  {
    return ((ccw(l1.p1, l1.p2, l2.p1)
            *ccw(l1.p1, l1.p2, l2.p2)) <= 0)
        && ((ccw(l2.p1, l2.p2, l1.p1)
            *ccw(l2.p1, l2.p2, l1.p2)) <= 0);
  }


Point inside a polygon test

	Draw a line through the point.   Whether this hits an even or
	odd number of edges of the polygon tells whether it in inside
	or outside.

int inside(struct point t, struct point p[], int N)
  {
    int i, count = 0, j = 0;
    struct line lt,lp;
    p[0] = p[N]; p[N+1] = p[1];
    lt.p1 = t; lt.p2 = t; lt.p2.x = INT_MAX;
    for (i = 1; i <= N; i++)
      {
        lp.p1= p[i]; lp.p2 = p[i];
        if (!intersect(lp,lt))
          {
            lp.p2 = p[j]; j = i;
            if (intersect(lp,lt)) count++;
          }
      }
    return count & 1;
  }
 

Nearest neighbor search

	Given a set of points, each has (at least one) nearest neighbor.
	The nearest neighbors can be found by exhaustive search.
	Note that all nearest neighbors appear as a subset of
	the minimum spanning tree of the points, which is in fact
	a subset of a special triangulation (the Delaunay triangulation).


Convex Hulls

	Graham's scan algorithm is the simplest, most efficient
	algorithm for convex hull in the plane.  This algorithm
	sorts the points by angle or x-coordinate and then
	incrementally inserts into the hull.  The gift-wrapping
	algorithm is an alternate way to construct the hull.

float theta(struct point p1, struct point p2)
  {
    int dx, dy, ax, ay;
    float t;
    dx = p2.x - p1.x; ax = abs(dx);
    dy = p2.y - p1.y; ay = abs(dy);
    t = (ax+ay == 0) ? 0 : (float) dy/(ax+ay);
    if (dx < 0) t = 2-t; else if (dy < 0) t = 4+t;
    return t*90.0;
  }
 
int grahamscan(point p[], int N)
  {
    int i, min, M;
    for (min = 1, i = 2; i <= N; i++)
      if (p[i].y < p[min].y) min = i;
    for (i = 1; i <= N; i++)
      if (p[i].y == p[min].y)
        if (p[i].x > p[min].x) min = i;
    swap(p, 1, min);
    shellsort(p, N);
    p[0] = p[N];
    for (M = 3, i = 4; i <= N; i++)
      {
        while (ccw(p[M], p[M-1], p[i]) >= 0) M--;
        M++; swap(p, i, M);
      }
    return M;
  }
 
int wrap(point p[], int N)
  {
    int i, min, M;
    float th, v;
    for (min = 0, i = 1; i < N; i++)
      if (p[i].y < p[min].y) min = i;
    p[N] = p[min]; th = 0.0;
    for (M = 0; M < N; M++)
      {
        swap(p, M, min);
        min = N; v = th; th = 360.0;
        for (i = M+1; i <= N; i++)
          if (theta(p[M], p[i]) > v)
            if (theta(p[M], p[i]) < th)
              { min = i; th = theta(p[M], p[min]); }
        if (min == N) return M;
      }
  }



Assigned Problems:

152 -- Find the nearest neighbor to each point in 3D.  Is it necessary
	to do better than brute force?

191 -- Test if a line segment intersects a rectangle.  Be aware of
	special cases and degeneracy.

218 -- Convex hull in a very thin disguise.

313 -- Identify the area shaded by pipes, by computing normal lines to
	circles, and merging intervals of shadows.

361 -- Which points are in triangles of other points.  Can the
	convex hull be used to avoid enumerating all triangles?