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?