Computational Geometry Introduction 15-750 CMU Spring 2009 Gary Miller Boilerplate: What is Computational Geometry(CG)? Why CG in algorithms class? Where is CG used? Is it fun or boring? At present CG is the design and analysis of algorithm for geometric problems that arise on low dimensions, 2 or 3. Most algorithms work well in 2D while 3D problems are not as well understood. CG will allow us to see our old algorithms in use and see new ones. Some application of CG are: Computer Graphics images creation hidden surface removal illumination physic based simulations Robotics motion planning Geographic Information Systems Height of mountains vegetation population cities, roads, electric lines CAD/CAM computer aided design/computer aided manufacturing Computer chip design and simulations Scientific Computation Blood flow simulations Molecular modeling and simulations ---------------------------------------------------------------- Basic approach used by computers to handle complex geometric objects Decompose the object into a large number of very simple objects with simple interactions. Examples: * An image might be a 2D array of dots. * An integrated circuit is a planar triangulation. * Mickey Mouse is a surface of triangles Basic algorithmic design approaches Divide-and-Conquer * There are two different types of Divide-and-Conquer. e.g. Merge sort e.g. Quick sort * Sweep-Line in 2D. * Random Incremental ------------------------------------------------------------------ We will cover the following topics: * Introduction and primitive or atomic operations * sweep-line algorithm for line segment intersection two lectures on random incremental algorithms for: * 2D convex hull of a point set. * An expected linear time algorithm for 2D linear programming. ------------------------------------------------------------------ First we discuss what abstract object we will need and their representation Abstract Object | Representation ------------------------------------- Real Number | Floating Point, Big Number Point | Pair of Reals Line | Pair of Points, A set of constraints Line Segment | Pair of Points, A set of constraints Triangle | Triple of Points, etc ----------------------------------------------------------------- Using points to generate objects P1, ..., Pk in Real^d Linear Combinations | Subspace = \Sum \alpha_i Pi for \alpha_i \in Real Affine Combinations | Plane = \Sum \alpha_i Pi such that \sum \alpha_i = 1 for \alpha_i \in Real e.g. { \alpha P + \beta Q | \alpha + \beta = 1 } line thru P and Q Convex Combinations | Body = \Sum \alpha_i Pi such that \sum \alpha_i = 1 and \alpha_i >= 0 for \alpha_i \in Real e.g. { \alpha P + \beta Q + \gamma R | \alpha + \beta + \gamma = 1 and \alpha, \beta, \gamma >= 0 } Triangle with corners P,Q, and R ------------------------------------------------------------------ Primitive Operations 1) Equality P=Q? Can be hard! 2) Line segment intersection testing 3) Line side test Input: (P1,P2,P3) Output: True: If P3 is left of ray P1 -> P2 4) In circle test Input: (P1,P2,P3,P4) Output: True: If P4 in circle thru (P1,P2,P3) 5) Etc 2) Segments L1 = [P1,P2] and L2 = [P3,P4] Pi = ( xi ) (vector of two reals) ( yi ) Note that a convex combination of two points P1 and P2 is a new point P1 \alpha_1 + P2 \alpha_2 where \alpha_1 and \alpha_2 are non-negative and sum to 1. So L1 intersects L2 iff there exists equal convex combinations That is, there exist alpha 1, 2, 3, 4 such that: (P1, P2) ( \alpha_1 ) = (P3, P4)(\alpha_3) \alpha_2 \alpha_4 such that \alpha_1 + \alpha_2 = 1 \alpha_3 + \alpha_4 = 1 \alpha_i >= 0 for 1 <= i <= 4 This is just a system of four linear equations with four unknowns. (eliminate \alpha_1 and \alpha_3 trivially to make it two equations and two unknowns. Can solve for the formula by hand.) 3) Line side tests Input: P1,P2,P3 Output: True: If P3 is left of ray P1 -> P2 Subtract P1 from both of the other vectors. Let V2 = P2-P1 and V3 = P3-P1. Now the cross product V2xV3 is the signed area of the parallogram formed by V2 and V3. This area is > 0 if and only if P3 is left of ray P1 -> P2. V3 *--------* / / / / / / *--------*V2 If V2 = ( X'2 , Y'2 ) and V3 = ( X'3 , Y'3 ) Then the cross product is (X'2 Y'3) - (Y'2 X'-3) Alternatively: ( X1 Y1 1 ) Claim: LineSideTest(P1,P2,P3) = det ( X2 Y2 1 ) ( X3 Y3 1 ) ( X1 y1 1 ) LHS = det ( X'2 Y'2 0 ) ( X'3 Y'3 0 ) LHS = det ( X'2 Y'2 ) ( X'3 Y'3 ) -------------------------------------------------------------------