Convex hull in 2D
mindthenerd.blogspot.com
www.codeproject.com
cgi.di.uoa.gr
www.youtube.com
Before we start …
• Link to study materials of Geometric
algorithms course
• https://is.muni.cz/auth/do/sci/UMS/el/geome
tricke-alg/index.html
Convex hull
• Set M is convex if a line segment connecting
its two arbitrary points fully lies inside M
• Convex hull of a set of points X in the
Euclidean space corresponds to the smallest
convex set containing X
http://www.surynkova.info/dokumenty/mff/PG/Prednasky/prednaska_8.pdf
Convex hull
• Input: n points on a plane
jcastellssala.wordpress.com
Convex hull
• Convex hull in 2D:
= convex polygon
- Represented by an ordered sequence of vertices
(counter clockwise)
• Convex hull in 3D:
= convex polyhedron
- Represented by a planar graph
Convex hull – algorithms
• Gift Wrapping (Jarvis March)
• Graham Scan
• Incremental algorithm
• Divide and conquer
Gift wrapping (Jarvis March)
• Resembles wrapping gifts, proposed by Jarvis
(1973)
• Simple implementation and extension to 3D
• Assumption: set X does not contain three colinear
points
• Complexity: Preprocessing O(n), algorithm
O(n2)
Gift wrapping (Jarvis March)
• Principle:
– Find pivot q (q = max(yi))
– Add q to the convex hull H
– pj-1 = arbitrary point on x axis, pj = q, pi = pj-1
– Repeat until pi ≠ q:
• Repeat pi ∉ H and points pj-1, pj :
– Find pi for that the angle Θ = min(Θi)
• Add pi to H
• pj-1 = pj, pj = pi
∀
Gift wrapping (Jarvis March)
http://web.natur.cuni.cz/~bayertom/Adk/adk4.pdf
pj-1
pj =
Gift wrapping (Jarvis March)
http://web.natur.cuni.cz/~bayertom/Adk/adk4.pdf
pj-1
pj
Implementation
• We find point P with the highest x-axis value –
this is one of the vertices of the convex hull
• In this point P we determine so called
separating line (often parallel to y axis). All
points in the input set lie in the same halfplane,
determined by
the separating line
Implementation
• From P we shoot rays heading to all other
points of the input set
Implementation
• We select a ray which has the minimal angle
with the first (separating) line. We have next
vertext of the convex hull (2)
Implementation
• New edge of the convex hull is 1-2
Implementation
• Repeat this until we will reach the first point P
again
Implementation