欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > IT业 > c++ 使用 Jarvis 算法或包装的凸包(Convex Hull using Jarvis’ Algorithm or Wrapping)

c++ 使用 Jarvis 算法或包装的凸包(Convex Hull using Jarvis’ Algorithm or Wrapping)

2024/11/30 10:51:18 来源:https://blog.csdn.net/hefeng_aspnet/article/details/141716082  浏览:    关键词:c++ 使用 Jarvis 算法或包装的凸包(Convex Hull using Jarvis’ Algorithm or Wrapping)

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

我们强烈建议您先阅读以下文章。 
如何检查两个给定的线段是否相交?

c++ https://blog.csdn.net/hefeng_aspnet/article/details/141713655
java https://blog.csdn.net/hefeng_aspnet/article/details/141713762
python https://blog.csdn.net/hefeng_aspnet/article/details/141714389
C# https://blog.csdn.net/hefeng_aspnet/article/details/141714420
javascript https://blog.csdn.net/hefeng_aspnet/article/details/141714442


贾维斯算法的思想很简单,我们从最左边的点(或 x 坐标值最小的点)开始,然后继续沿逆时针方向包裹点。 

最大的问题是,给定一个点 p 作为当前点,如何在输出中找到下一个点? 

这里的想法是使用orientation()。

 //c++ C++ 3 个有序点的方向(Orientation of 3 ordered points)-CSDN博客
//java Java 3 个有序点的方向(Orientation of 3 ordered points)-CSDN博客
//python Python 3 个有序点的方向(Orientation of 3 ordered points)_gh python 判断三点是否顺时针方向 如果是则反序-CSDN博客
//C# C# 3 个有序点的方向(Orientation of 3 ordered points)-CSDN博客
//Javascript javascript 3 个有序点的方向(Orientation of 3 ordered points)-CSDN博客 

下一个点被选为在逆时针方向上领先于所有其他点的点,即,如果对于任何其他点 r,我们有“orientation(p, q, r) = 逆时针”,则下一个点是 q。 

 算法:
步骤 1)将 p 初始化为最左边的点。 
步骤 2)继续进行,直到不再回到第一个(或最左边的)点。2.1 
            )下一个点 q 是这样的点,即对于任何其他点 r,三元组 (p, q, r) 都是逆时针的。 

                    为了找到这一点,我们只需将 q 初始化为下一个点,然后遍历所有点。 

                    对于任意点 i,如果 i 更偏向逆时针,即 orientation(p, i, q) 是逆时针的,则我们将 q 更新为 i。 

                    我们的 q 的最终值将是最逆时针的点。2.2 
           ) next[p] = q(将 q 作为 p 的下一个存储在输出凸包中)。2.3 
           ) p = q(将 p 设置为 q 以进行下一次迭代)。

以下是上述算法的实现: 

// 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 <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 << ")\n";
}
 
// 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;
}

输出:

(0,3)
(0,0)
(3,0)
(3,3)

时间复杂度:O(m * n),其中 n 是输入点数,m 是输出点数或船体点数 (m <= n)。对于船体上的每个点,我们都会检查所有其他点以确定下一个点。  

最坏情况,时间复杂度:O(n 2 )。最坏情况发生在所有点都在船体上(m = n)。

辅助空间:O(n),因为已占用 n 个额外空间

集合 2-凸包(Graham 扫描) 

注意:当凸包中存在共线点时,上述代码可能会对不同顺序的输入产生不同的结果。例如,当输入 (0, 3), (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)。如果是共线,我们通常需要最远的下一个点,如果是共线点,我们可以通过添加一个 if 条件来获得所需的结果。请参考此修改后的代码。

资料来源:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com