領域充填の走査線アルゴリズム
実は秩序あるエッジテーブルは実際に理解しても理解しても、肝心なのは思想をコードに変換することです.
まずアルゴリズムの考え方を紹介します.
1.与えられた多角形頂点座標に基づいてETテーブルを確立する(ymaxとyminを同時に計算する)
2.AETテーブルを空にする
3.走査線yi値を循環変数として使用し、初期値をyminとする
次の操作を繰り返します.
(1)ETテーブルのyiバケツが空でない場合、AETにマージ
(2)AETテーブルに対する記録をx値の小さい順から大きい順に並べ替える
(3)表の記録を順次取り出し、両ペアで記入する
(4)AETテーブルに記録されているymax=yiの場合、その記録を削除する
(5)AETに残っているレコードに対してx値を修正し、x=x+1/m(mは傾き)
今、肝心なのは詳細な処理とコードの実現です.
1.頂点座標は、頂点数を決定できないため、配列で保存します.パディング関数の作成
void regionfill(HDC hdc,Point1 *p,int len,int ymin,int ymax)
EdgeTableクラスを作成する必要があります.分析により、この構造は私たちのデータ構造の図(隣接テーブルで表される)に似ています.
コードは次のとおりです.
/*
*author qyl
*date 2012/4/7
*purpose
*version 1.1
*/
#include"LList.h"
#include"Point1.h"
class Edge{
public:
float x;
float increment;
float ymax;
Edge(){x=-1;increment=0;ymax=-1;}
Edge(float x0,float incr,float y0)
{
x=x0;
increment=incr;
ymax=y0;
}
friend bool operator &b)
{
return a.x(Edge &a,Edge &b)
{
return a.x>b.x;
}
};
class EdgeTable
{
private:
int numberLine;
int numberEdge;
LList **vertex;
public:
EdgeTable(int numLine)
{
int i;
numberLine=numLine;
numberEdge=0;
vertex=(LList**) new LList*[numberLine];
for(i=0;i();
}
~EdgeTable()
{
for(int i=0;iisEmpty();
}
LList* getValue(int pos)
{
Edge it;
LList* l=new LList();
for(vertex[pos]->setStart();vertex[pos]->getValue(it);vertex[pos]->next())
{
l->insert(it);
}
return l;
}
void setEdge(int pos,Edge e)
{
Edge curr;
for(vertex[pos]->setStart();vertex[pos]->getValue(curr);vertex[pos]->next())
{
if(curr.x<=e.x)
break;
}
numberEdge++;
vertex[pos]->insert(e);
}
void delEdge(int pos,Edge e)
{
Edge curr;
for(vertex[pos]->setStart();vertex[pos]->getValue(curr);vertex[pos]->next())
{
if(curr.ymax==e.ymax)
{
vertex[pos]->remove(curr);
numberEdge--;
}
}
}
void deleteAll(int pos)
{
numberEdge-=vertex[pos]->removeAll();
}
void createTableEdge(Point1 * p,int len,int ymin,int ymax)
{
Edge* e;
/*version 1.2
*
*/
// ,
/*
int *flag=new int[len];
for(int i=0;ip[0].getY() && p[len-1].getY()>p[0].getY())
*(flag+i)=2;
else if(p[1].getY()p[0].getY())
*(flag+i)=1;
else if(p[(i+1)%len].getY()>p[i].getY() && p[len-1].getY()
p[i].getY() && p[(i-1)%len].getY()>p[i].getY())
*(flag+i)=2;
else if(p[(i+1)%len].getY()
p[i].getY())
*(flag+i)=1;
else if(p[(i+1)%len].getY()>p[i].getY() && p[(i-1)%len].getY()
insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
break;
case 2:
if((*(flag+len-1))!=1 && (*(flag+len-1))!=3)
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
if((*(flag+j+1))!=1 && (*(flag+j+1)!=1)!=3)
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
break;
case 3:
if((*(flag+j+1))!=1 && (*(flag+j+1))!=3)
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
break;
default: break;
}
}
else
{
switch(mark)
{
case 0: break;
case 1:
if((*(flag+j-1))!=1 && (*(flag+j-1))!=3)
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[j-1].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[j-1].getY()-1);
vertex[i]->insert(*e);
}
break;
case 2:
if((*(flag+(j+1)%len))!=1 && (*(flag+(j+1)%len))!=3)
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
if((*(flag+j-1))!=1 && (*(flag+j-1))!=3)
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[j-1].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[j-1].getY()-1);
vertex[i]->insert(*e);
}
break;
case 3:
if((*(flag+(j+1)%len))!=1 && (*(flag+(j+1)%len))!=3)
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
break;
default: break;
}
}
}
}
}
*/
/*
for(int i=ymin;i<=ymax;i++)
{
for(int j=0;jp[0].getY() && p[len-1].getY()>p[0].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
// ymax-1
else if(p[1].getY()>p[0].getY() && p[len-1].getY()
insert(*e);
}
// ymax-1
else if(p[1].getY()
p[0].getY())
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
}
else
{
if(p[(j+1)%len].getY()>p[j].getY() && p[(j-1)%len].getY()>p[j].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
// ymax-1
else if(p[(j+1)%len].getY()>p[j].getY() && p[(j-1)%len].getY()
insert(*e);
}
// ymax-1
else if(p[(j+1)%len].getY()
p[j].getY())
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
}
}
}
*/
/*
for(int j=0;jp[0].getY() && p[len-1].getY()>p[0].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
// ymax-1
else if(p[1].getY()>p[0].getY() && p[len-1].getY()
insert(*e);
}
// ymax-1
else if(p[1].getY()
p[0].getY())
{
e=new Edge(p[1].getX(),(p[1].getX()-p[j].getX())/(p[1].getY()-p[j].getY()),p[1].getY()-1);
vertex[(int)p[1].getY()]->insert(*e);
}
}
else
{
if(p[(j+1)%len].getY()>p[j].getY() && p[(j-1)%len].getY()>p[j].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
// ymax-1
else if(p[(j+1)%len].getY()>p[j].getY() && p[(j-1)%len].getY()
insert(*e);
}
// ymax-1
else if(p[(j+1)%len].getY()
p[j].getY())
{
e=new Edge(p[(j+1)%len].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[(int)p[(j+1)%len].getX()]->insert(*e);
}
}
}
*/
for(int i=ymin;i<=ymax;i++)
{
for(int j=0;jp[0].getY() && p[len-1].getY()>p[0].getY())
{
if(p[2].getY()>p[1].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
if(p[len-2].getY()>p[len-1].getY())
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY());
vertex[i]->insert(*e);
}
}
// ymax-1
else if(p[1].getY()>p[0].getY() && p[len-1].getY()
p[1].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
}
// ymax-1
else if(p[1].getY()
p[0].getY())
{
if(p[len-2].getY()>p[len-1].getY())
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[len-1].getX()-p[j].getX())/(p[len-1].getY()-p[j].getY()),p[len-1].getY());
vertex[i]->insert(*e);
}
}
}
else
{
if(p[(j+1)%len].getY()>p[j].getY() && p[j-1].getY()>p[j].getY())
{
if(p[(j+2)%len].getY()>p[(j+1)%len].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
if(j==1)
{
if(p[len-1].getY()>p[j-1].getY())
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY());
vertex[i]->insert(*e);
}
}
else
{
if(p[j-2].getY()>p[j-1].getY())
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY());
vertex[i]->insert(*e);
}
}
}
// ymax-1
else if(p[(j+1)%len].getY()>p[j].getY() && p[(j-1)%len].getY()
p[(j+1)%len].getY())
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j+1)%len].getX()-p[j].getX())/(p[(j+1)%len].getY()-p[j].getY()),p[(j+1)%len].getY());
vertex[i]->insert(*e);
}
}
// ymax-1
else if(p[(j+1)%len].getY()
p[j].getY())
{
if(j==1)
{
if(p[len-1].getY()>p[j-1].getY())
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY());
vertex[i]->insert(*e);
}
}
else
{
if(p[j-2].getY()>p[j-1].getY())
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY()-1);
vertex[i]->insert(*e);
}
else
{
e=new Edge(p[j].getX(),(p[(j-1)%len].getX()-p[j].getX())/(p[(j-1)%len].getY()-p[j].getY()),p[(j-1)%len].getY());
vertex[i]->insert(*e);
}
}
}
}
}
}
}
};
コードは少し乱れていますが、いくつかの間違いの私は削除していません.ただ、どのように一歩一歩改善したのか、発見した間違いを示しています.変更した後、いくつかの注釈も修正したようです.
この時計は構造が成り立っていれば,実はほかの時計は簡単だ.
この関数は走査線アルゴリズムです.
void regionfill(HDC hdc,Point1 *p,int len,int ymin,int ymax)
{
EdgeTable ET(/*ymax-ymin+1*/1024);
// ET
ET.createTableEdge(p,len,ymin,ymax);
// AET
EdgeTable AET(1024);
LList* l,*ptr;
for(int i=ymin;i<=ymax;i++)
{
// ET i ， AET
if(!ET.isEmptyInLine(i))
{
Edge curr;
l=ET.getValue(i);
for(l->setStart();l->getValue(curr);l->next())
{
AET.setEdge(i,curr);
}
l->removeAll();
}
// AET
Edge curr;
Edge temp;
Edge min;
ptr=l=AET.getValue(i);
/*
AET.deleteAll(i);
int count=0;
for(l->setStart();l->getValue(curr);l->next())
{
min=curr;
for(ptr->setPos(count);ptr->getValue(curr);ptr->next())
{
if(min.x>curr.x)
min=curr;
}
count++;
AET.setEdge(i,min);
}
*/
// AET y ，
for(l->setStart();l->getValue(curr);l->next())
{
l->next();
l->getValue(temp);
for(int x0=int(curr.x);x0<=temp.x;x0++)
SetPixel(hdc,x0,i,255);
// AET ymax= y，
if(curr.ymax==i)
AET.delEdge(i,curr);
if(temp.ymax==i)
AET.delEdge(i,temp);
}
// AET x
ptr->removeAll();
ptr=AET.getValue(i);
for(ptr->setStart();ptr->getValue(curr);ptr->next())
{
curr.x+=curr.increment;
AET.setEdge(i+1,curr);
}
// AET l,ptr
AET.deleteAll(i);
l->removeAll();
ptr->removeAll();
}
} 最後に、細部の問題について話します.スキャンラインが頂点と交差する場合、交点個数の計算を正しく行わなければなりません.そうしないとエラーが発生します.これは私はすでにEdgeTableクラスに含まれていて、上に2つの考え方を示しましたが、そのうちの1つは時間の問題ですべて完成したので、注釈されて、修正することに興味があります.ハ、コード共有ハ.頂点の前後にリングが接続されているため、私が使っている配列は、いくつかの特殊な状況に注意してください.もちろん、ループチェーンテーブルも使えます.
最大最小値を求める場合は、関数解を作成することもできます.ここでは、簡単にするために手動入力を採用します.針もあるので気をつけてください.ソートすると言ったかもしれませんが、ソートしていません.それは私がレコードを挿入してソートして挿入したものです.
カッコ1つで100以上のエラーが増え、1つの変数が午前1時まで振り回されたため・・・
最后の最后に、私はただ言いたいだけで、デバッグは根気と忍耐力を试す仕事です!!!
添付:コードのダウンロード:http://download.csdn.net/my