用Matlab求解绘制2D散点(x y)数据的最小外接矩形

用Matlab求解绘制2D散点(x y)数据的最小外接矩形

  • 0 引言
  • 1 原理介绍及实现
  • 2 完整代码及相关函数
  • 3 结语


0 引言

  散点/多边形的外接图形是确定模型轮廓或姿态的一种可视化方法,也是有很大的用途的。前面已经介绍过两种简单的散点 ( x , y ) {(x,y)} (x,y)外接图形的原理及实现过程,本篇继续理解下散点数据最小外接矩形原理

😜 且听絮叨

  前面提到的沿轴外接矩形,实际是一种简单的外接矩形,因为沿轴,所以方向已知,在 X O Y XOY XOY面内有一个解,所以比较好求;最小外接矩形通常指面积最小周长最小,在随机点中找满足条件的矩形,就需要在 X O Y XOY XOY内旋转矩形使其可以包含所有随机点,且面积/周长最小的,即为符合要求的解。本篇基于网上资料使用凸包算法求解散点的最小外接矩形。

1 原理介绍及实现

  先介绍下凸包算法求解最小外接矩形的步骤:

(1)先找散点 ( x i , y i ) {(x_{i},y_{i})} (xi,yi)的凸包点或最小外包多边形,问题转化为了求多边形的最小外接矩形。找凸包点可以调用matlab函数convhull,返回凸包点的坐标索引,进而可以得到外接多边形的角点坐标

edges = convhull(x,y); 
plot(x(edges),y(edges),'Color','b')

(2)以 n n n边形的一条边 ( A − B ) (A-B) (AB)为例,假设矩形的某边平行于 ( A − B ) (A-B) (AB),那么通过 ( A − B ) (A-B) (AB)仅有一个矩形可以包含所有散点。所以一共可以找到 n n n个矩形,通过比较n个矩形,找到满足面积最小/周长最小的一个即为所求解。

(3)如何找到平行于 ( A − B ) (A-B) (AB)边的矩形呢? 假设 ( A − B ) (A-B) (AB)边平行于Y轴,那么问题就等价于前面介绍过的找沿轴外接矩形的过程;若 ( A − B ) (A-B) (AB)不平行于Y轴,只用将所有散点或角点坐标旋转到以 ( A − B ) (A-B) (AB)为轴的坐标系下,然后用找沿轴外接矩形的原理,就能找到一个以 ( A − B ) (A-B) (AB)为边的矩形。

  下面为示例代码,相关函数在下一部分。

%% 散点外接图形
clc;clear;
n = 100;
x = rand(n,1); % 随机数
y = rand(n,1);figure(1)
scatter(x,y,'o')
hold on% 凸包多边形
edges = convhull(x,y); 
plot(x(edges),y(edges),'Color','b')% 散点x y最小外接矩形(XX最小)
[rectx,recty,area,perimeter] = minboundrect(x,y,'p');
hold on
plot(rectx,recty,Color='c',LineStyle='--',LineWidth=3.4);

2 完整代码及相关函数

💦💦💦💦💦

%% 散点求外接图形,与前面提到的两种进行对比
clc;clear;
n = 100;
x = rand(n,1); % 随机数
y = rand(n,1);figure(1)
scatter(x,y,'o')
hold on% 绘制外接圆(方法1)
[center_x,center_y,r] = maxBoundCycle(x,y);
para = [center_x-r, center_y-r, 2*r, 2*r];
rectangle('Position', para, 'Curvature', [1 1],'EdgeColor','g',LineStyle='-.');% 绘制外接圆(方法2)
hold on
theta = 0:pi/50:2*pi; %角度[0,2*pi] 
xx = center_x + r*cos(theta);
yy = center_y + r*sin(theta);
plot(xx,yy,'o')% 散点x y外接矩形[沿轴]
hold on
[boundary] = maxBoundRect(x,y);
plot(boundary(:,1),boundary(:,2),Color='b',LineStyle='-',LineWidth=1.2);% 散点x y最小外接矩形[]
[rectx,recty,area,perimeter] = minboundrect(x,y,'a');
hold on
plot(rectx,recty,Color='m',LineStyle=":",LineWidth=3.4);
% 最小外接矩形(求解函数)
function [rectx,recty,area,perimeter] = minboundrect(x,y,metric)
% minboundrect: Compute the minimal bounding rectangle of points in the plane
% usage: [rectx,recty,area,perimeter] = minboundrect(x,y,metric)
%
% arguments: (input)
%  x,y - vectors of points, describing points in the plane as
%        (x,y) pairs. x and y must be the same lengths.
%
%  metric - (OPTIONAL) - single letter character flag which
%        denotes the use of minimal area or perimeter as the
%        metric to be minimized. metric may be either 'a' or 'p',
%        capitalization is ignored. Any other contraction of 'area'
%        or 'perimeter' is also accepted.
%
%        DEFAULT: 'a'    ('area')
%
% arguments: (output)
%  rectx,recty - 5x1 vectors of points that define the minimal
%        bounding rectangle.
%
%  area - (scalar) area of the minimal rect itself.
%
%  perimeter - (scalar) perimeter of the minimal rect as found
%
%
% Note: For those individuals who would prefer the rect with minimum
% perimeter or area, careful testing convinces me that the minimum area
% rect was generally also the minimum perimeter rect on most problems
% (with one class of exceptions). This same testing appeared to verify my
% assumption that the minimum area rect must always contain at least
% one edge of the convex hull. The exception I refer to above is for
% problems when the convex hull is composed of only a few points,
% most likely exactly 3. Here one may see differences between the
% two metrics. My thanks to Roger Stafford for pointing out this
% class of counter-examples.
%
% Thanks are also due to Roger for pointing out a proof that the
% bounding rect must always contain an edge of the convex hull, in
% both the minimal perimeter and area cases.
%
%
% See also: minboundcircle, minboundtri, minboundsphere
%
%
% default for metric
if (nargin<3) || isempty(metric)metric = 'a';
elseif ~ischar(metric)error 'metric must be a character flag if it is supplied.'
else% check for 'a' or 'p'metric = lower(metric(:)');                    ind = strmatch(metric,{'area','perimeter'});             if isempty(ind)                error 'metric does not match either ''area'' or ''perimeter'''end% just keep the first letter.metric = metric(1);
end% preprocess data
x=x(:);
y=y(:);% not many error checks to worry about
n = length(x);                                    
if n~=length(y)                               error 'x and y must be the same sizes'
end% start out with the convex hull of the points to
% reduce the problem dramatically. Note that any
% points in the interior of the convex hull are
% never needed, so we drop them.
if n>3edges = convhull(x,y);  % 'Pp' will silence the warnings% exclude those points inside the hull as not relevant% also sorts the points into their convex hull as a% closed polygonx = x(edges);y = y(edges);% probably fewer points now, unless the points are fully convexnedges = length(x) - 1;                       
elseif n>1% n must be 2 or 3nedges = n;x(end+1) = x(1);y(end+1) = y(1);
else% n must be 0 or 1nedges = n;
end% now we must find the bounding rectangle of those
% that remain.% special case small numbers of points. If we trip any
% of these cases, then we are done, so return.
switch nedgescase 0% empty begets emptyrectx = [];recty = [];area = [];perimeter = [];returncase 1% with one point, the rect is simple.rectx = repmat(x,1,5);recty = repmat(y,1,5);area = 0;perimeter = 0;returncase 2% only two points. also simple.rectx = x([1 2 2 1 1]);recty = y([1 2 2 1 1]);area = 0;perimeter = 2*sqrt(diff(x).^2 + diff(y).^2);return
end
% 3 or more points.% will need a 2x2 rotation matrix through an angle theta
Rmat = @(theta) [cos(theta) sin(theta);-sin(theta) cos(theta)];% get the angle of each edge of the hull polygon.
ind = 1:(length(x)-1);
edgeangles = atan2(y(ind+1) - y(ind),x(ind+1) - x(ind));
% move the angle into the first quadrant.
edgeangles = unique(mod(edgeangles,pi/2));% now just check each edge of the hull
nang = length(edgeangles);              
area = inf;                           
perimeter = inf;
met = inf;
xy = [x,y];
for i = 1:nang                         % rotate the data through -theta rot = Rmat(-edgeangles(i));xyr = xy*rot;xymin = min(xyr,[],1);xymax = max(xyr,[],1);% The area is simple, as is the perimeterA_i = prod(xymax - xymin);P_i = 2*sum(xymax-xymin);if metric=='a'M_i = A_i;elseM_i = P_i;end% new metric value for the current interval. Is it better?if M_i<met% keep this onemet = M_i;area = A_i;perimeter = P_i;rect = [xymin;[xymax(1),xymin(2)];xymax;[xymin(1),xymax(2)];xymin];rect = rect*rot';rectx = rect(:,1);recty = rect(:,2);end
end

3 结语

💦💦💦💦💦
  本篇介绍了求解2维散点最小外接矩形原理,并提供了示例代码对相关过程进行了实现。希望对你有所帮助😜。






😜
😜😜
😜😜😜😜

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

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

相关文章

mysql——关于表的增删改查(CRUD)

目录 比较运算符和逻辑运算符图 一、增加&#xff08;Create&#xff09; 1、全列插入 2、指定列插入 二、查询&#xff08;Retrieve&#xff09; 1、全列查询 2、指定列查询 3、别名&#xff08;as&#xff09; 4、表达式查询 5、去重&#xff08;distinct&#xff09; 6、…

如何正确复盘带货直播间?

如何正确复盘带货直播间&#xff1f;其实&#xff0c;直播复盘可以分为四个关键步骤。首先&#xff0c;如果你的直播间没有人进来&#xff0c;核心问题往往是曝光率太低。观众不愿意点击进入你的直播间&#xff0c;那还谈什么卖货呢&#xff1f;平台也不会给予推荐流量。那么&a…

和服务端系统的通信

首先web网站 前端浏览器 和 后端系统 是通过HTTP协议进行通信的 同步请求&异步请求&#xff1a; 同步请求&#xff1a;可以从浏览器中直接获取的&#xff08;HTML/CSS/JS这样的静态文件资源)&#xff0c;这种获取请求的http称为同步请求 异步请求&#xff1a;js代码需要到服…

Android12_13左上角状态栏数字时间显示右移动

文章目录 问题场景解决问题 一、基础资料二、代码追踪三、解决方案布局的角度解决更改paddingStart 的默认值设置marginLeft 值 硬编码的角度解决 问题场景 1&#xff09;早期一般屏幕都是方形的&#xff0c;但是曲面屏&#xff0c;比如&#xff1a;好多车机Android产品、魔镜…

springboot 的共享session方案?

问&#xff1a;springboot 的共享session方案&#xff1f; 参考&#xff1a; https://juejin.cn/post/7195227930077691963分布式之session共享问题 4种解决方案及spring session的使用_分布式session共享方案-CSDN博客 什么是 Session &#xff1f; 答&#xff1a;因为Http协…

杂七杂八-部署框架

杂七杂八-部署框架 docker docker dockerhub&#xff1a;Docker发布/上传镜像到dockerhub&&下载/拉取镜像&&删除dockerhub镜像 仅个人笔记使用&#xff0c;感谢点赞关注 目前仅专注于 NLP 大模型 机器学习和前后端的技术学习和分享 感谢大家的关注与支持&…

前端技术(七)——less 教程

一、less简介 1. less是什么&#xff1f; less是一种动态样式语言&#xff0c;属于css预处理器的范畴&#xff0c;它扩展了CSS语言&#xff0c;增加了变量、Mixin、函数等特性&#xff0c;使CSS 更易维护和扩展LESS 既可以在 客户端 上运行 &#xff0c;也可以借助Node.js在服…

STM32CubeMx学习笔记——GPIO使用

一、新建工程 1、选择芯片型号 2、配置时钟RCC 选择 HSE(外部高速时钟) 为 Crystal/Ceramic Resonator(晶振/陶瓷谐振器) ​ 3、时钟树配置 在clock Configuration中将HCLK配置为最高频率然后回车 ​ 4、选择调试模式 SYS 设置&#xff0c;选择 Debug 为 Serial Wire …

Qt qrc机制

文章目录 0. 前言1. qrc机制2. qrc使用 0. 前言 要设置窗口图标&#xff0c;就需要有图片及其图片所在路径&#xff0c;在本机上可能没什么问题&#xff0c;但是换了一个机器&#xff0c;路径可能不一致或者图片丢失&#xff0c;这就导致图片显示不出来。 Qt引入qrc机制&…

【零基础学习CAPL】——CRC值监控测试

🙋‍♂️【零基础学习CAPL】系列💁‍♂️点击跳转 ——————————————————————————————————–—— 从0开始学习CANoe使用 从0开始学习车载车身 相信时间的力量 星光不负赶路者,时光不负有心人。 目录 1.概述2.需求介绍3.算法4.逻辑判断5.测…

swift qwen2-vl推理及加载lora使用案例

参考: https://swift.readthedocs.io/zh-cn/latest/Instruction/LLM%E5%BE%AE%E8%B0%83%E6%96%87%E6%A1%A3.html#%E5%BE%AE%E8%B0%83%E5%90%8E%E6%A8%A1%E5%9E%8B https://blog.csdn.net/weixin_42357472/article/details/142150209 SWIFT支持300+ LLM和50+ MLLM(多模态大模型…

《程序猿之设计模式实战 · 装饰者模式》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…

欢迎来到我的Java世界“抽象类”

前言 在上篇中我们学习到了继承的概念、语法等等&#xff0c;那么小编将来为大家方享下一篇Java中的抽象类。 1.抽象类的概念 2.抽象类的语法 3.抽象类的特性 4.抽象类的作用 一&#xff1a;讲到抽象类&#xff0c;大家是不是会很迷惑什么是抽象类&#xff1f; 在面向对象…

安卓framework美化手势导航侧滑返回UI

文章目录 手势导航的侧滑返回效果图原生效果如下:要实现的功能,: 实现代码1. 初始化代码2. 修改绘制的代码,进行箭头与退出UI的显示3. 拖动的时候手指上下移动时,箭头ui跟着移动 以下是一些其他可以美化安卓右滑手势拖动 UI 的方法&#xff1a;视觉效果方面形状和布局方面 安卓…

加密软件有哪些数据防护功能?

1.文件透明加密&#xff1a;采用透明加密技术&#xff0c;自动对指定类型的敏感文件进行实时加密&#xff0c;确保数据在存储和传输过程中的安全性。 2.权限管理与访问控制&#xff1a;通过细粒度的权限管理&#xff0c;控制员工对敏感数据的访问权限&#xff0c;包括读取、修…

PHP一键约课高效健身智能健身管理系统小程序源码

一键约课&#xff0c;高效健身 —— 智能健身管理系统让健康触手可及 &#x1f3cb;️‍♀️ 告别繁琐&#xff0c;一键开启健身之旅 你还在为每次去健身房前的繁琐预约流程而烦恼吗&#xff1f;现在有了“一键约课高效健身智能健身管理系统”&#xff0c;所有问题都迎刃而解…

Solana核心漏洞技术详解

8月9日&#xff0c;Solana团队齐心协力解决了一个严重的安全漏洞。这次秘密修复详情可以在GitHub上查询到。CertiK团队对这一漏洞进行了深入分析。 1. Solana漏洞起因 8月9日&#xff0c;Solana验证者和客户端团队齐心协力解决了一个严重的安全漏洞。Solana验证者Laine表示&am…

TypeScript 扩展

扩展 ?:可选参数 可选链事实上并不是TypeScript独有的特性&#xff0c;它是ES11&#xff08;ES2020&#xff09;中增加的特性 可选链使用可选链操作符 ? 作用是当对象的属性不存在时&#xff0c;会短路&#xff0c;直接返回undefined&#xff0c;如果存在&#xff0c;那么…

【机器学习】从零开始理解深度学习——揭开神经网络的神秘面纱

1. 引言 随着技术的飞速发展,人工智能(AI)已从学术研究的实验室走向现实应用的舞台,成为推动现代社会变革的核心动力之一。而在这一进程中,深度学习(Deep Learning)因其在大规模数据处理和复杂问题求解中的卓越表现,迅速崛起为人工智能的最前沿技术。深度学习的核心是…

安卓玩机工具-----ADB方式的刷机玩机工具“秋之盒”’ 测试各项功能预览

秋之盒 安卓玩机工具-秋之盒是一款ADB刷机工具箱&#xff0c;基于谷歌ADB的一款绿色安装&#xff0c;具备了海量扩展模块,支持ADB刷机救砖、一键激活黑域、adb指令修复等功能&#xff0c;是一款开源、免费、易用的手机刷机工具&#xff01; 并且是一款开源、免费、易用的图形化…