Introduction to Computational Geometry: Convex Hulls Overview
Explore the fundamentals of computational geometry with a focus on convex hulls. Learn about convex and concave sets, the properties and degenerate cases of convex hulls, the convex hull problem, and more. Delve into algorithms like Graham scan and Javis march for computing convex hulls efficiently. Discover the significance of edges in convex hulls and the workings of a slow convex hull algorithm.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Convex Hulls Outline I. Convex sets II. Convex hull properties III. Graham scan IV. Correctness and running time V. Javis march Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.
I. Convex Sets & Concave Sets A planar region ?is called convex if and only if for any pair of points ?, ? in ?, the line segment ?? lies completely in ?. Otherwise, it is called concave. ? ? ?2 ?1 ? ? Concave Convex
An Example 4 1 2 3 Regions 1 & 2: convex Regions 3 & 4: concave
Convex Hull The convex hull CH(?) of a set ? is the smallest convex region that contains ?. Rubber band When ? is finite, its convex hull is the unique convex polygon whose vertices are from ? and that contains all points of ?.
Degenerate Cases The convex hull of a single point is itself. The convex hull of several collinear points is the line segment joining the two extreme points.
II. The Convex Hull Problem Input: a set ? = { ?1 ,?2 , ,?? } of points Output: a list of vertices of CH(?) in counterclockwise order. (direction of traversal about the outward axis with the interior on the left) Example ?5 ?7 ?9 ?6 ?1 ?2 ?4 ?3 ?10 ?8 Output: ?5, ?9, ?2, ?8, ?10, ?7.
Edges of a Convex Hull For every edge with endpoints ?,? ?. All other points in ?lie to the same side of the line passing through ? and ?, or between ? and ? if on the line. q p
A Slow Convex Hull Algorithm Slow-Convex-Hull(?) ? {} // set of directed edges of CH(?) that bounds the // points of P on the right. for every ordered pair (?,?), where ?,? ? and ? ? // (?2) pairs do valid true for every point ? ? or ? // ? 2 such points do if ? lies to the right of ??or collinear with ?and ? but not on ?? then valid false if valid then ? ? { ?? } // ?? and ?? cannot be both in ? From ? construct a list ? of vertices of CH(?), sorted in counterclockwise order. // ?(?2) improvable to ?(? log?) return L ? ? ? ? ? ? Running time (??)
Floating Arithmetic is not Exact! Nearly colinear points ?, ?,?. q r p ? to the left of ??. ? to the left of ??. ? to the left of ??. All three are accepted as edges! Not robust the algorithm could fail with small numerical error.
Polar Angle ? ? polar angle p ? ?
III. Graham Scan 1) Select the node with the smallest ? coordinate. ?0 This node will be a vertex of the convex hull.
Tie Breaking (1) When more than one point has the smallest ? coordinate, pick the leftmost (or rightmost) one. ?0
Sorting by Polar Angle 2) Sort by polar angle with respect to ?0. ?6 ?9 ?4 ?11 ?7 ?3 ?8 ?5 ?10 ?2 ?1 ?0 ?0 Labels are in the polar angle order.
No Polar Angle Evaluation all polar angles 0,? . ?0 is the lowest (and leftmost) ??? ????? ???????! ??< ?? if ?0?? ?0??> 0 ?? ?? ?0
Tie Breaking (2) What if ?0,??,?? are on the same line? Order them by distance from ?0. ??< ?? if and ?0?? ?0??= 0 ?0?? < |?0??| ?? No square roots. Use dot product! ?? ?0 ?0?? ?0??< ?0?? ?0??
Point Elimination When multiple points have the same polar angle, keep the one furthest from ?0. Remove the rest since they cannot possibly be the hull vertices. furtherest ?? ?? remove ?0
Stack Initialization 3) Scan points in the increasing order of polar angle, maintaining a stack. ?6 ?9 ?4 ?11 ?7 ? ?3 ?8 ?2 ?5 ?10 ?1 ?2 ?1 ?0 ?0
?6 ?9 ?4 ?11 ?7 ? ?3 ?8 ?3 ?5 ?10 ?1 ?2 ?1 ?0 ?0
?6 ?9 ?4 ?11 ?7 ? ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
?6 ?9 ? ?4 ?11 ?7 ?5 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
?6 ?9 ? ?4 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
? ?8 ?6 ?9 ?4 ?7 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
? ?6 ?9 ?4 ?7 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
? ?10 ?6 ?9 ?4 ?9 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
? ?11 ?6 ?9 ?4 ?9 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
Finish S ?11 ?6 ?9 ?4 ?9 ?11 ?7 ?6 ?3 ?8 ?4 ?5 ?10 ?1 ?2 ?1 ?0 ?0
Grahams Scan candidates for vertices of CH(?) ?? finish Non-vertices of CH(?) determined so far are popped ?? ?? Every point in ? is pushed onto ? once ?? start ?? ?? ?? ?? ?2 ?1 ?0 ?0 ?0 ?0 ?0 vertices of CH(?) in the counter- clockwise order.
IV. The Graham Scan Algorithm Graham-Scan(?) let ?0 be the point in ? with minimum?-coordinate let ?1,?2, ,?? 1 be the remaining points in ? sorted in counterclockwise order by polar angle around ?0. Top[?] 0 Push(?0, ?) Push(?1, ?) Push(?2 , ?) for ? = 3 to ? 1 do while ?? makes a nonleft turn from the line segment determined by Top(?) and Next-to-Top(?) do Pop(?) Push(?, ??) return ?
Running time #operations time / operation total Finding ?0 1 (?) (?) Sorting 1 ?(? log?)O(? log?) (?) ?(?) Push? Pop ? 2 ?(1) ?(1) Why? The running time of Graham s Scan is?(? log?).
Proof of Correctness Claim 1 Each point popped from stack S is not a vertex of CH(P). Two cases when ?? is popped: Proof ?? ?? ?? ?? ?? ?? ?0 ?0 In neither case can ?? become a vertex of CH(P).
Claim 2 Graham-Scan maintains theinvariant that the points on stack S always form the vertices of a convex polygon in counterclockwise order. The claim holds right after initialization of ? when ?0,?1,?2form a triangle (which is obviously convex). Proof Popping a point from ? preserves the invariant. Consider a point ?? being pushed onto ?. ?? The region containing ?? The invariant still holds. ?? ?0
Correctness of Grahams Scan Theorem If Graham-Scan is run on a set ?of at least three points, then a point of ? is on the stack ? at termination if and only if it is a vertex of CH(?).
V. Jarvis March A package wrapping technique (smallest polar angle w.r.t. ?2) ?3 ?4 ?2(smallest polar angle w.r.t. ?1) (smallest polar angle w.r.t. ?4) Right chain Left chain ?5 ?1 (smallest polar angle w.r.t. ?0) ?6 ?0 (lowest point) (smallest polar angle w.r.t. ?5)
Running Time of Jarviss March Let be the number of vertices of the convex hull. For each vertex, finding the point with the minimum Polar angle, that is, the next vertex, takes time ?(?). Comparison between two polar angles can be done using cross product. Thus ?(??) time in total.
