【计算几何】凸包问题 (Convex Hull)

【计算几何】凸包问题 (Convex Hull)

引言

凸多边形

凸多边形是指所有内角大小都在 [ 0 , π ] [0,π] [0,π]范围内的简单多边形

凸包

在平面上能包含所有给定点的最小凸多边形叫做凸包。

其定义为:对于给定集合 X,所有包含 X 的凸集的交集 S 被称为 X 的 凸包。

实际上可以理解为用一个橡皮筋包含住所有给定点的形态。

凸包用最小的周长围住了给定的所有点。如果一个凹多边形围住了所有的点,它的周长一定不是最小,如下图。根据三角不等式,凸多边形在周长上一定是最优的。

在这里插入图片描述

凸包的求法

主要介绍Graham扫描法

Graham Scan 算法求凸包

Graham Scan 算法是一种十分简单高效的二维凸包算法,能够在 O ( n l o g n ) O(nlogn) O(nlogn)
的时间内找到凸包。

Graham Scan 算法的做法是先确定一个起点(一般是最左边的点和最右边的点),然后一个个点扫过去,如果新加入的点和之前已经找到的点所构成的 “壳” 凸性没有变化,就继续扫,否则就把已经找到的最后一个点删去,再比较凸性,直到凸性不发生变化。分别扫描上下两个 “壳”,合并在一起,凸包就找到了。这么说很抽象,我们看图来解释:

在这里插入图片描述
在这里插入图片描述

先找 “下壳”,上下其实是一样的。首先加入两个点 A 和 B。

然后插入第三个点 C,并计算 A B ⃗ × B C ⃗ \vec{AB} \times \vec{BC} AB ×BC 的向量积,却发现向量积系数小于(等于)0,也就是说 B C ⃗ \vec{BC} BC
A B ⃗ \vec{AB} AB 的顺时针方向上。

在这里插入图片描述

于是删去 B 点。

在这里插入图片描述

按照这样的方法依次扫描,找完 “下壳” 后,再找 “上壳”。


#include <algorithm>struct Point {double x, y;// 重载减法运算符,用于计算向量差Point operator-(Point& p) {Point t;t.x = x - p.x;t.y = y - p.y;return t;}// 计算向量叉积double cross(Point p) {return x * p.y - p.x * y;}
};// 比较函数,用于排序点
bool cmp(Point& p1, Point& p2) {if (p1.x != p2.x) return p1.x < p2.x;return p1.y < p2.y;
}Point point[1005];  // 无序点
int convex[1005];   // 保存组成凸包的点的下标
int n;              // 坐标系的无序点的个数// 获取凸包的函数
int GetConvexHull() {// 按照x坐标排序,如果x相同则按照y坐标排序sort(point, point + n, cmp);int temp;int total = 0;// 构建下凸包for (int i = 0; i < n; i++) {// 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向while (total > 1 &&(point[convex[total - 1]] - point[convex[total - 2]]).cross(point[i] - point[convex[total - 1]]) <= 0)total--;  // 弹出栈顶点convex[total++] = i;  // 将当前点加入栈中}temp = total;  // 记录下凸包的点数// 构建上凸包for (int i = n - 2; i >= 0; i--) {// 如果当前栈中至少有两个点,并且新点使得栈顶的两个点与新点形成的向量不满足逆时针方向while (total > temp &&(point[convex[total - 1]] - point[convex[total - 2]]).cross(point[i] - point[convex[total - 1]]) <= 0)total--;  // 弹出栈顶点convex[total++] = i;  // 将当前点加入栈中}return total - 1;  // 返回组成凸包的点的个数,实际上多了一个,就是起点,所以组成凸包的点个数是 total - 1
}

代码解释

结构体 Point:

  • 包含两个成员变量 x 和 y,表示点的坐标。

  • 重载了减法运算符 operator-,用于计算两个点的向量差。

  • 定义了 cross 方法,用于计算两个向量的叉积。

比较函数 cmp:

  • 用于对点进行排序,首先按 x 坐标排序,如果 x 坐标相同则按 y 坐标排序。

全局变量:

  • point 数组存储无序点。

  • convex 数组存储组成凸包的点的下标。

  • n 表示无序点的个数。

函数 G e t C o n v e x H u l l GetConvexHull GetConvexHull:

  • 首先对点进行排序。

  • 构建下凸包:从左到右遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。

  • 构建上凸包:从右到左遍历点,使用栈来维护凸包的点,确保每次新加入的点与栈顶的两个点形成的向量满足逆时针方向。

  • 返回组成凸包的点的个数,注意实际点的个数是 total - 1,因为起点被重复计算了一次。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

UE5 03-物体碰撞检测

在你需要碰撞的物体上添加一个碰撞检测组件 碰撞预设 设置为NoCollision,这样移动过程中就不会有物理碰撞阻挡效果,只负责检测是否碰撞,比较难解释,如果学过Unity的话,可以把它理解成 Collision 为 Trigger -------------------下面这个有点像Unity的OnTriggerEnter,跟OnColli…

单对以太网连接器多场景应用

单对以太网连接器应用场景概述 单对以太网&#xff08;Single Pair Ethernet&#xff0c;简称SPE&#xff09;作为一种新兴的以太网技术&#xff0c;以其独特的优势在多个领域得到了广泛的应用。SPE通过单对电缆进行数据传输&#xff0c;支持高速数据传输&#xff0c;同时还能…

解决C++编译时的产生的skipping incompatible xxx 错误

问题 我在编译项目时&#xff0c;产生了一个 /usr/bin/ld: skipping incompatible ../../xxx/ when searching for -lxxx 的编译错误&#xff0c;如下图所示&#xff1a; 解决方法 由图中的错误可知&#xff0c;在编译时&#xff0c;是能够在我们指定目录下的 *.so 动态库的…

2024-7-9 Windows NDK,Clion,C4droid 编译环境配置(基础|使用命令编译,非AndroidStudio),小白(记录)友好型教程

2024-7-9 Windows NDK,Clion,C4droid 编译环境配置(基础|使用命令编译),小白友好型 一直想使用NDK编译出lua库,然后进行开发.结果一直不成功,问题Bug出现了一堆(主要还是自己太菜,毕竟咱是编程散修一名>_<) NDK之前一直不会配置(直接用命令配置的那种,非AndroidStudio),一…

PID控制与模糊PID控制的比较

一、PID控制器的设计 1.PID控制原理图&#xff1a; PID控制其结构框图如下图所示&#xff1a; 图1&#xff1a;PID控制器结构框图 2.PID控制器传递函数的一般表达式 PID控制器传递函数的一般表达形式为&#xff1a; 其中kp为比例增益&#xff1b;ki为积分增益&#xff1b;k…

昇思25天学习打卡营第22天 | Shufflenet图像分类

ShuffleNet图像分类 当前案例不支持在GPU设备上静态图模式运行&#xff0c;其他模式运行皆支持。 ShuffleNet网络介绍 ShuffleNetV1是旷视科技提出的一种计算高效的CNN模型&#xff0c;和MobileNet, SqueezeNet等一样主要应用在移动端&#xff0c;所以模型的设计目标就是利用有…

uniapp 表格,动态表头表格封装渲染

1.接口表格数据&#xff1a; {"headers": [{"label": "实例名","name": "v1","order": 1,"hide": false,"dateTypeValue": null},{"label": "所属科室","name&quo…

[从0开始轨迹预测][NMS]:NMS的应用(目标检测、轨迹预测)

非极大值抑制&#xff08;Non-Maximum Suppression&#xff0c;简称NMS&#xff09;是一种在计算机视觉中广泛应用的算法&#xff0c;主要用于消除冗余和重叠的边界框。在目标检测任务中&#xff0c;尤其是在使用诸如R-CNN系列的算法时&#xff0c;会产生大量的候选区域&#x…

【Linux进阶】文件系统3——目录树,挂载

前言 在Windows 系统重新安装之前&#xff0c;你可能会事先考虑&#xff0c;到底系统盘C盘要有多大容量&#xff1f;而数据盘D盘又要给多大容量等&#xff0c;然后实际安装的时候&#xff0c;你会发现其实C盘之前会有个100MB的分区被独立出来&#xff0c;所以实际上你就会有三个…

10、matlab中字符、数字、矩阵、字符串和元胞合并为字符串并将字符串以不同格式写入读出excel

1、前言 在 MATLAB 中&#xff0c;可以使用不同的数据类型&#xff08;字符、数字、矩阵、字符串和元胞&#xff09;合并为字符串&#xff0c;然后将字符串以不同格式写入 Excel 文件。 以下是一个示例代码&#xff0c;展示如何将不同数据类型合并为字符串&#xff0c;并以不…

ElementPlusError: [ElPagination] 你使用了一些已被废弃的用法,请参考 el-pagination 的官方文档 - 报警告之一

一、问题描述&#xff1a; 今天在使用elementui plus的时候遇到了一个奇葩的问题&#xff0c; 就是提示 使用了一些已被废弃的用法&#xff0c; 奇葩就在于我是 复制另一个页面的分页&#xff0c; 一摸一样的东西&#xff0c;就只这个页面报错&#xff0c; 分页也不出 为了这个…

C# Bitmap类型与Byte[]类型相互转化详解与示例

文章目录 一、Bitmap类型转Byte[]类型使用Bitmap类的Save方法使用Bitmap类的GetBytes方法 二、Byte[]类型转Bitmap类型使用MemoryStream将Byte[]数组转换为Bitmap对象使用System.Drawing.Imaging.BitmapImage类 总结 在C#编程中&#xff0c;Bitmap类型和Byte[]类型之间的相互转…

运动爱好者的新选择:哈氪聆光气传导耳机,轻巧又安全

平时不管是漫步街头、骑行穿梭&#xff0c;还是乘坐公共交通时&#xff0c;我总是喜欢佩戴耳机&#xff0c;借此隔绝外部的喧嚣&#xff0c;享受音乐的乐趣。在户外使用耳机&#xff0c;我更倾向于选择气传导耳机&#xff0c;它们更符合我的需求&#xff0c;因为这种耳机能让我…

在 PostgreSQL 里如何处理数据的版本跟踪和回滚?

文章目录 一、事务二、保存点三、使用版本控制扩展四、审计表和触发器五、使用时间戳列六、比较和还原数据七、考虑数据备份和恢复八、结论 在数据库管理中&#xff0c;数据的版本跟踪和回滚是非常重要的功能&#xff0c;有助于在数据操作出现错误或需要回滚到特定状态时进行有…

Mysql笔记-v2

零、 help、\h、? 调出帮助 mysql> \hFor information about MySQL products and services, visit:http://www.mysql.com/ For developer information, including the MySQL Reference Manual, visit:http://dev.mysql.com/ To buy MySQL Enterprise support, training, …

Windows11配置WSL2支持代理上网

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、安装WSL2分发版二、配置步骤三、测试总结 前言 说起来本来这个功能我也不需要的&#xff0c;只是最近突然有个需求就顺便研究了下&#xff0c;WSL2默认的网…

Dynamics365 UCI下的高级查找(不要留恋Classic了)

UCI界面已经用了多年了&#xff0c;在Classic下的的高级查找按钮(漏斗icon)已不见踪影 但因为使用习惯问题&#xff0c;还是有人会通过右上角高级设置&#xff0c;进入Classic界面找到漏斗Icon来使用高级查找 但新的UCI风格下已经没了高级查找的概念&#xff0c;取而代之的是基…

评估测试用例有效性 5个方面

评估测试用例的有效性是确保软件测试活动能够达到预期目标的关键步骤&#xff0c;有助于测试团队优化测试计划&#xff0c;提高测试效率&#xff0c;减少返工&#xff0c;节省成本。如果缺乏对测试用例的有效性评估&#xff0c;可能会导致测试用例无法覆盖关键功能点&#xff0…

python爬虫基础入门

步骤 获取网页内容&#xff1a; http请求 python的Requests库 解析网页内容 html网页结构 python的Beautiful Soup库 储存或分析数据 储存进数据库 作为ai分析的数据 转化为图表显示出来 DDoS攻击 通过给服务器发送海量高频请求&#xff0c;大量消耗网页资源&#…

JavaScript-日期对象

日期对象 作用&#xff1a;用来表示时间的对象 获取当前时间 const datenew Date();console.log(date);可以得到日期对象&#xff0c;里面的属性有星期&#xff0c;年月日&#xff0c;时分秒 获取指定时间 const datenew Date(2023-05-01);console.log(date); 获取时间戳 时间…