给定平面上的一组点。集合的凸包是包含其所有点的最小凸多边形。
null
![图片[1]-凸壳|集1（贾维斯算法或换行）-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/ConvexHull.png)
我们强烈建议先看下面的帖子。 如何检查两条给定线段是否相交？ Jarvis算法的思想很简单，我们从最左边的点（或x坐标值最小的点）开始，并保持按逆时针方向包装点。最大的问题是，给定一个点p作为当前点，如何在输出中找到下一个点？这个想法是使用 方向（） 在这里选择下一个点作为逆时针方向超过所有其他点的点，即，如果对于任何其他点r，我们有“方向（p，q，r）=逆时针方向”，则下一个点为q。下面是详细的算法。 1) 将p初始化为最左边的点。 2) 在我们不回到第一点（或最左边）的时候，跟着做。 ….. （a） 下一个点q是这样的点，三元组（p，q，r）对于任何其他点r都是逆时针的。要找到这个，我们只需将q初始化为下一个点，然后遍历所有点。对于任何点i，如果i更逆时针，即方向（p，i，q）是逆时针的，那么我们将q更新为i。q的最终值将是最逆时针的点。 ….. b） next[p]=q（将q存储为输出凸包中p的next）。 ….. c） p=q（为下一次迭代设置p为q）。
![图片[2]-凸壳|集1（贾维斯算法或换行）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20210324/geeks_Jarvis-March_1_60.jpg)
下面是上述算法的实现。
C++
// A C++ program to find convex hull of a set of points. Refer // for explanation of orientation() #include <bits/stdc++.h> using namespace std; struct Point { int x, 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 } // Prints convex hull of a set of n points. void convexHull(Point points[], int n) { // There must be at least 3 points if (n < 3) return ; // Initialize Result vector<Point> hull; // Find the leftmost point int l = 0; for ( int i = 1; i < n; i++) if (points[i].x < points[l].x) l = i; // Start from leftmost point, keep moving counterclockwise // until reach the start point again. This loop runs O(h) // times where h is number of points in result or output. int p = l, q; do { // Add current point to result hull.push_back(points[p]); // Search for a point 'q' such that orientation(p, q, // x) is counterclockwise for all points 'x'. The idea // is to keep track of last visited most counterclock- // wise point in q. If any point 'i' is more counterclock- // wise than q, then update q. q = (p+1)%n; for ( int i = 0; i < n; i++) { // If i is more counterclockwise than current q, then // update q if (orientation(points[p], points[i], points[q]) == 2) q = i; } // Now q is the most counterclockwise with respect to p // Set p as q for next iteration, so that q is added to // result 'hull' p = q; } while (p != l); // While we don't come to first point // Print Result for ( int i = 0; i < hull.size(); i++) cout << "(" << hull[i].x << ", " << hull[i].y << ")" ; } // Driver program to test above functions int main() { Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}}; int n = sizeof (points)/ sizeof (points[0]); convexHull(points, n); return 0; } |
JAVA
// Java program to find convex hull of a set of points. Refer // for explanation of orientation() import java.util.*; class Point { int x, y; Point( int x, int y){ this .x=x; this .y=y; } } class GFG { // 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 public static 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 } // Prints convex hull of a set of n points. public static void convexHull(Point points[], int n) { // There must be at least 3 points if (n < 3 ) return ; // Initialize Result Vector<Point> hull = new Vector<Point>(); // Find the leftmost point int l = 0 ; for ( int i = 1 ; i < n; i++) if (points[i].x < points[l].x) l = i; // Start from leftmost point, keep moving // counterclockwise until reach the start point // again. This loop runs O(h) times where h is // number of points in result or output. int p = l, q; do { // Add current point to result hull.add(points[p]); // Search for a point 'q' such that // orientation(p, q, x) is counterclockwise // for all points 'x'. The idea is to keep // track of last visited most counterclock- // wise point in q. If any point 'i' is more // counterclock-wise than q, then update q. q = (p + 1 ) % n; for ( int i = 0 ; i < n; i++) { // If i is more counterclockwise than // current q, then update q if (orientation(points[p], points[i], points[q]) == 2 ) q = i; } // Now q is the most counterclockwise with // respect to p. Set p as q for next iteration, // so that q is added to result 'hull' p = q; } while (p != l); // While we don't come to first // point // Print Result for (Point temp : hull) System.out.println( "(" + temp.x + ", " + temp.y + ")" ); } /* Driver program to test above function */ public static void main(String[] args) { Point points[] = new Point[ 7 ]; points[ 0 ]= new Point( 0 , 3 ); points[ 1 ]= new Point( 2 , 3 ); points[ 2 ]= new Point( 1 , 1 ); points[ 3 ]= new Point( 2 , 1 ); points[ 4 ]= new Point( 3 , 0 ); points[ 5 ]= new Point( 0 , 0 ); points[ 6 ]= new Point( 3 , 3 ); int n = points.length; convexHull(points, n); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find convex hull of a set of points. Refer # for explanation of orientation() # point class with x, y as point class Point: def __init__( self , x, y): self .x = x self .y = y def Left_index(points): ''' Finding the left most point ''' minn = 0 for i in range ( 1 , len (points)): if points[i].x < points[minn].x: minn = i elif points[i].x = = points[minn].x: if points[i].y > points[minn].y: minn = i return minn def orientation(p, q, r): ''' 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 ''' val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) if val = = 0 : return 0 elif val > 0 : return 1 else : return 2 def convexHull(points, n): # There must be at least 3 points if n < 3 : return # Find the leftmost point l = Left_index(points) hull = [] ''' Start from leftmost point, keep moving counterclockwise until reach the start point again. This loop runs O(h) times where h is number of points in result or output. ''' p = l q = 0 while ( True ): # Add current point to result hull.append(p) ''' Search for a point 'q' such that orientation(p, q, x) is counterclockwise for all points 'x'. The idea is to keep track of last visited most counterclock- wise point in q. If any point 'i' is more counterclock- wise than q, then update q. ''' q = (p + 1 ) % n for i in range (n): # If i is more counterclockwise # than current q, then update q if (orientation(points[p], points[i], points[q]) = = 2 ): q = i ''' Now q is the most counterclockwise with respect to p Set p as q for next iteration, so that q is added to result 'hull' ''' p = q # While we don't come to first point if (p = = l): break # Print Result for each in hull: print (points[each].x, points[each].y) # Driver Code points = [] points.append(Point( 0 , 3 )) points.append(Point( 2 , 2 )) points.append(Point( 1 , 1 )) points.append(Point( 2 , 1 )) points.append(Point( 3 , 0 )) points.append(Point( 0 , 0 )) points.append(Point( 3 , 3 )) convexHull(points, len (points)) # This code is contributed by # Akarsh Somani, IIIT Kalyani |
C#
// C# program to find convex hull of a set of points. Refer // for explanation of orientation() using System; using System.Collections.Generic; public class Point { public int x, y; public Point( int x, int y) { this .x = x; this .y = y; } } public class GFG { // 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 public static 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 } // Prints convex hull of a set of n points. public static void convexHull(Point []points, int n) { // There must be at least 3 points if (n < 3) return ; // Initialize Result List<Point> hull = new List<Point>(); // Find the leftmost point int l = 0; for ( int i = 1; i < n; i++) if (points[i].x < points[l].x) l = i; // Start from leftmost point, keep moving // counterclockwise until reach the start point // again. This loop runs O(h) times where h is // number of points in result or output. int p = l, q; do { // Add current point to result hull.Add(points[p]); // Search for a point 'q' such that // orientation(p, q, x) is counterclockwise // for all points 'x'. The idea is to keep // track of last visited most counterclock- // wise point in q. If any point 'i' is more // counterclock-wise than q, then update q. q = (p + 1) % n; for ( int i = 0; i < n; i++) { // If i is more counterclockwise than // current q, then update q if (orientation(points[p], points[i], points[q]) == 2) q = i; } // Now q is the most counterclockwise with // respect to p. Set p as q for next iteration, // so that q is added to result 'hull' p = q; } while (p != l); // While we don't come to first // point // Print Result foreach (Point temp in hull) Console.WriteLine( "(" + temp.x + ", " + temp.y + ")" ); } /* Driver code */ public static void Main(String[] args) { Point []points = new Point[7]; points[0]= new Point(0, 3); points[1]= new Point(2, 3); points[2]= new Point(1, 1); points[3]= new Point(2, 1); points[4]= new Point(3, 0); points[5]= new Point(0, 0); points[6]= new Point(3, 3); int n = points.Length; convexHull(points, n); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to find convex hull of a set of points. Refer // for explanation of orientation() class Point { constructor(x, y) { this .x = x; this .y = 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 function orientation(p, q, r) { let 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 } // Prints convex hull of a set of n points. function convexHull(points, n) { // There must be at least 3 points if (n < 3) return ; // Initialize Result let hull = []; // Find the leftmost point let l = 0; for (let i = 1; i < n; i++) if (points[i].x < points[l].x) l = i; // Start from leftmost point, keep moving // counterclockwise until reach the start point // again. This loop runs O(h) times where h is // number of points in result or output. let p = l, q; do { // Add current point to result hull.push(points[p]); // Search for a point 'q' such that // orientation(p, q, x) is counterclockwise // for all points 'x'. The idea is to keep // track of last visited most counterclock- // wise point in q. If any point 'i' is more // counterclock-wise than q, then update q. q = (p + 1) % n; for (let i = 0; i < n; i++) { // If i is more counterclockwise than // current q, then update q if (orientation(points[p], points[i], points[q]) == 2) q = i; } // Now q is the most counterclockwise with // respect to p. Set p as q for next iteration, // so that q is added to result 'hull' p = q; } while (p != l); // While we don't come to first // point // Print Result for (let temp of hull.values()) document.write( "(" + temp.x + ", " + temp.y + ")<br>" ); } /* Driver program to test above function */ let points = new Array(7); points[0] = new Point(0, 3); points[1] = new Point(2, 3); points[2] = new Point(1, 1); points[3] = new Point(2, 1); points[4] = new Point(3, 0); points[5] = new Point(0, 0); points[6] = new Point(3, 3); let n = points.length; convexHull(points, n); // This code is contributed by avanitrachhadiya2155 </script> |
输出： 输出是凸包的点。
(0, 3)(0, 0)(3, 0)(3, 3)
笔记 ：当凸壳中存在共线点时，上述代码可能会对不同顺序的输入产生不同的结果。例如，它为输入（0,3）、（0,0）、（0,0）、（0,1）、（3,0）、（3,3）生成（0,3）（0,0）（3,0）（3,3）输出为（0,3）（0,1）（0,0）（3,0）（3,3），为输入（0,3）、（0,1）、（0,0）、（3,0）、（3,3）生成（0,3）输出为（0,3）（0,1）（0,0），为（0,3），为输入为（0,3），（0,3），（0,0,0），（3），通常在共线的情况下，我们需要最远的下一个if条件，在共线的情况下，我们可以通过增加一个if条件来获得。请参考 这 修改代码。 时间复杂性： 对于船体上的每个点，我们检查所有其他点以确定下一个点。时间复杂性是什么？（m*n），其中n是输入点的数量，m是输出点或外壳点的数量（m<=n）。在最坏的情况下，时间复杂度为O（n） 2. ).最坏的情况发生在所有点都位于船体上时（m=n） 集合2-凸面外壳（格雷厄姆扫描） 资料来源： http://www.cs.uiuc.edu/~jeffe/teaching/373/notes/x05 convxhull。pdf http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1。pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
