找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 4458|回复: 5
打印 上一主题 下一主题
收起左侧

MATLAB等距线扫描程序实现思路与源程序

[复制链接]
跳转到指定楼层
楼主
由于网上多数都是c语言实现多边形扫描的例子我这就给大家一个matlab实现的方法吧


实现思路如下:
6月19作业题任务是用等距离的扫描线扫描下不规则多边形,如例图所示,获得扫描区间,并画出结果。
B是多边形顶点坐标
B=[0     1     2     3     6     7     9    10     9     8     7     5     4     3     2     1;
5     2     3     0     0     1     5     6    13    13    15    15    14    15    11    10]
Ymin=0,Ymax=15,需要n=100个扫描间隔,那么扫描距离就0.15,101条扫描线。
上面这部分编程肯定是没问题,接下就是模型的难点:
1、如何求扫描线与间隔的交点;
2、如果扫描线刚好扫描到多边形的顶点,要如何处理;
3、如果扫描线刚好扫描到多边形的边,要如何处理;
步骤:
1、从第一条扫描线开始扫描,扫描线为yi
2、从多边形的第一个点开始,取第一个点n1,  n1的上一个点n0,n1的下一个点n2,n2的下一个点n3。那么n1-n2就表示当前多边形的边,n0-n1表示前一条边,n2-n3表示后一条边,等下需要用到。
3、判断扫描线yi与n1-n2是否有交点,有就求交点,没有就回到步骤2,取下一个点n1;
判断是否有交点公式:abs(Y(n1)-yi)+ abs(Y(n2)-yi)== abs(Y(n1)-Y(n2)),abs(.)是绝对值的函数。
4、求得交点后,要判断如何记录。如果是普通的交点,就直接可以记录。如果交点刚好是多边形的顶点,或者扫描到多边形的边,就需要处理。
(1)情况1,扫描到普通交点,直接记录
(2)情况2,扫描到横线,这个时候就需要用到n0-n1,n2-n3,即前边与后边。
        <1> 如果是下图的情况,记录n1,n2
<2> 如果是下图的情况,记录n1
<3> 如果是下图的情况,记录n2
(3)情况3,扫描到顶点每一条边的两个顶点,第一个点是不算的,第二个点算。类似这样,实心表示这个点算上,空心表示不算。这样的目的是为了不让扫描到顶点时,会记录两次。
<1>遇到极大小值
<2>遇到下一条边n2-n3是横线的话,这个点就不用记录了。不然会多记录了该点
5、循环完所有的扫描线,就OK啦。最终就获得了一个所有扫描线多边形的交点的矩阵!
6、每一条扫描线扫描到的交点肯定是偶数滴,每两点画起来就OK。

程序方面:

最终我是写了如下两个函数的形式,这题是我最近在做的项目的中间环节,方便调用:
function [smqj]=saomiao(B,dt)
输入:B表示多边形,dt表示扫描间隔
输出:smqj表示最终的扫描区间    (英语特水,只能用拼音命名,用英语命名才高大上)
function huaxian(jl,ZB,MB,dt)(画线的函数自己写一下,我这里是有其他作用,多输入了一个ZB参数,所以有所区别)
输入:jl 表示扫描区间,ZB 表示子板多边形,MB 表示母板多边形,dt 表示扫描间隔
输出:直接显示图像

这题只是让你们处理母板多边形而已,所以调用的时候,直接 huaxian(M_QJ,MB,MB,dt)就可以了,自己运行程序看看。


注:程序里面出现这样的
其实是表示
abs(Y(n1)-yi)+ abs(Y(n2)-yi)== abs(Y(n1)-Y(n2))

(道理如A1==A2  ,写成 abs(A1-A2)<=0.000001)

在matlab里面,有可能会出现A1跟A2相等,却判断A1==A2为0的情况。如果测试A1-A2的话,会出现  e-14,也就是无穷小量,这是matlab本身精确度的问题,把他们当作不相等了。

在测试程序的时候就被这情况干扰了,才做了abs(A1-A2)<=0.000001的处理。

题外话:
1、上面也说了,这个题目是我最近在做的“皮革排版”项目的小部分内容。任务大概是:一张大的不规则母板皮革,要用它来裁剪 如皮带,皮包等材料的子板,如何排版这些材料,优化的处理这张母板皮革。
如输入5个图1,10个图2,6个图3,4个图4。用我们上面的母板,如何最优。

这个项目涉及到数学建模,比如:”如何把子板放到母板里面”,这个东西如何转化为数学描述就很有难度。  还有涉及到智能优化算法,如遗传算法,模拟退火算法等用于求最优解。  有参加数学建模的,有时间的可以考虑跟着做这个项目,还是有一定的帮助。

MATLAB源程序:
  1. %输出smqj为扫描区间,输入B为板块顶点,dt为扫描距离
  2. function [smqj]=saomiao(B,dt)
  3. X=B(:,1);
  4. Y=B(:,2);
  5. Y_MIN=min(Y);
  6. Y_MAX=max(Y);

  7. %%这一步是为了删除一些顶点,可有可无,还是保留一下。相邻两条线段斜率一样,删中间点
  8. k=[];
  9. for n1=1:size(Y,1)                %计算斜率
  10.     if n1~=size(Y,1)
  11.         n2=n1+1;
  12.     else
  13.         n2=1;
  14.     end
  15.     ki=(Y(n1)-Y(n2))/(X(n1)-X(n2));
  16.     k=[k ki];
  17. end

  18. d_p=[];                          %删除某些不必要顶点
  19. for n1=1:size(Y,1)
  20.      if n1~=size(Y,1)
  21.         n2=n1+1;
  22.     else
  23.         n2=1;
  24.      end
  25.     if k(n1)==k(n2)
  26.        d_p=[d_p n1];
  27.     end
  28. end

  29. X(d_p+1,:)=[];   %删除数据     
  30. Y(d_p+1,:)=[];   %删除数据
  31. k(:,d_p+1)=[];   %删除数据

  32. %%下面才是扫描的重点

  33. %%开始扫描线
  34. smqj=[];           %用来保存交点
  35. for yi=Y_MIN:dt:Y_MAX
  36.     smqji=[];   %用于记录每行交点
  37.     for n1=1:size(Y,1)
  38.         %n0-n1为上一条线段
  39.         if n1~=1
  40.             n0=n1-1;
  41.         else
  42.             n0=size(Y,1);
  43.         end
  44.         %n1-n2为当前线段
  45.         if n1~=size(Y,1)
  46.             n2=n1+1;
  47.         else
  48.             n2=1;
  49.         end
  50.         %n2-n3为下一条线段
  51.         if n2~=size(Y,1)
  52.             n3=n2+1;
  53.         else
  54.             n3=1;
  55.         end
  56.         
  57.         
  58.         %*******求交点坐标********
  59.         xi=[];   %初始无交点
  60.         if abs(abs(Y(n1)-yi)+abs(Y(n2)-yi)-abs(Y(n1)-Y(n2)))<=0.000001   %说明存在交点
  61.             if (X(n1)-X(n2))~=0 && (Y(n1)-Y(n2))~=0
  62.                 ki=(Y(n1)-Y(n2))/(X(n1)-X(n2));
  63.                 xi=(yi-Y(n2))/ki+X(n2);
  64.                 p=[xi;yi];             %交点坐标
  65.             elseif (X(n1)-X(n2))==0
  66.                 xi=X(n1);
  67.                 p=[xi;yi];
  68.             elseif (Y(n1)-Y(n2))==0    %先取两个端点交点,再判断是否取
  69.                 xi=X(n1);%表示存在而已,不记录
  70.                 p1=[X(n1);yi];
  71.                 p2=[X(n2);yi];
  72.             end
  73.         end
  74.         %*****判断改坐标是否记录*****
  75.         if isempty(xi)==0    %如果存在xi,即有交点
  76.             if sum(Y(find(X==xi))==yi)==0   %说明不是多边形顶点
  77.                 smqji=[smqji p];            %直接记录
  78.             else %下面是顶点的情况
  79.                 if  sign(Y(n1)-Y(n2))==0     %本条线是横线
  80.                     if (sign(Y(n0)-Y(n1))+sign(Y(n2)-Y(n3)))==0
  81.                         smqji=[smqji p1 p2];  %两点都记录
  82.                     end
  83.                     if sign(Y(n0)-Y(n1))>0 && sign(Y(n2)-Y(n3))>0
  84.                         smqji=[smqji p1];  %只取前一个
  85.                     end
  86.                     if sign(Y(n0)-Y(n1))<0 && sign(Y(n2)-Y(n3))<0
  87.                         smqji=[smqji p2];  %只取后一个
  88.                     end
  89.                 elseif   xi==X(n2)   %如果不是横线,后交点才记录,前交点不用管
  90.                     if  (sign(Y(n1)-Y(n2))+sign(Y(n2)-Y(n3)))==0  %说明是极大极小值
  91.                         smqji=[smqji p p];      %需要记录两个
  92.                     else
  93.                         if sign(Y(n2)-Y(n3))~=0 %下一条如果是横线,也不用记录
  94.                            smqji=[smqji p];        %记录1个
  95.                         end
  96.                     end
  97.                 end
  98.             end
  99.         end
  100.     end
  101.     smqji=sort(smqji,2);  %按从小到大排列
  102.     smqj=[smqj smqji];
  103. end
复制代码


全部资料51hei下载地址:
matlab等距线扫描多边形程序实现.zip (153.92 KB, 下载次数: 35)


分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享淘帖 顶 踩
回复

使用道具 举报

沙发
ID:523872 发表于 2019-4-28 22:00 | 只看该作者
您好,能提供一下子板材的程序吗,我邮箱:1764245803@qq.com,谢谢
回复

使用道具 举报

板凳
ID:523872 发表于 2019-4-28 22:08 | 只看该作者
您好啊,能提供一下子板材的程序么
回复

使用道具 举报

地板
ID:584107 发表于 2019-7-14 22:07 来自手机 | 只看该作者
楼主能把排版放置那部分的算法给一下吗?
回复

使用道具 举报

5#
ID:757518 发表于 2020-5-21 16:28 | 只看该作者
定定 ,介绍不错,不过感觉这个思想还是没有掌握
回复

使用道具 举报

6#
ID:757518 发表于 2020-5-27 15:52 | 只看该作者
好奇下,如果是多连通区域呢 ,就是中间有孔洞呢,扫描线要怎么避开然后实现连接?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表