由于网上多数都是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源程序: - %输出smqj为扫描区间,输入B为板块顶点,dt为扫描距离
- function [smqj]=saomiao(B,dt)
- X=B(:,1);
- Y=B(:,2);
- Y_MIN=min(Y);
- Y_MAX=max(Y);
- %%这一步是为了删除一些顶点,可有可无,还是保留一下。相邻两条线段斜率一样,删中间点
- k=[];
- for n1=1:size(Y,1) %计算斜率
- if n1~=size(Y,1)
- n2=n1+1;
- else
- n2=1;
- end
- ki=(Y(n1)-Y(n2))/(X(n1)-X(n2));
- k=[k ki];
- end
- d_p=[]; %删除某些不必要顶点
- for n1=1:size(Y,1)
- if n1~=size(Y,1)
- n2=n1+1;
- else
- n2=1;
- end
- if k(n1)==k(n2)
- d_p=[d_p n1];
- end
- end
- X(d_p+1,:)=[]; %删除数据
- Y(d_p+1,:)=[]; %删除数据
- k(:,d_p+1)=[]; %删除数据
- %%下面才是扫描的重点
- %%开始扫描线
- smqj=[]; %用来保存交点
- for yi=Y_MIN:dt:Y_MAX
- smqji=[]; %用于记录每行交点
- for n1=1:size(Y,1)
- %n0-n1为上一条线段
- if n1~=1
- n0=n1-1;
- else
- n0=size(Y,1);
- end
- %n1-n2为当前线段
- if n1~=size(Y,1)
- n2=n1+1;
- else
- n2=1;
- end
- %n2-n3为下一条线段
- if n2~=size(Y,1)
- n3=n2+1;
- else
- n3=1;
- end
-
-
- %*******求交点坐标********
- xi=[]; %初始无交点
- if abs(abs(Y(n1)-yi)+abs(Y(n2)-yi)-abs(Y(n1)-Y(n2)))<=0.000001 %说明存在交点
- if (X(n1)-X(n2))~=0 && (Y(n1)-Y(n2))~=0
- ki=(Y(n1)-Y(n2))/(X(n1)-X(n2));
- xi=(yi-Y(n2))/ki+X(n2);
- p=[xi;yi]; %交点坐标
- elseif (X(n1)-X(n2))==0
- xi=X(n1);
- p=[xi;yi];
- elseif (Y(n1)-Y(n2))==0 %先取两个端点交点,再判断是否取
- xi=X(n1);%表示存在而已,不记录
- p1=[X(n1);yi];
- p2=[X(n2);yi];
- end
- end
- %*****判断改坐标是否记录*****
- if isempty(xi)==0 %如果存在xi,即有交点
- if sum(Y(find(X==xi))==yi)==0 %说明不是多边形顶点
- smqji=[smqji p]; %直接记录
- else %下面是顶点的情况
- if sign(Y(n1)-Y(n2))==0 %本条线是横线
- if (sign(Y(n0)-Y(n1))+sign(Y(n2)-Y(n3)))==0
- smqji=[smqji p1 p2]; %两点都记录
- end
- if sign(Y(n0)-Y(n1))>0 && sign(Y(n2)-Y(n3))>0
- smqji=[smqji p1]; %只取前一个
- end
- if sign(Y(n0)-Y(n1))<0 && sign(Y(n2)-Y(n3))<0
- smqji=[smqji p2]; %只取后一个
- end
- elseif xi==X(n2) %如果不是横线,后交点才记录,前交点不用管
- if (sign(Y(n1)-Y(n2))+sign(Y(n2)-Y(n3)))==0 %说明是极大极小值
- smqji=[smqji p p]; %需要记录两个
- else
- if sign(Y(n2)-Y(n3))~=0 %下一条如果是横线,也不用记录
- smqji=[smqji p]; %记录1个
- end
- end
- end
- end
- end
- end
- smqji=sort(smqji,2); %按从小到大排列
- smqj=[smqj smqji];
- end
-
复制代码
全部资料51hei下载地址:
|