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

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

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

如下图示例:

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

 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. 循环操作

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

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

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

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

相关文章

springboot - 定时任务

定时任务是企业级应用中的常见操作 定时任务是企业级开发中必不可少的组成部分&#xff0c;诸如长周期业务数据的计算&#xff0c;例如年度报表&#xff0c;诸如系统脏数据的处理&#xff0c;再比如系统性能监控报告&#xff0c;还有抢购类活动的商品上架&#xff0c;这些都离不…

ES管理工具Cerebro 0.8.5 Windows版本安装及启动

前言&#xff1a; Cerebro 的下载地址 https://github.com/lmenezes/cerebro/releases Cerebro 默认监听IP 0.0.0.0 &#xff0c;默认端口9000&#xff0c;访问地址&#xff1a;http://localhost:9000 启动 cmd命令到安装目录下&#xff1a;cerebro-0.8.5\bin 执行命令 ce…

Flutter 正在切换成 Monorepo 和支持 workspaces

其实关于 Monorepo 和 workspaces 相关内容在之前《Dart 3.5 发布&#xff0c;全新 Dart Roadmap Update》 和 《Flutter 之 ftcon24usa 大会&#xff0c;创始人分享 Flutter 十年发展史》 就有简单提到过&#xff0c;而目前来说刚好看到 flaux 这个新进展&#xff0c;所以就再…

[论文][环境]3DGS+Colmap环境搭建_WSL2_Ubuntu22.04 - 副本

0. 前言 仅使用Ubuntu进行场景编译&#xff0c;场景渲染查看则使用Windows下官方提供的编译好的预编译包打开即可&#xff0c;非常方便&#xff08;要注意即使是预编译版本&#xff0c;Windows端也应该安装VS和CUDA Toolkit&#xff0c;要注意的是&#xff0c;最新的SIBR预编译…

json-server的使用(根据json数据一键生成接口)

一.使用目的 在前端开发初期&#xff0c;后端 API 可能还未完成&#xff0c;json-server 可以快速创建模拟的 RESTful API&#xff0c;帮助前端开发者进行开发和测试。 二.安装 npm install json-server //局部安装npm i json-server -g //全局安装 三.使用教程 1.准备一…

导入和部署自定义 LLM 大模型

本文以【Qwen2-7B-Instruct】模型为例&#xff0c;指导如何将自定义大模型导入到 TI 平台&#xff0c;并使用平台内置推理镜像部署大模型对话推理服务。 前置要求 申请 CFS 本文所涉及到的操作需要通过 CFS 存储模型文件&#xff0c;详情请查看创建文件系统及挂载点。 操作…

开源办公软件 ONLYOFFICE 深入探索

文章目录 引言1. ONLYOFFICE 创建的背景1. 1 ONLYOFFICE 项目启动1. 2 ONLYOFFICE 的发展历程 2. 核心功能介绍2. 1 桌面编辑器2. 1. 1 文档2. 1. 2 表格2. 1. 3 幻灯片 2. 2 协作空间2. 3 文档编辑器 - 本地部署版 3. 技术介绍4. 安装5. 优势与挑战6. 个人体验7. 强大但不止于…

HTTP慢速攻击原理及解决办法

目录 引言 HTTP慢速攻击原理 解决办法 Nginx Tomcat 华宇TAS IIS 结论 引言 HTTP慢速攻击&#xff08;Slow HTTP Attack&#xff09;是一种拒绝服务攻击&#xff08;DoS&#xff09;&#xff0c;攻击者通过故意缓慢地发送HTTP请求来耗尽服务器资源&#xff0c;导致合法…

[mysql]修改表和课后练习

目录 DDL数据定义语言 添加一个字段 添加一个字段到最后一个 添加到表中的第一个一个字段 选择其中一个位置: 修改一个字段:数据类型,长度,默认值(略) 重命名一个字段 删除一个字段 重命名表 删除表 清空表 DCL中事务相关内容 DCL中COMMIT和ROLLBACK的讲解 对比TR…

SpringBoot+ClickHouse集成

前面已经完成ClickHouse的搭建&#xff0c;创建账号&#xff0c;创建数据库&#xff0c;保存数据库等&#xff0c;接下来就是在SpringBoot项目中集成ClickHouse。 一&#xff0c;引入依赖 <!-- SpringBoot集成ClickHouse --> <dependency><groupId>com.baom…

搜维尔科技:【煤矿虚拟仿真】煤矿企业、高校、科研单位-多语言支持、数字孪生、交互式学习体验

品牌&#xff1a;SouVR 发票&#xff1a;支持专票、普票 单位&#xff1a;套 版本号&#xff1a;1.0 包装清单&#xff1a;软件1套 软件形式&#xff1a;U盘、光盘 运行环境&#xff1a;windows 应用对象&#xff1a;煤矿企业、高校、科研单位 系统配置&#xff1a;…

(五)Spark大数据开发实战:灵活运用PySpark常用DataFrame API

目录 一、PySpark 二、数据介绍 三、PySpark大数据开发实战 1、数据文件上传HDFS 2、导入模块及数据 3、数据统计与分析 ①、计算演员参演电影数 ②、依次罗列电影番位前十的演员 ③、按照番位计算演员参演电影数 ④、求每位演员所有参演电影中的最早、最晚上映时间及…

单链表的实现(数据结构)

一. 单链表的实现 我们在上一篇中简单的认识了链表的组成和结构&#xff0c;并打印出链表&#xff0c;那么今天就来具体实现一下单链表对于数据增加、删减、插入等。 接下来就是我们在链表中对于数据的增、删、插的实现&#xff0c;对于我们的链表来说在任何地方增加数据都需…

Golang | Leetcode Golang题解之第540题有序数组中的单一元素

题目&#xff1a; 题解&#xff1a; func singleNonDuplicate(nums []int) int {low, high : 0, len(nums)-1for low < high {mid : low (high-low)/2mid - mid & 1if nums[mid] nums[mid1] {low mid 2} else {high mid}}return nums[low] }

算法: 链表题目练习

文章目录 链表题目练习两数相加两两交换链表中的节点重排链表合并 K 个升序链表K 个一组翻转链表 总结 链表题目练习 两数相加 坑: 两个链表都遍历完后,可能需要进位. class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 l1;ListNode…

深入Pillow:处理图像下载中的意外挑战

在当今数字化时代&#xff0c;获取和处理图像数据已经成为了许多应用程序的核心功能。从社交媒体到电子商务&#xff0c;图像的获取和处理对于用户体验至关重要。下载图片不仅能够丰富我们的内容&#xff0c;还能够通过分析图像数据为我们的应用提供更多价值。然而&#xff0c;…

零基础Java第十三期:继承与多态(一)

目录 一、继承 1.1. 继承的目的 1.2. 继承的概念 1.3. 继承的语法 1.4. 父类的访问 1.5. 继承中的重载与重写 1.6. 子类的构造方法 1.7. 再谈初始化 一、继承 1.1. 继承的目的 我们来定义一个Dog和Cat的类&#xff1a; public class Dog {public int age;public Strin…

【ONLYOFFICE文档】8.2版本测评

文章目录 引言ONLYOFFICE 产品简介PDF编辑器新功能1.协作编辑 PDF&#xff0c;让团队合作更高效2.为 PDF 表单添加签名3.改进的简洁界面4.性能优化&#xff1a;更快、更高效的体验 文档编辑器中的新功能域代码功能&#xff1a;自动更新文档中的动态数据协作功能&#xff1a;轻松…

【JAVA】java 企业微信信息推送

前言 JAVA中 将信息 推送到企业微信 // 企微消息推送messageprivate String getMessage(String name, String problemType, String pushResults, Long orderId,java.util.Date submitTime, java.util.Date payTime) {String message "对接方&#xff1a;<font color\…

【RK3588 Linux 5.x 内核编程】-GPIO设备驱动与点亮LED

GPIO设备驱动与点亮LED 文章目录 GPIO设备驱动与点亮LED1、Linux中的GPIO介绍2、GPIO库和工具3、Linux内核GPIO操作步骤3.1 验证GPIO3.2 请求GPIO3.3 导出GPIO到sysfs(可选)3.4 设置GPIO为输入/输出3.5 更改GPIO的电平(值)3.6 读取GPIO的值(电平)3.7 释放GPIO4、GPIO驱动…