C o m p u t i n g C O N V E X H U L L S.ppt

c o m p u t i n gc o m p u t i n gC O N V E X H U L L SC O N V E X H U L L SbybyKok Lim LowKok Lim Low10 Nov P 290-P 290-072PresentationPresentationPresentation OutlinePresentation Outline?2D Convex Hulls–Definitions and Properties–Approaches:?Brute Force?Gift Wrapping?QuickHull?Graham Scan?Incremental?Divide and Conquer?By Delaunay Triangulation & Voronoi DiagramPresentation OutlinePresentation Outline?3D Convex Hulls–Approaches:?Gift Wrapping?QuickHull?Divide and Conquer?Incremental?Higher Dimensions?Some ApplicationsSome Applications?Collision Avoidance–robot motion planning?Finding Smallest Box–collision detection?Shape Analysis2D CONVEX HULLS2D CONVEX HULLSDefinitions and PropertiesDefinitions and Properties–Intersection of all convex sets containing P–Smallest convex set containing P–Intersection of all half-planes containing P–Union of all triangles formed by points of Prubber bandDefinitions and PropertiesDefinitions and Properties–Smallest convex polygon containing P–All vertices of hull are some points of P–NOTE: convex hull is the closed solid region, not just the boundaryextreme pointnot extreme pointalways uniqueBrute-Force ApproachBrute-Force Approach?Determine extreme edgesfor each pair of points p,q?P doif all other points lie on one side of line passing thru p and q then keep edge (p, q)pqBrute-Force ApproachBrute-Force Approach?Next, sort edges in counterclockwise order–we want output in counterclockwise?Running time: O(n3)–bad but not the worst yetGift WrappingGift Wrappingp? the lowest point p0repeatfor each q?P and q?p pute counterclockwise angle ? from previous hull edgelet r be the point with smallest ?output (p, r) as a hull edgep?runtil p = p0p?