Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 26, 2010 8:51:53 AM6.1 Geometric Primitives‣primitive operations‣convex hull‣closest pair‣voronoi diagram2Geometric algorithmsApplications. •Data mining.•VLSI design.•Computer vision.•Mathematical models.•Astronomical simulation.•Geographic information systems.•Computer graphics (movies, games, virtual reality).•Models of physical world (maps, architecture, medical imaging).History.•Ancient mathematical foundations.•Most geometric algorithms less than 25 years old.http://www.ics.uci.edu/~eppstein/geom.htmlairflow around an aircraft wing3‣primitive operations‣convex hull‣closest pair‣voronoi diagram4Geometric primitivesPoint: two numbers (x, y).Line: two numbers a and b. [ax + by = 1]Line segment: two points.Polygon: sequence of points.Primitive operations.•Is a polygon simple?•Is a point inside a polygon?•Do two line segments intersect?•What is Euclidean distance between two points?•Given three points p1, p2, p3, is p1!p2!p3 a counterclockwise turn?Other geometric shapes.•Triangle, rectangle, circle, sphere, cone, …•3D and higher dimensions sometimes more complicated.any line not through origin5Geometric intuitionWarning: intuition may be misleading. •Humans have spatial intuition in 2D and 3D.•Computers do not.•Neither has good intuition in higher dimensions!Q. Is a given polygon simple?we think of this algorithm sees thisno crossingsxy165872786421xy1151413121110987654321218418419419420320220xy11037288346515111314216Jordan curve theorem. [Jordan 1887, Veblen 1905] Any continuous simple closed curve cuts the plane in exactly two pieces: the inside and the outside.Q. Is a point inside a simple polygon?Application. Draw a filled polygon on the screen.6Polygon inside, outsidePuzzle. Are A and B inside or outside the maze?7Fishy mazehttp://britton.disted.camosun.bc.ca/fishmaze.pdf8Polygon inside, outsideJordan curve theorem. [Jordan 1887, Veblen 1905] Any continuous simple closed curve cuts the plane in exactly two pieces: the inside and the outside.Q. Is a point inside a simple polygon?Application. Draw a filled polygon on the screen.http://www.ics.uci.edu/~eppstein/geom.htmlQ. Does line segment intersect ray?9public boolean contains(double x0, double y0){ int crossings = 0; for (int i = 0; i < N; i++) { double slope = (y[i+1] - y[i]) / (x[i+1] - x[i]); boolean cond1 = (x[i] <= x0) && (x0 < x[i+1]); boolean cond2 = (x[i+1] <= x0) && (x0 < x[i]); boolean above = (y0 < slope * (x0 - x[i]) + y[i]); if ((cond1 || cond2) && above) crossings++; } return crossings % 2 != 0; }Polygon inside, outside: crossing numbery0 = yi+1 - yi xi+1 - xi (x0 - xi) + yixi ! x0 ! xi+1(xi, yi)(xi+1, yi+1)(x0, y0)10CCW. Given three point a, b, and c, is a-b-c a counterclockwise turn?•Analog of compares in sorting.•Idea: compare slopes.Lesson. Geometric primitives are tricky to implement.•Dealing with degenerate cases.•Coping with floating-point precision.Implementing ccwabyesacnoabYes(!-slope)ab???(collinear)ba???(collinear)ac???(collinear)ccbccbCCW. Given three point a, b, and c, is a!b!c a counterclockwise turn?•Determinant gives twice signed area of triangle.•If area > 0 then a!b!c is counterclockwise.•If area < 0, then a!b!c is clockwise.•If area = 0, then a!b!c are collinear.< 0> 011Implementing ccw! 2 " Area(a, b, c) = axay1bxby1cxcy1= (bx# ax)(cy# ay) # (by# ay)(cx# ax)(ax, ay)(bx, by)(cx, cy)(ax, ay)(bx, by)(cx, cy)12Immutable point data typepublic class Point { private final int x; private final int y; public Point(int x, int y) { this.x = x; this.y = y; } public double distanceTo(Point that) { double dx = this.x - that.x; double dy = this.y - that.y; return Math.sqrt(dx*dx + dy*dy); } public static int ccw(Point a, Point b, Point c) { int area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); if (area2 < 0) return -1; else if (area2 > 0) return +1; else return 0; } public static boolean collinear(Point a, Point b, Point c) { return ccw(a, b, c) == 0; }}cast to long to avoidoverflowing an intl1.p1l2.p113Intersect. Given two line segments, do they intersect?•Idea 1: find intersection point using algebra and check.•Idea 2: check if the endpoints of one line segment are ondifferent "sides" of the other line segment (4 calls to ccw).Sample ccw client: line intersectionnot handledl1.p2l2.p2public static boolean intersect(LineSegment l1, LineSegment l2){ int test1 = Point.ccw(l1.p1, l1.p2, l2.p1) * Point.ccw(l1.p1, l1.p2, l2.p2); int test2 = Point.ccw(l2.p1, l2.p2, l1.p1) * Point.ccw(l2.p1, l2.p2, l1.p2); return (test1 <= 0) && (test2 <= 0);}14‣primitive operations‣convex hull‣closest pair‣voronoi diagram15Convex hullA set of points is convex if for any two points p and q in the set,the line segment pq is completely in the set.Convex hull. Smallest convex set containing all the points.Properties.•"Simplest" shape that approximates set of points.•Shortest perimeter fence surrounding the points.•Smallest area convex polygon enclosing the points.convexnot convexconvex hullpqpq16Mechanical solutionMechanical convex hull algorithm. Hammer nails perpendicular to plane;stretch elastic rubber band around points.http://www.dfanning.com/math_tips/convexhull_1.gif17An application: farthest pairFarthest pair problem. Given N points in the plane, find a pair of points with the largest Euclidean distance between them.Fact. Farthest pair of points are on convex hull.18Brute-force algorithmObservation 1. Edges of convex hull of P connect pairs of points in P.Observation 2.p-q is on convex hull if all other points are counterclockwise of pq.O(N3) algorithm. For all pairs of points p and q:•Compute ccw(p, q, x) for all other points x.•p-q is on hull if all values are positive.pq19Package wrap (Jarvis march)Package wrap.•Start with point with smallest (or largest) y-coordinate.•Rotate sweep line around current point in ccw direction.•First point hit is on the hull.•Repeat.20Package wrap (Jarvis march)Implementation.•Compute angle between current point and all remaining points.•Pick smallest angle larger than current angle.•"(N) per iteration.21Jarvis march:
View Full Document
Unlocking...