overviewprimitivesconvex hull algorithmscontextGeometric Algorithms2Important and far-reaching applications•models of physical worldexamples: maps, architecture, medical imaging•computer graphicsexamples: movies, games, virtual reality•mathematical modelsstay tunedAncient mathematical foundations, butmost geometric algorithms are less than 30 years oldKnowledge of fundamental algorithms is critical•use them directly•use the same design strategies for harder problems•learn how to compare and evaluate algorithmsGeometric algorithms3Humans have spatial intuition in 2D and 3D: computers do not!Example: Is a given polygon convex?Warning: intuition may not be helpful1658727864211151413121110 9 8 7 654321218418419 4 19 4 20 3 20 3 201103 7288346515111314 2 16we see theseprograms see these4Point•two numbers (x, y)#typedef struct {double x; double y;} Point;Line•two numbers a and b [ax + by = 1]Line segment•four numbers (x1, y1) and (x2, y2)•two points p0 and p1#typedef struct {Point x; Point y;} LineSegment;Polygon•sequence of pointsPoint p[N];No shortage of other geometric shapes triangle, square, circle, quadrilateral, parallelogram, ...3D and higher dimensions more complicatedElementary geometric primitives (2D)lines through origin are exceptional5Typical scenario in algorithm design: Example:Is a given polygon simple?Do two given line segments intersect?Are two given points on the same side of a given line?Is the route connecting three given points a ccw turn?Building layers of abstractionnoyesnoyesUse a more primitive operation!6Input: points p0, p1, and p2Output:1 if p0-p1-p2 is a ccw turn-1 if p0-p1-p2 is a cw turn0 if p0, p1, p2 are collinearApproach: compare slopesCCW implementation int ccw(Point p0, Point p1, 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; return 0; }slope dx2/dy2slopes are equalp0p1p2p0p1p2p0p1p2p0p1p2p0p1p2slope dx1/dy17Is the route connecting p0, p1, and p2 a ccw turn?ccw(p0, p1, p2)Are points q and r on the same side of line L?ccw(L.p0, L.p1, q) == ccw(L.p0, L.p1. r)Do line segments L and S intersect?!same(L.p0, L.p1, S) && !same(S.p0, S.p1, L)Is a given polygon simple? for(i = 0; i < N; i++) for(j = i+1; j < N; j++) if (intersect(p[i], p[j]) return 0; return 1;Layers of abstraction example (continued)noyesnoyesp0p1p2rqLLRStay tuned (next lecture) for faster implementation8Still not quite right! Bug in degenerate case with four collinear pointsDoes AB intersect CD?•on the line in the order ABCD: NO•on the line in the order ACDB: YESNeed more careful CCW implementaton•more work when dx1*dy2 == dx2*dy1 (see book)Lessons:•geometric primitives are tricky to implement•can't ignore degenerate casesLine-segment intersection implementation bugABCDABCD9Convex hull: smallest polygon enclosing a given set of pointsA polygon is convex iff every line whose endpoints are within thepolygon falls entirely within the polygonLemma: Hull must be convexRunning time of convex hull algorithms can depend on•N: number of points•M: number of points on the hull•point distributionConvex hull of a point setconvex not convex10Idea: consider points one by one•next point inside current hull—ignore•next point outside current hull—updateTwo subproblems to solve•test if point inside or outside polygon•update hull for outside pointsBoth subproblems•brute force: O(M) to check all hull points•can be improved to O(log M) with binary search•relatively cumbersome to codeRandomize: take points in random orderTotal running time: O(N log M)Incremental convex hull algorithms11Idea: presort on x for incremental algorithmEquivalent to imagining sweep line movingfrom left to right through pointsplus: eliminates “inside” testminus: have to pay cost of sortTotal cost: O(N log N)Sweep-line convex hull algorithm12Divide point set into two halves•solve subproblems recursively•merge resultsIdea 1: take points in random orderIdea 2: divide space in half (presort on one coordinate)Both O(N log N) but relatively cumbersome to codeDivide-and-conquer convex hull algorithms13Idea:•point with lowest y coordinate is on the hull•sweep line ccw anchored at current point—first point hit is on hullPackage-wrapping convex hull algorithm14Input: polygon (represented as an array of N points)Output: M (array rearranged such that first M points are convex hull)Implementation of package-wrapping algorithm int wrap(Point p[], int N) { int i, min, M; double th, v; Point t; 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++) { t = p[M]; p[M] = p[min]; p[min] = t; 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; } }find point with min y coordinatefind min angle > v2D analog of selection sort: O(NM) running timeimplementation of theta omitted (can use slope)15Idea:•sort points by angle to get simple closed polygon•scan polygon—discard points causing cw turnGraham scan convex hull algorithm16 int grahamscan(Point p[], int N) { int i, min, M; Point t; 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; t = p[1]; p[1] = p[min]; p[min] = t; quicksort(p, 1, 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++; t = p[M]; p[M] = p[i]; p[i] = t; } return M; }Input: polygon (represented as an array of N points)Output: M (array rearranged such that first M points are convex hull)Implementation of Graham scan algorithmswap “lower left” point with firstback up to include i on hullpoints in p[1]...p[N]p[0] is sentineladd i to putative hullimplementation of less uses angle with p[1]Total cost: O(N log N) (for sort).17Idea: fast test to eliminate most inside pointsquick: use quadrilateral Q min (x+y), max(x+y), min(x-y), max(x-y)quicker: use inscribed rectangle RThree-phase algorithm•pass through all points to compute R•eliminate points inside
View Full Document
Unlocking...