Understanding Convex Hulls in Computational Geometry
Convex hulls are a fundamental concept in computational geometry, representing the smallest convex shape that contains a set of points. The process involves defining the convexity of a set, determining the unique convex polygon, and computing the convex hull efficiently using algorithms. This content explores the properties and algorithms related to convex hulls, providing insights into their significance and computation methods.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMPS 3130/6130: Computational Geometry Spring 2020 Convex Hulls I Carola Wenk 1/14/20 1 CMPS 3130/6130: Computational Geometry
Convex Hull Problem Given a set of pins on a pinboard and a rubber band around them. How does the rubber band look when it snaps tight? The convex hull of a point set is one of the simplest shape approximations for a set of points. 1/14/20 2 CMPS 3130/6130: Computational Geometry
Convexity A set C R2 is convex if for every two points p,q C the line segment pq is fully contained in C. convex non-convex 1/14/20 3 CMPS 3130/6130: Computational Geometry
Convex Hull The convex hull CH(P) of a point set P R2 is the smallest convex set C P. In other words CH(P) = C . C P C convex P 1/14/20 4 CMPS 3130/6130: Computational Geometry
Convex Hull Observation: CH(P) is the unique convex polygon whose vertices are points of P and which contains all points of P. Goal: Compute CH(P). What does that mean? How do we represent/store CH(P)? Represent the convex hull as the sequence of points on the convex hull polygon (the boundary of the convex hull), in counter-clockwise order. 4 5 3 6 2 1 0 1/14/20 5 CMPS 3130/6130: Computational Geometry
A First Try Algorithm SLOW_CH(P): /* CH(P) = Intersection of all half-planes that are defined by the directed line through ordered pairs of points in P and that have all remaining points of P on their left */ Input: Point set P R2 Output: A list L of vertices describing CH(P) in counter-clockwise order E:= for all (p,q) P P with p q // ordered pair valid := true for all r P, r p and r q if r lies to the right of directed line through p and q // takes constant time valid := false if valid then E:=E pq // directed edge Construct from E sorted list L of vertices of CH(P) in counter-clockwise order Runtime: O(n3) , where n = |P| How to test that a point lies to the right of a directed line? p1 q1 valid p2 q2 invalid 1/14/20 6 CMPS 3130/6130: Computational Geometry
A First Try in d Dimensions Algorithm SLOW_CH(P): /* CH(P) = Intersection of all half-spaces that are defined by an oriented hyperplane through ordered d-tuples of points in P and that have all remaining points of P on their positive side */ Input: Point set P Rd Output: A list L of vertices describing CH(P) in counter-clockwise order E:= for all (p1, , pd) Pd with pi pj for all i j valid := true for all r P, r pi for all i=1, ,n Let H be the (d-1)-dimensional hyperplane through p1, , pd if r lies on the negative side of H // takes O(I) time, using normal vector valid := false if valid then S:=E (p1, , pd) // add simplex (segment, triangle, tetrahedron, ) Construct from S the simplicial complex (higher-dimensional equivalent of a triangulation) to represent CH(P) Runtime: O(nd+1) , where n = |P| 1/14/20 7 CMPS 3130/6130: Computational Geometry
Orientation Test / Halfplane Test p r q q r q r p p zero orientation r lies on the line pq negative orientation (clockwise) positive orientation (counter-clockwise) r lies to the right of pq 1 px py 1 qx qy 1 rx ry r lies to the left of pq Orient(p,q,r) = sign det , where p = (px,py) = sign (qx ry - qyrx ( pxry - pyrx) + pxqy - py qx) Can be computed in constant time 1/14/20 8 CMPS 3130/6130: Computational Geometry
Jarvis March (Gift Wrapping) Algorithm Giftwrapping_CH(P): // Compute CH(P) by incrementally inserting points from left to right Input: Point set P R2 Output: List q1, q2, of vertices in counter-clockwise order around CH(P) q1 = point in P with smallest y (break ties by x-coordinate) q2 = point in P with smallest angle to horizontal line through q1 i = 2 do { i++ qi = point with smallest angle to line through qi-2 and qi-1 } while qi q1 q3 q2 q1 Runtime: O(hn) , where n = |P| and h = #points on CH(P) Output-sensitive algorithm 1/14/20 9 CMPS 3130/6130: Computational Geometry
