求平面连接线段组成的所有最小闭合区间

这个功能确实非常实用,我在过去开发地面分区编辑器时就曾应用过这一算法。最近,在新产品的开发中再次遇到了类似的需求。尽管之前已经实现过,但由于长时间未接触,对算法的具体细节有所遗忘,导致重新编写时耗费了不少时间。

起初,我尝试采用广度优先搜索来解决问题,却发现这种方法需要遍历所有可能性以找到最小面积的解,性能上显得过于低下。经过一番考量后,最终决定回归之前所用的更为高效的算法。这种算法不仅能够满足性能要求,还能有效减少开发时间和资源消耗。

如下图示例:

想要求出图中所有闭合区域,首先要收集这些线段,并绑定他们的关系。

 private static Dictionary<Vector3, HashSet<Vector3>> BuildAdjacencyList(List<LineSegment> segments)
    {
        var graph = new Dictionary<Vector3, HashSet<Vector3>>();

        foreach (var segment in segments)
        {
            AddVertexToGraph(segment.Start, graph);
            AddVertexToGraph(segment.End, graph);
            graph[segment.Start].Add(segment.End);
            graph[segment.End].Add(segment.Start);
        }
        RemoveSingletonVertices(ref graph);
        return graph;
    }

如上,构建无向图邻接表。将顶点收集并绑定相邻的顶点。我们要移除那些顶点相邻顶点只有一个的数据。他是组成不了闭合区间的。

接下来,我们需要分别计算出最小闭合区间和最大闭合区间。核心算法如下:

  1. 选择起始顶点

    • 选出一个 x 值最小的顶点作为第一个顶点。
    • 如果有多个顶点的 x 值相同,则选择 y 值最小的顶点。
  2. 逆时针选择顶点

    • 从选定的起始顶点开始,沿着逆时针方向选择下一个顶点。
    • 重复此过程,直到找出的顶点和第一个顶点相同,形成最小闭合区间。
  3. 计算最大闭合区间

    • 最大闭合区间算法与最小闭合区间相似。也是逆时针选出。但是从第三个点开始选最外围的也就是夹角最大的顶点。注意:需要用叉乘判断是凸角还是凹角。若是凹角,则角度=360-夹角。
  4. 移除边缘顶点

    • 遍历最小闭合区间的顶点,检查每个顶点的相邻顶点数是否为 2。
    • 如果某个顶点的相邻顶点数为 2,并且该顶点同时存在于最大闭合区间中,则将其视为边缘顶点并移除。
    • 移除顶点的同时,解除其他顶点与该顶点的相邻关系。
  5. 循环操作

    • 重复上述步骤,直到所有顶点都被移除。

通过这些步骤,我们就可以找出最小闭合区间啦。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring Boot开发入门教程

简介 Spring Boot是一个开源的Java基础框架&#xff0c;用于创建独立、生产级的基于Spring框架的应用程序。通过Spring Boot&#xff0c;你可以轻松地创建独立的、生产级的Spring应用程序。 环境准备 Java开发环境&#xff1a;确保你的机器上安装了Java 8或更高版本。Maven…

虚拟化数据恢复—XenServer虚拟机中SQL Server数据库数据恢复案例

服务器虚拟化数据恢复环境&#xff1a; 某品牌720服务器中有一组通过同品牌、型号为H710P的RAID卡4块STAT硬盘组建的RAID10磁盘阵列。上层部署XenServer虚拟化平台。1台Windows Server操作系统虚拟机&#xff0c;该虚拟机有2块虚拟磁盘&#xff08;系统盘数据盘&#xff09;&am…

2024年【流动式起重机司机】模拟考试及流动式起重机司机证考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 流动式起重机司机模拟考试考前必练&#xff01;安全生产模拟考试一点通每个月更新流动式起重机司机证考试题目及答案&#xff01;多做几遍&#xff0c;其实通过流动式起重机司机模拟考试题很简单。 1、【多选题】( )和…

移动应用开发:实现简易调查问卷

文章目录 前言一&#xff0c;创建SurveyActivity活动二&#xff0c;设计UI三&#xff0c;创建字符串资源文件四&#xff0c;编写活动代码五&#xff0c;更新 AndroidManifest.xml六&#xff0c;运行测试 前言 在Android Studio中开发一个调查问卷界面思路解析&#xff1a; 创建…

深度学习-图像评分实验(TensorFlow框架运用、读取处理图片、模型建构)

目录 0、实验准备 ①实验环境 ②需要下载的安装包 ③注意事项&#xff08;很关键&#xff0c;否则后面内容看不懂&#xff09; ④容易出现的问题 1、查看数据并读取数据。 2、PIL库里的Image包进行读取&#xff08;.resize更改图片尺寸&#xff0c;并将原始数据归一化处…

Intern大模型训练营(五):书生大模型全链路开源体系笔记

观看视频&#xff0c;可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点&#xff1a; 这张图讲述了书生浦语大模型开源的发展史&#xff0c;同时与主流的llama和Chatgpt模型进行比较&#xff0c;可以看出在参数上&#xff0c;InterLM在努力追赶甚至超…

《 C++ 修炼全景指南:十九 》想懂数据库?深入 B 树的世界,揭示高效存储背后的逻辑

摘要 本文深入探讨了 B 树的原理、操作、性能优化及其实际应用。B 树作为一种平衡多路树结构&#xff0c;因其高效的查找、插入和删除操作广泛应用于数据库与文件系统中。文章首先介绍了 B 树的定义与性质&#xff0c;并详细阐述了节点分裂、合并等核心操作的实现方法。接着&a…

开源模型应用落地-glm模型小试-glm-4-9b-chat-批量推理(二)

一、前言 GLM-4是智谱AI团队于2024年1月16日发布的基座大模型&#xff0c;旨在自动理解和规划用户的复杂指令&#xff0c;并能调用网页浏览器。其功能包括数据分析、图表创建、PPT生成等&#xff0c;支持128K的上下文窗口&#xff0c;使其在长文本处理和精度召回方面表现优异&a…

libgdiplus在MacOS M1上问题:Unable to load shared library ‘libgdiplus‘

libgdiplus在MacOS M1上问题&#xff1a;Unable to load shared library libgdiplus 问题解决步骤1步骤2 问题 在mac上的pycharm中执行下面的代码时出现下面的错误 slide.get_thumbnail( RuntimeError: Proxy error(TypeInitializationException): The type initializer for…

大健康零售行业帮助中心的构建与客户服务优化

在大健康零售行业&#xff0c;客户服务的质量直接影响着企业的品牌形象和市场竞争力。随着数字化转型的推进&#xff0c;构建一个高效、智能的帮助中心成为了提升客户服务和满意度的关键。本文将分析大健康零售行业如何通过构建帮助中心来优化客户服务&#xff0c;并提升客户满…

typescript 补充

文章目录 Pick<T, K> 从 T 中挑选部分属性构成新类型Partial<T>&#xff1a;将类型的所有属性变为可选Required<T>&#xff1a;将类型的属性变为必选。Omit<T, K>&#xff1a;从 T 中移除部分属性构成新类型。Readonly<T>&#xff1a;将类型的属…

Git介绍以及SSH配置

目录 1. Git介绍 1.1 Git的基本原理 1.2 Git的主要功能 1.3 Git的优点 1.4 Git的缺点 2. Git安装 3. SSH配置 1. Git介绍 Git是一款功能强大的分布式版本控制系统&#xff0c;最初由Linux操作系统的开发者Linus Torvalds在2005年开发&#xff0c;用于管理Linux内核的源代…

java多线程sleep() 和 wait() 有什么区别?

大家好&#xff0c;我是锋哥。今天分享关于【java多线程sleep() 和 wait() 有什么区别?】面试题。希望对大家有帮助&#xff1b; java多线程sleep() 和 wait() 有什么区别? 在Java中&#xff0c;sleep() 和 wait() 都是多线程编程中常用的控制线程执行的方法。它们看似有相似…

从无音响Windows 端到 有音响macOS 端实时音频传输播放

以下是从 Windows 端到 macOS 端传输音频的优化方案&#xff0c;基于上述链接中的思路进行调整&#xff1a; Windows 端操作 安装必要软件 安装 Python&#xff08;确保版本兼容且已正确配置环境变量&#xff09;。安装 PyAudio 库&#xff0c;可通过 pip install pyaudio 命令…

测度论原创(三)

Morden Prob 文章目录 Morden ProbWeek3多维扩展和随机向量定理3.1推论&#xff1a;random variable的变换定理3.2 连续函数的可测性定理3.3 可测函数的线性组合关于拓展实数集的延伸定理3.4 可测函数的极限依旧为可测性随机变量的概率律&#xff08;Law of X X X&#xff09;…

【C++】C++移动语义、左值右值、左值引用右值引用、移动构造函数、std::move、移动赋值操作符

二十五、C移动语义、左值和右值、左值引用右值引用、移动构造函数、std::move、移动赋值操作符 本部分讨论一些更高级的C特性&#xff1a;C移动语义。但是讲移动语义之前我们得先了解什么左值右值、左值引用和右值引用。 1、C的左值和右值、左值引用和右值引用左值是有地址的…

uniapp实现H5和微信小程序获取当前位置(腾讯地图)

之前的一个老项目&#xff0c;使用 uniapp 的 uni.getLocation 发现H5端定位不准确&#xff0c;比如余杭区会定位到临平区&#xff0c;根据官方文档初步判断是项目的uniapp的版本太低。 我选择的方式不是区更新uniapp的版本&#xff0c;是直接使用高德地图的api获取定位。 1.首…

Pycharm,2024最新版Pycharm下载安装配置教程!

目录 1、Pycharm 简介2、Pycharm下载3、环境变量的配置4、Pycharm的使用 1、Pycharm 简介 Pycharm资料领取不收米 PyCharm是一种Python IDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;&#xff0c;带有一整套可以帮助用户在使用Py…

(十三)JavaWeb后端开发——MySQL2

目录 1.DQL数据查询语言 1.1基本查询 1.2条件查询 where关键字 1.3分组查询 1.4排序查询 1.5分页查询 2.多表设计 3.多表查询——联查 4.多表查询——子查询​ 5.MySQL 事务 6.事务管理&#xff08;事务进阶&#xff09; 7.MySQL 索引 1.DQL数据查询语言 分为五大…

C++虚继承演示

在继承中如果出现&#xff1a; 这种情况&#xff0c;B和C都继承了A&#xff0c;D继承了B、C 在D中访问A的成员会出现&#xff1a; 这样的警告 是因为在继承时A出现两条分支&#xff1a;ABD、ACD 编译器不知道访问的A中的元素是经过B继承还是C继承 所以B、C在继承A时要用到…