由于網(wǎng)上多數(shù)都是c語言實現(xiàn)多邊形掃描的例子我這就給大家一個matlab實現(xiàn)的方法吧
結(jié)果的實現(xiàn)大概就是這樣
實現(xiàn)思路如下：
6月19作業(yè)題任務是用等距離的掃描線掃描下不規(guī)則多邊形，如例圖所示，獲得掃描區(qū)間，并畫出結(jié)果。
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（.）是絕對值的函數(shù)。 4、求得交點后，要判斷如何記錄。如果是普通的交點，就直接可以記錄。如果交點剛好是多邊形的頂點，或者掃描到多邊形的邊，就需要處理。 （1）情況1，掃描到普通交點，直接記錄 （2）情況2，掃描到橫線，這個時候就需要用到n0-n1，n2-n3，即前邊與后邊。 <1> 如果是下圖的情況，記錄n1，n2 <2> 如果是下圖的情況，記錄n1 <3> 如果是下圖的情況，記錄n2 （3）情況3，掃描到頂點每一條邊的兩個頂點，第一個點是不算的，第二個點算。類似這樣，實心表示這個點算上，空心表示不算。這樣的目的是為了不讓掃描到頂點時，會記錄兩次。 <1>遇到極大小值 <2>遇到下一條邊n2-n3是橫線的話，這個點就不用記錄了。不然會多記錄了該點 5、循環(huán)完所有的掃描線，就OK啦。最終就獲得了一個所有掃描線多邊形的交點的矩陣！ 6、每一條掃描線掃描到的交點肯定是偶數(shù)滴，每兩點畫起來就OK。
程序方面：
最終我是寫了如下兩個函數(shù)的形式，這題是我最近在做的項目的中間環(huán)節(jié)，方便調(diào)用： function [smqj]=saomiao(B,dt) 輸入：B表示多邊形，dt表示掃描間隔 輸出：smqj表示最終的掃描區(qū)間 （英語特水，只能用拼音命名，用英語命名才高大上） function huaxian(jl,ZB,MB,dt)（畫線的函數(shù)自己寫一下，我這里是有其他作用，多輸入了一個ZB參數(shù)，所以有所區(qū)別） 輸入：jl 表示掃描區(qū)間，ZB 表示子板多邊形，MB 表示母板多邊形，dt 表示掃描間隔 輸出：直接顯示圖像
這題只是讓你們處理母板多邊形而已，所以調(diào)用的時候，直接 huaxian(M_QJ,MB,MB,dt)就可以了，自己運行程序看看。
注：程序里面出現(xiàn)這樣的 其實是表示 abs（Y(n1)-yi）+ abs(Y(n2)-yi)== abs(Y(n1)-Y(n2))
（道理如A1==A2 ,寫成 abs(A1-A2)<=0.000001）
在matlab里面，有可能會出現(xiàn)A1跟A2相等，卻判斷A1==A2為0的情況。如果測試A1-A2的話，會出現(xiàn) e-14，也就是無窮小量，這是matlab本身精確度的問題，把他們當作不相等了。
在測試程序的時候就被這情況干擾了，才做了abs(A1-A2)<=0.000001的處理。
題外話： 1、上面也說了，這個題目是我最近在做的“皮革排版”項目的小部分內(nèi)容。任務大概是：一張大的不規(guī)則母板皮革，要用它來裁剪 如皮帶，皮包等材料的子板，如何排版這些材料，優(yōu)化的處理這張母板皮革。 如輸入5個圖1，10個圖2，6個圖3，4個圖4。用我們上面的母板，如何最優(yōu)。
這個項目涉及到數(shù)學建模，比如：”如何把子板放到母板里面”，這個東西如何轉(zhuǎn)化為數(shù)學描述就很有難度。 還有涉及到智能優(yōu)化算法，如遺傳算法，模擬退火算法等用于求最優(yōu)解。 有參加數(shù)學建模的，有時間的可以考慮跟著做這個項目，還是有一定的幫助。
MATLAB源程序： - %輸出smqj為掃描區(qū)間，輸入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,:)=[]; %刪除數(shù)據(jù)
- Y(d_p+1,:)=[]; %刪除數(shù)據(jù)
- k(:,d_p+1)=[]; %刪除數(shù)據(jù)
- %%下面才是掃描的重點
- %%開始掃描線
- 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下載地址：
| 
