当前位置: 首页 > article >正文

Python 使用 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)_threejs计算三个点的朝向-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 以进行下一次迭代)。

以下是上述算法的实现: 

# Python3 program to find convex hull of a set of points. Refer 
# https://www.geeksforgeeks.org/orientation-3-ordered-points/
# 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 

输出:

(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


http://www.kler.cn/a/355094.html

相关文章:

  • 服务器压力测试怎么做
  • 专栏二十三:Python读取和分析空间数据的经验杂谈
  • RGCL:A Review-aware Graph Contrastive Learning Framework for Recommendation
  • 对文件内的文件名生成目录,方便查阅
  • uniapp跨平台开发---webview调用app方法
  • MyBatis通过注解配置执行SQL语句原理源码分析
  • Unknown column ‘oMIbw5H29LXtmAUjSSm7ZrymASUI‘ in ‘where clause‘
  • 前端技巧汇总
  • 驱动总裁免登陆单文件版
  • 网页前端开发之HTML入门篇:标题标签 heading
  • Leetcode 1223 LCA of Deepest TreeNode
  • 带头结点的单链表按数据域从小到大进行选择排序的算法
  • 生成器和迭代器
  • Mysql 5.7 安装与卸载(非常详细)
  • 【原创】java+springboot+mysql智能农村管理系统设计与实现
  • OpenUAV:首个专为现实无人机视觉语言导航设计的大规模轨迹数据集,由大约 12k 个轨迹组成,涵盖了多种环境和复杂的飞行动态。
  • laravel清除不同缓存
  • 疾病防控|基于springBoot的疾病防控综合系统设计与实现(附项目源码+论文+数据库)
  • 海康相机
  • 通信学习干货:运营商为什么要大力推广FTTR?
  • 2. 继承Mono的单例模式基类
  • 一文搞懂模型倍率怎么计算的,以及模型分组倍率原理!
  • Java | Leetcode Java题解之第480题滑动窗口中位数
  • 决策树C4.5算法详解及实现
  • openEuler-22.03-SP4离线编译安装ZLMediaKit
  • A Survey on 3D Gaussian Splatting 整理