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?