c++ 使用 Graham 扫描的凸包（Convex Hull using Graham Scan）

先决条件：

如何检查两个给定的线段是否相交？

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 

贾维斯算法

 c++ https://blog.csdn.net/hefeng_aspnet/article/details/141716082
java https://blog.csdn.net/hefeng_aspnet/article/details/141716363
python https://blog.csdn.net/hefeng_aspnet/article/details/141716444
C# https://blog.csdn.net/hefeng_aspnet/article/details/141716403
Javascript https://blog.csdn.net/hefeng_aspnet/article/details/141716421 

        凸包是包含给定点集的最小凸多边形。它是计算几何学中一个有用的概念，在计算机图形学、图像处理和碰撞检测等各个领域都有应用。

凸多边形是所有内角都小于180度的多边形。可以为任意点集构造凸包，无论这些点如何排列。

格雷厄姆扫描算法：
        格雷厄姆扫描算法是一种简单而有效的算法，用于计算一组点的凸包。它的工作原理是迭代地将点添加到凸包中，直到所有点都添加完毕。

        该算法首先找到 y 坐标最小的点。该点始终位于凸包上。然后，该算法根据剩余点相对于起点的极角对它们进行排序。

        然后，算法会迭代地将点添加到凸包中。在每个步骤中，算法都会检查添加到凸包中的最后两个点是否形成右转。如果是，则将最后一个点从凸包中移除。否则，将排序列表中的下一个点添加到凸包中。

当所有点都被添加到凸包时，算法终止。

Graham Scan的实现：

第一阶段（排序点）：
        实现格雷厄姆扫描算法的第一步是按照点相对于起点的极角对点进行排序。
        一旦点排序完毕，起点就会添加到凸包中。一旦点排序完毕，它们就会形成一条简单的闭合路径（见下图）。 

第二阶段（接受或拒绝点）：

    一旦我们有了闭合路径，下一步就是遍历该路径并移除该路径上的凹点。如何决定移除哪个点以及保留哪个点？同样，方向在这里有帮助。排序数组中的前两个点始终是凸包的一部分。对于剩余的点，我们跟踪最近的三个点，并找到它们形成的角度。让这三个点分别为prev(p)、curr(c)和next(n)。如果这些点的方向（按相同顺序考虑它们）不是逆时针的，我们丢弃 c，否则我们保留它。下图显示了此阶段的分步过程。
 

下面是上述算法的实现： 

// A C++ program to find convex hull of a set of points. Refer
//c++ https://blog.csdn.net/hefeng_aspnet/article/details/141713859
//java https://blog.csdn.net/hefeng_aspnet/article/details/141717851
//python https://blog.csdn.net/hefeng_aspnet/article/details/141717981
//C# https://blog.csdn.net/hefeng_aspnet/article/details/141718039
//Javascript https://blog.csdn.net/hefeng_aspnet/article/details/141718097
// 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 choose 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;
}

输出： 

（0，3）
（4，4）
（3，1）
（0，0）

时间复杂度： O(nLogn)，其中 n 为输入点的数量。

    第一步（找到最底部的点）需要 O(n) 时间。第二步（对点进行排序）需要 O(nLogn) 时间。第三步需要 O(n) 时间。在第三步中，每个元素最多被推送和弹出一次。因此，第六步逐个处理点需要 O(n) 时间，假设堆栈操作需要 O(1) 时间。总体复杂度为 O(n) + O(nLogn) + O(n) + O(n)，即 O(nLogn)。

辅助空间： O（n），因为使用了显式堆栈，所以没有占用额外的空间。

凸包的应用：

    凸包的应用范围很广，包括：

    碰撞检测：凸包可用于快速确定两个物体是否发生碰撞。这在计算机图形学和物理模拟中很有用。

    图像处理：凸包可用于分割图像中的对象。这对于诸如对象识别和跟踪之类的任务很有用。

    计算几何：凸包用于各种计算几何算法，例如查找最近的点对和计算一组点的直径。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1546765.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

PG duckdb插件 pg_quack部署与使用

PG duckdb插件 pg_quack部署与使用

一.pg_quack简介 pg_quack 是一个创新的 PostgreSQL扩展&#xff0c;它将 DuckDB-—一个嵌入式列式数据库 管理系统集成到PostgreSQL中。这个开源项目为开发者提供了一种在同一个数据 库环境中利用高性能数据处理和存储的新方式,使得在PostgreSQL在OLAP的性能 上得到了很大的提…
阅读更多...
Spring Boot 进阶-第一个程序HelloWorld

Spring Boot 进阶-第一个程序HelloWorld

从我们学习编程语言开始，每次入门一个语言都是从Hello World开始，当然这里我们也不例外。首先从一个简单的HelloWorld程序开始。 既然是要学着做Java Web开发，那么首先需要了解的就是如何去编写一个RESTFul风格的接口，这里我们就需要引入一个pom的依赖。 <dependency&g…
阅读更多...
Django设计批量导入Excel数据接口(包含图片)

Django设计批量导入Excel数据接口(包含图片)

Django设计批量导入Excel数据接口(包含图片) 目录 Django设计批量导入Excel数据接口(包含图片)示例xlsx文件接口详情前端上传FormData后端APIView调用函数 Django 4.2.7 openpyxl 3.1.5示例xlsx文件 接口详情 前端上传FormData …
阅读更多...
自动驾驶规划算法（一）：A*算法原理和代码（c++与python）

自动驾驶规划算法（一）：A*算法原理和代码（c++与python）

1. A*算法简介 A*算法&#xff08;A-star algorithm&#xff09;诞生于1968年&#xff0c;由彼得哈特&#xff08;Peter Hart&#xff09;、尼尔森尼尔森&#xff08;Nils Nilsson&#xff09;和伯特拉波特&#xff08;Bertram Raphael&#xff09;三位计算机科学家提出。它的…
阅读更多...
基于大数据可视化的图书推荐及数据分析系统

基于大数据可视化的图书推荐及数据分析系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码 精品专栏&#xff1a;Java精选实战项目…
阅读更多...
快速订餐：Spring Boot 点餐系统

快速订餐：Spring Boot 点餐系统

第二章关键技术的研究 2.1相关技术 网上点餐系统是在Java MySQL开发环境的基础上开发的。Java是一种服务器端脚本语言&#xff0c;易于学习&#xff0c;实用且面向用户。全球超过35&#xff05;的Java驱动的互联网站点使用Java。MySQL是一个数据库管理系统&#xff0c;因为它的…
阅读更多...
WanFangAi论文写作研究生论文写作神器在线生成真实数据，标注参考文献位置，表格公式代码流程图查重20以内，研究生论文开题报告写作技巧

WanFangAi论文写作研究生论文写作神器在线生成真实数据，标注参考文献位置，表格公式代码流程图查重20以内，研究生论文开题报告写作技巧

撰写开题报告时&#xff0c;遭循以下结构将有助于你条理清晰地展示你的研究计划: 研究目标 1.研究背景:简要介绍你选择该研究题目的背景&#xff0c;阐述研究的重要性。 2.研究问题:明确阐述你的研究将解决的核心问题。 研究价值 1.理论价值:探讨你的研究在学术领域内的贡献&a…
阅读更多...
C语言 | Leetcode C语言题解之第437题路径总和III

C语言 | Leetcode C语言题解之第437题路径总和III

题目&#xff1a; 题解&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/ //递归遍历树节点&#xff0c;判断是否为有效路径 int dfs(struct TreeNode * root, int ta…
阅读更多...
基于RealSense D435相机实现手部姿态重定向

基于RealSense D435相机实现手部姿态重定向

基于Intel RealSense D435 相机和 MediaPipe的手部姿态检测&#xff0c;进一步简单实现手部姿态与机器人末端的重定向。 假设已经按照【基于 RealSenseD435i相机实现手部姿态检测】配置好所需的库和环境&#xff0c;并且有一个可以控制的机器人接口。 一、手部姿态重定向介绍 …
阅读更多...
【WRF运行第二期（Ubuntu）】ARWpost安装及错误总结

【WRF运行第二期（Ubuntu）】ARWpost安装及错误总结

WRF运行第二期&#xff1a;ARWpost安装及错误总结 1 ARWpost介绍2 ARWpost安装2.1 ARWpost_V3安装前准备2.2 安装ARWpost2.3 修改Makefile文件2.4 修改configure.arwp文件2.5 生成可执行文件EXE另&#xff1a;报错1-Error: Type mismatch between actual argument at (1) and a…
阅读更多...
【项目】基于Linux和C++的动态在线视频点播系统设计

【项目】基于Linux和C++的动态在线视频点播系统设计

文章目录 1. 前言1.1 源码1.2 项目简介1.3 实现内容1.4 涉及技术 / 环境 2. 整体架构2.1 服务器功能2.2 服务器结构 3. 前提步骤3.1 思路分析3.2 创建视频表 4. 后端 基本功能实现&#xff08;视频点播&#xff09;4.1 服务端工具类实现4.2 日志输出类4.3 数据库/表 管理类4.4 …
阅读更多...
前端开发之代理模式

前端开发之代理模式

介绍 代理模式是一种结构型设计模式&#xff0c;它通过为一个对象提供一个代理对象来控制对该对象的访问。代理对象可以在访问真实对象之前或之后添加一些额外的操作。 class RealImg {fileName: string;constructor(fileName: string) {this.fileName fileName;}disPlay()…
阅读更多...
ValueError: Out of range float values are not JSON compliant

ValueError: Out of range float values are not JSON compliant

可能原因一 可能原因二 数据里面有NaN
阅读更多...
优化java中 HashMap 的容量](capacity值)

优化java中 HashMap 的容量](capacity值)

我们很多人都知道&#xff0c;分配比我们所需更多的内存可能会对应用程序的性能产生负面影响。因此&#xff0c;使用带有容量的构造函数创建列表可能会产生很大的不同。 但是&#xff0c;使用Maps时&#xff0c;这个优化步骤可能不是那么简单。在本文中&#xff0c;我们将学习…
阅读更多...
Django 基础之启动命令和启动配置修改

Django 基础之启动命令和启动配置修改

Django启动 django启动一般可以通过ide或者命令启动 ide启动&#xff1a; 启动命令&#xff1a; python manage.py runserver该命令后续可以增加参数&#xff0c;如&#xff1a; python manage.py runserver 8081 python manage.py runserver 127.0.0.1:8082 注意&#xff1…
阅读更多...
PDF转换器哪个好？这5款PDF工具值得推荐

PDF转换器哪个好？这5款PDF工具值得推荐

PDF转换器哪个好&#xff1f;选择一款优质的PDF转换器&#xff0c;能够极大地提升我们的工作效率与灵活性。它不仅能轻松实现PDF文件与Word、Excel、PPT等多种格式间的互转&#xff0c;还支持图片、TXT等多种格式的转换&#xff0c;满足多样化的办公与学习需求。此外&#xff0…
阅读更多...
南卡首款耳夹开放式耳机，舒适与音质双双达行业峰值，再次“颠覆”行业！

南卡首款耳夹开放式耳机，舒适与音质双双达行业峰值，再次“颠覆”行业！

近日&#xff0c;南卡Ultra夹耳式蓝牙耳机的正式上市&#xff0c;再次在蓝牙耳机圈内掀起波澜。这款耳机以其超舒适的夹耳式设计和卓越音质&#xff0c;为用户带来了全新的音乐体验&#xff0c;有望重新定义夹耳式耳机的市场标准。 南卡品牌背后有着强大的研发实力和丰富的行业…
阅读更多...
一文读懂Service以及实践攻略

一文读懂Service以及实践攻略

一文读懂Service以及实践攻略 目录 1 一文读懂 Kubernetes Service 以及实践攻略 1.1 1. 什么是 Service&#xff1f; 1.1.1 为什么需要 Service&#xff1f; 1.2 2. Service 的工作原理 1.2.1 核心概念1.2.2 流量转发过程 1.3 3. Service 的几种类型及应用场景 2 实践&#…
阅读更多...
网络与信息安全工程师（工信部教育与考试中心）

网络与信息安全工程师（工信部教育与考试中心）

在当今数字化时代&#xff0c;大量的敏感信息与业务流程在网络上传输和处理&#xff0c;使得网络与信息安全成为保障企业运营、政务管理以及金融交易等关键领域不可忽视的一环。 因此&#xff0c;对网络安全专家的需求日益增长。 例如&#xff0c;金融机构、大型电信运营商以…
阅读更多...
云专线和虚拟专线是什么？两者有什么区别？

云专线和虚拟专线是什么？两者有什么区别？

云专线和虚拟专线是两种用于企业网络连接的技术方案&#xff0c;它们各自有不同的特点和适用场景。下面将分别介绍这两种技术&#xff0c;并指出它们之间的主要区别。 云专线 云专线是一种物理的或逻辑的专用线路&#xff0c;它直接连接企业的本地数据中心或分支机构与云端服务…
阅读更多...
最新文章

Copyright @ 2022~2023