凸包|集2（格雷厄姆扫描）-yiteyi-C++库

给定平面上的一组点。集合的凸包是包含其所有点的最小凸多边形。

null

图片[1]-凸包|集2（格雷厄姆扫描）-yiteyi-C++库

我们强烈建议先看下面的帖子。如何检查两条给定线段是否相交？我们讨论过贾维斯算法对于凸面外壳。Jarvis算法的最坏情况时间复杂度为O（n^2）。利用格雷厄姆扫描算法，我们可以在O（nLogn）时间内找到凸包。下面是格雷厄姆的算法设点[0..n-1]为输入数组。 1) 通过比较所有点的y坐标找到最底部的点。如果有两个点具有相同的y值，则考虑具有较小x坐标值的点。让最低点为P0。将P0置于输出外壳的第一个位置。 2) 考虑其余的N-1点，并以极角为单位在点附近逆时针排序[0 ]。如果两点的极角相同，则先放置最近的点。 3. 排序后，检查两个或多个点是否具有相同的角度。如果两个以上的点具有相同的角度，则移除所有相同的角度点，但距离P0最远的点除外。让新数组的大小为m。 4) 如果m小于3，则返回（不可能出现凸包） 5) 创建一个空堆栈“S”，并将点[0]、点[1]和点[2]推送到S。 6) 逐个处理剩余的m-3点。对每一个“点[i]”进行以下操作 4.1) 继续从堆栈中移除点，同时方向以下三个点中有一个不是逆时针方向的（或者它们不左转）。 a）堆栈中靠近顶部的点 b）指向堆栈顶部 c）要点[i] 4.2) 推送点[i]到S 5) 打印文件的内容上述算法可分为两个阶段。 第一阶段（分拣点）： 我们首先找到最底层的点。这样做的目的是对点进行预处理，根据最底层的点对点进行排序。一旦这些点被排序，它们就会形成一条简单的闭合路径（见下图）。

图片[2]-凸包|集2（格雷厄姆扫描）-yiteyi-C++库

排序标准应该是什么？由于三角函数不容易计算，实际角度的计算效率很低。其思想是使用方向来比较角度，而不实际计算角度（参见下面的compare（）函数） 第2阶段（接受或拒绝分数）： 一旦我们有了闭合的路径，下一步就是遍历该路径并移除该路径上的凹点。如何决定删除和保留哪一点？再一次方向这里有帮助。排序数组中的前两点始终是凸包的一部分。对于剩余的点，我们跟踪最近的三个点，并找到它们形成的角度。让这三个点分别为上一个（p）、当前（c）和下一个（n）。如果这些点的方向（以相同的顺序考虑）不是逆时针的，我们丢弃c，否则我们保留它。下图显示了该阶段的逐步过程。

图片[3]-凸包|集2（格雷厄姆扫描）-yiteyi-C++库

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

下面是C++实现上述算法。

CPP

                         // A C++ program to find convex hull of a set of points. Refer                       
                         //                           https://www.geeksforgeeks.org/orientation-3-ordered-points/                                    
                         // for explanation of orientation()                       
                         #include <iostream>                       
                         #include <stack>                       
                         #include <stdlib.h>                       
                         using                                     namespace                                     std;                       
           
                         struct                                     Point                       
                         {                       
                                                 int                                     x, y;                       
                         };                       
           
                         // A global point needed for  sorting points with reference                       
                         // to  the first point Used in compare function of qsort()                       
                         Point p0;                       
           
                         // A utility function to find next to top in a stack                       
                         Point nextToTop(stack<Point> &S)                       
                         {                       
                                                 Point p = S.top();                       
                                                 S.pop();                       
                                                 Point res = S.top();                       
                                                 S.push(p);                       
                                                 return                                     res;                       
                         }                       
           
                         // A utility function to swap two points                       
                         void                                     swap(Point &p1, Point &p2)                       
                         {                       
                                                 Point temp = p1;                       
                                                 p1 = p2;                       
                                                 p2 = temp;                       
                         }                       
           
                         // A utility function to return square of distance                       
                         // between p1 and p2                       
                         int                                     distSq(Point p1, Point p2)                       
                         {                       
                                                 return                                     (p1.x - p2.x)*(p1.x - p2.x) +                       
                                                 (p1.y - p2.y)*(p1.y - p2.y);                       
                         }                       
           
                         // To find orientation of ordered triplet (p, q, r).                       
                         // The function returns following values                       
                         // 0 --> p, q and r are collinear                       
                         // 1 --> Clockwise                       
                         // 2 --> Counterclockwise                       
                         int                                     orientation(Point p, Point q, Point r)                       
                         {                       
                                                 int                                     val = (q.y - p.y) * (r.x - q.x) -                       
                                                 (q.x - p.x) * (r.y - q.y);                       
           
                                                 if                                     (val == 0)                                     return                                     0;                                     // collinear                       
                                                 return                                     (val > 0)? 1: 2;                                     // clock or counterclock wise                       
                         }                       
           
                         // A function used by library function qsort() to sort an array of                       
                         // points with respect to the first point                       
                         int                                     compare(                                     const                                     void                                     *vp1,                                     const                                     void                                     *vp2)                       
                         {                       
                                                 Point *p1 = (Point *)vp1;                       
                                                 Point *p2 = (Point *)vp2;                       
           
                                                 // Find orientation                       
                                                 int                                     o = orientation(p0, *p1, *p2);                       
                                                 if                                     (o == 0)                       
                                                 return                                     (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;                       
           
                                                 return                                     (o == 2)? -1: 1;                       
                         }                       
           
                         // Prints convex hull of a set of n points.                       
                         void                                     convexHull(Point points[],                                     int                                     n)                       
                         {                       
                                                 // Find the bottommost point                       
                                                 int                                     ymin = points[0].y, min = 0;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 int                                     y = points[i].y;                       
           
                                                 // Pick the bottom-most or chose the left                       
                                                 // most point in case of tie                       
                                                 if                                     ((y < ymin) || (ymin == y &&                       
                                                 points[i].x < points[min].x))                       
                                                 ymin = points[i].y, min = i;                       
                                                 }                       
           
                                                 // Place the bottom-most point at first position                       
                                                 swap(points[0], points[min]);                       
           
                                                 // Sort n-1 points with respect to the first point.                       
                                                 // A point p1 comes before p2 in sorted output if p2                       
                                                 // has larger polar angle (in counterclockwise                       
                                                 // direction) than p1                       
                                                 p0 = points[0];                       
                                                 qsort                                     (&points[1], n-1,                                     sizeof                                     (Point), compare);                       
           
                                                 // If two or more points make same angle with p0,                       
                                                 // Remove all but the one that is farthest from p0                       
                                                 // Remember that, in above sorting, our criteria was                       
                                                 // to keep the farthest point at the end when more than                       
                                                 // one points have same angle.                       
                                                 int                                     m = 1;                                     // Initialize size of modified array                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 {                       
                                                 // Keep removing i while angle of i and i+1 is same                       
                                                 // with respect to p0                       
                                                 while                                     (i < n-1 && orientation(p0, points[i],                       
                                                 points[i+1]) == 0)                       
                                                 i++;                       
           
           
                                                 points[m] = points[i];                       
                                                 m++;                                     // Update size of modified array                       
                                                 }                       
           
                                                 // If modified array of points has less than 3 points,                       
                                                 // convex hull is not possible                       
                                                 if                                     (m < 3)                                     return                                     ;                       
           
                                                 // Create an empty stack and push first three points                       
                                                 // to it.                       
                                                 stack<Point> S;                       
                                                 S.push(points[0]);                       
                                                 S.push(points[1]);                       
                                                 S.push(points[2]);                       
           
                                                 // Process remaining n-3 points                       
                                                 for                                     (                                     int                                     i = 3; i < m; i++)                       
                                                 {                       
                                                 // Keep removing top while the angle formed by                       
                                                 // points next-to-top, top, and points[i] makes                       
                                                 // a non-left turn                       
                                                 while                                     (S.size()>1 && orientation(nextToTop(S), S.top(), points[i]) != 2)                       
                                                 S.pop();                       
                                                 S.push(points[i]);                       
                                                 }                       
           
                                                 // Now stack has the output points, print contents of stack                       
                                                 while                                     (!S.empty())                       
                                                 {                       
                                                 Point p = S.top();                       
                                                 cout <<                                     "("                                     << p.x <<                                     ", "                                     << p.y <<                                     ")"                                     << endl;                       
                                                 S.pop();                       
                                                 }                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},                       
                                                 {0, 0}, {1, 2}, {3, 1}, {3, 3}};                       
                                                 int                                     n =                                     sizeof                                     (points)/                                     sizeof                                     (points[0]);                       
                                                 convexHull(points, n);                       
                                                 return                                     0;                       
                         }                       

Python3

                         # A Python3 program to find convex hull of a set of points. Refer                       
                         #                           https://www.geeksforgeeks.org/orientation-3-ordered-points/                                    
                         # for explanation of orientation()                       
           
                         from                                     functools                                     import                                     cmp_to_key                       
           
                         # A class used to store the x and y coordinates of points                       
                         class                                     Point:                       
                                                 def                                     __init__(                                     self                                     , x                                     =                                     None                                     , y                                     =                                     None                                     ):                       
                                                 self                                     .x                                     =                                     x                       
                                                 self                                     .y                                     =                                     y                       
           
                         # A global point needed for sorting points with reference                       
                         # to the first point                       
                         p0                                     =                                     Point(                                     0                                     ,                                     0                                     )                       
           
                         # A utility function to find next to top in a stack                       
                         def                                     nextToTop(S):                       
                                                 return                                     S[                                     -                                     2                                     ]                       
           
                         # A utility function to return square of distance                       
                         # between p1 and p2                       
                         def                                     distSq(p1, p2):                       
                                                 return                                     ((p1.x                                     -                                     p2.x)                                     *                                     (p1.x                                     -                                     p2.x)                                     +                       
                                                 (p1.y                                     -                                     p2.y)                                     *                                     (p1.y                                     -                                     p2.y))                       
           
                         # To find orientation of ordered triplet (p, q, r).                       
                         # The function returns following values                       
                         # 0 --> p, q and r are collinear                       
                         # 1 --> Clockwise                       
                         # 2 --> Counterclockwise                       
                         def                                     orientation(p, q, r):                       
                                                 val                                     =                                     ((q.y                                     -                                     p.y)                                     *                                     (r.x                                     -                                     q.x)                                     -                       
                                                 (q.x                                     -                                     p.x)                                     *                                     (r.y                                     -                                     q.y))                       
                                                 if                                     val                                     =                                     =                                     0                                     :                       
                                                 return                                     0                                     # collinear                       
                                                 elif                                     val >                                     0                                     :                       
                                                 return                                     1                                     # clock wise                       
                                                 else                                     :                       
                                                 return                                     2                                     # counterclock wise                       
           
                         # A function used by cmp_to_key function to sort an array of                       
                         # points with respect to the first point                       
                         def                                     compare(p1, p2):                       
                                   
                                                 # Find orientation                       
                                                 o                                     =                                     orientation(p0, p1, p2)                       
                                                 if                                     o                                     =                                     =                                     0                                     :                       
                                                 if                                     distSq(p0, p2) >                                     =                                     distSq(p0, p1):                       
                                                 return                                     -                                     1                       
                                                 else                                     :                       
                                                 return                                     1                       
                                                 else                                     :                       
                                                 if                                     o                                     =                                     =                                     2                                     :                       
                                                 return                                     -                                     1                       
                                                 else                                     :                       
                                                 return                                     1                       
           
                         # Prints convex hull of a set of n points.                       
                         def                                     convexHull(points, n):                       
                                   
                                                 # Find the bottommost point                       
                                                 ymin                                     =                                     points[                                     0                                     ].y                       
                                                 min                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                                 y                                     =                                     points[i].y                       
           
                                                 # Pick the bottom-most or chose the left                       
                                                 # most point in case of tie                       
                                                 if                                     ((y < ymin)                                     or                       
                                                 (ymin                                     =                                     =                                     y                                     and                                     points[i].x < points[                                     min                                     ].x)):                       
                                                 ymin                                     =                                     points[i].y                       
                                                 min                                     =                                     i                       
           
                                                 # Place the bottom-most point at first position                       
                                                 points[                                     0                                     ], points[                                     min                                     ]                                     =                                     points[                                     min                                     ], points[                                     0                                     ]                       
           
                                                 # Sort n-1 points with respect to the first point.                       
                                                 # A point p1 comes before p2 in sorted output if p2                       
                                                 # has larger polar angle (in counterclockwise                       
                                                 # direction) than p1                       
                                                 p0                                     =                                     points[                                     0                                     ]                       
                                                 points                                     =                                     sorted                                     (points, key                                     =                                     cmp_to_key(compare))                       
           
                                                 # If two or more points make same angle with p0,                       
                                                 # Remove all but the one that is farthest from p0                       
                                                 # Remember that, in above sorting, our criteria was                       
                                                 # to keep the farthest point at the end when more than                       
                                                 # one points have same angle.                       
                                                 m                                     =                                     1                                     # Initialize size of modified array                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                   
                                                 # Keep removing i while angle of i and i+1 is same                       
                                                 # with respect to p0                       
                                                 while                                     ((i < n                                     -                                     1                                     )                                     and                       
                                                 (orientation(p0, points[i], points[i                                     +                                     1                                     ])                                     =                                     =                                     0                                     )):                       
                                                 i                                     +                                     =                                     1                       
           
                                                 points[m]                                     =                                     points[i]                       
                                                 m                                     +                                     =                                     1                                     # Update size of modified array                       
           
                                                 # If modified array of points has less than 3 points,                       
                                                 # convex hull is not possible                       
                                                 if                                     m <                                     3                                     :                       
                                                 return                       
           
                                                 # Create an empty stack and push first three points                       
                                                 # to it.                       
                                                 S                                     =                                     []                       
                                                 S.append(points[                                     0                                     ])                       
                                                 S.append(points[                                     1                                     ])                       
                                                 S.append(points[                                     2                                     ])                       
           
                                                 # Process remaining n-3 points                       
                                                 for                                     i                                     in                                     range                                     (                                     3                                     , m):                       
                                   
                                                 # Keep removing top while the angle formed by                       
                                                 # points next-to-top, top, and points[i] makes                       
                                                 # a non-left turn                       
                                                 while                                     ((                                     len                                     (S) >                                     1                                     )                                     and                       
                                                 (orientation(nextToTop(S), S[                                     -                                     1                                     ], points[i]) !                                     =                                     2                                     )):                       
                                                 S.pop()                       
                                                 S.append(points[i])                       
           
                                                 # Now stack has the output points,                       
                                                 # print contents of stack                       
                                                 while                                     S:                       
                                                 p                                     =                                     S[                                     -                                     1                                     ]                       
                                                 print                                     (                                     "("                                     +                                     str                                     (p.x)                                     +                                     ", "                                     +                                     str                                     (p.y)                                     +                                     ")"                                     )                       
                                                 S.pop()                       
           
                         # Driver Code                       
                         input_points                                     =                                     [(                                     0                                     ,                                     3                                     ), (                                     1                                     ,                                     1                                     ), (                                     2                                     ,                                     2                                     ), (                                     4                                     ,                                     4                                     ),                       
                                                 (                                     0                                     ,                                     0                                     ), (                                     1                                     ,                                     2                                     ), (                                     3                                     ,                                     1                                     ), (                                     3                                     ,                                     3                                     )]                       
                         points                                     =                                     []                       
                         for                                     point                                     in                                     input_points:                       
                                                 points.append(Point(point[                                     0                                     ], point[                                     1                                     ]))                       
                         n                                     =                                     len                                     (points)                       
                         convexHull(points, n)                       
           
                         # This code is contributed by Kevin Joshi                       

输出：

(0, 3)(4, 4)(3, 1)(0, 0)

时间复杂性： 设n为输入点数。如果使用O（nLogn）排序算法，该算法需要O（nLogn）时间。第一步（找到最低点）需要O（n）个时间。第二步（排序点）需要O（nLogn）时间。第三步需要O（n）时间。在第三步中，每个元素最多一次被推和弹出。因此，假设堆栈操作需要O（1）个时间，那么逐个处理点的第六步需要O（n）个时间。总体复杂度为O（n）+O（nLogn）+O（n）+O（n），即O（nLogn）。

参考资料： 算法导论第三版由Clifford Stein、Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest编写 http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1。pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章