다각형 채우기
씨앗 충전법은
다각형에서 피드 점 선택이 점이 채워지지 않으면 채워집니다.그렇지 않으면 되돌아오기;
이 점 주위의 점 (8개 점 또는 4개 점) 을 검사하고 각 점에 대해 2 를 차례로 호출합니다.
이것은 귀속으로 실현된 것으로 당연히 수공으로 창고로 실현할 수 있지만 차이가 크지 않다.매번 단일 조작이기 때문에 각 점은 주위의 8개 또는 4개의 점을 고려해야 하기 때문에 시간, 공간 비용이 매우 크다.많은 학우들이 차례대로 하는데 도형이 너무 크면 프로그램 전체가 넘쳐난다.자신이 사용한 수제 창고는 처음에 함수 내부에 커다란 Cpoint(용 MFC-) 수조를 열었는데 그 당시에 운행하자마자 붕괴되었다. 주위 학우들이 모두 만들어 냈기 때문에 자신이 비교적 조급했다. 마음을 가라앉히고 분석하지 못했다. 창고가 넘쳐흐르는 것을 알았지만 수조를 자기가 작다고 생각했는지 틀렸다고 고쳤다.나중에 수업 후에 마음을 가라앉히고 디버깅을 했는데 먼저 코드 알고리즘 부분에 문제가 있었다(수공으로 창고에 들어갈 때 틀렸으니 먼저 이 점을 채우고 창고에 넣어야 한다. 그렇지 않은 사람은 점이 중복된 창고에 들어가게 된다.).그 다음은 창고에 들어갈 때 창고 자체의 경계를 넘지 않는 문제를 고려하지 않았기 때문에 제때에 수조가 작게 열렸지만 프로그램은 수조가 경계를 넘어서 붕괴되었다.마지막으로, 프로그램 창고의 제한으로 인해 수조는 일정한 크기까지만 열 수 있으며, 이 수조를 전역 변수로 삼았다.최근에 번역 원리를 배웠는데 학우들의 말에 의하면 전체 변수는 정적 구역에 놓고 창고에 넣지 않기 때문에 매우 크게 열 수 있다고 한다.그리고 마지막에 만들었어요.효과가 매우 나쁘다.일단 수조는 정말 크게 틀어야 돼요.그 다음은 효율이 매우 낮아서 충전의 상태를 뚜렷하게 볼 수 있다. 창고(귀속)를 사용하기 때문에 먼저 한 방향으로 충전한다. 이렇게 하면 이 방향으로 충전이 끝난 후에 창고가 나가는 문제(귀속 귀환)가 존재한다. 이때 이미지가 채워지지 않아서 결과적으로 충전이 두 걸음이 된 것 같다. 먼저 반을 채우고 시간이 지나면 반을 채워야 한다.물론 책에서 최적화 방법은 2를 고치는 것이다. 매번 이 점만 채우지 않고 다각형 내의 십자형 궤적을 채우는 것이다.이렇게 하면 창고의 깊이와 그리는 시간을 줄일 수 있을 것이다. 그러나 자신은 하지 않았다.
이 알고리즘은 실현할 때 경계를 GetPixel을 통해 이 점의 픽셀 색을 얻은 다음에 경계인지 아닌지를 확인하기 때문에 먼저 채우기 전에 경계를 그려야 한다. 그 다음에 피드 점 선택은 구역 내의 한 점을 클릭하여 얻을 수 있기 때문에 이런 방법은 상호작용식 그림에 적합하다. 그림의'채우기'도구는 이렇게 해야 한다고 생각한다.
질서정연한 변표법:
질서 있는 변표의 기본 사상은 모든 스캐닝 선과 다각형의 변의 교점을 구한 다음에 교점 사이의 구역을 선을 그리면 된다는 것이다.
그래서 우리는 우선 이 다각형의 각 변의 정보를 알아야 한다. 이것은 정점을 통해 구성될 수 있다.후방 처리의 편의를 위해서 우리는 모든 변의 y를 점차적으로 증가시켰다. 즉, 시작점의 y가 종점의 y값보다 작다는 것이다.그리고 우리는 다시 가장자리를 정렬하고 기점 y값이 작으면 크고, 기점 y값이 같을 때 종점 y값이 작으면 큰 순서로 정렬한다.이러한 처리를 통해 우리는 스캐닝 라인의 범위 (즉 첫 번째 테이블의 시작점 y값에서 마지막 끝점 y값까지) 를 알 수 있다.
이어서 핵심 부분으로 각 스캐너와 다각형의 교점을 구한다.각 스캐너는 다각형의 각 모서리와 교차하지 않고 이러한 규칙이 존재하기 때문에 항상 각 정점에서 한 스캐너는 하나 이상의 모서리와 교차하거나 하나 이상의 모서리와 더 이상 교차하지 않는다.즉, 스캐너 y 값이 정점의 y 값과 같을 때 우리는 스캐너 선과 다각형 교점의 개수에 변화가 생겼음을 고려해야 한다. (확실한 것은 교점이 증가하면 이 교점이 바로 이 교점이다.) 나머지 시간에 우리는 이전 스캐너와 다각형의 교점 상황에 따라간단하게 이 스캐너와 다각형의 상황을 얻어낼 수 있다. (확정적으로 말하면 다각형 변이 직선이기 때문에 우리가 y값에서 작은 것부터 큰 것까지 스캐닝을 한다면 이 스캐너는 한 변의 교점과 이전 스캐너와 이 변의 교점과 이런 관계가 존재한다. xcur=(xpre+1/k), k는 직선 경사율이다.구체적인 방법은 다음과 같다.
각 변의 경사율의 역수를 구하여 변의 데이터 구조에 저장한다새 모서리 테이블을 만듭니다. 즉, 각 정점(정확하게 말하면 각 모서리의 시작점입니다. 종점에 새로운 모서리가 있을 수 없기 때문입니다)에 대해 이 위치의 스캐너와 다각형이 새로 추가된 교차점이 있는 모서리를 구합니다.
질서정연한 변표를 세우다.구축 struct Node
{
float x ;
float deltaX ;
int yMax ;
struct Node * next ;
}의 모서리 테이블 항목입니다. 이 항목은 스캐너와 다각형 모서리의 교차점을 나타냅니다.
세우다
struct AET
{
int y ;
struct Node * nodeList ;
}의 수조는 스캐너선과 이 다각형의 모든 교점입니다.
이 교차점을 구축할 때 먼저 새 사이드 테이블에 이 스캐너가 새 사이드에 추가되었는지 확인하고, 만약 있다면, 새 사이드와 스캐너 라인의 교차점을 노드 노드로 구성하여 x가 점차적으로 증가하는 순서에 따라nodeList에 추가합니다. (여기에서 주의하십시오. 이 교차점은 바로 사이드의 정점이며, 같은 교차점은 두 번 추가됩니다. [곰곰이 생각해 보면 그럴 것입니다! 이렇게 하면 질서정연하게 선을 그리면서 겪는 정점 문제도 해결됩니다.]그리고 이전 스캐너 라인의 모든 node를 보십시오. 현재 y>yMax라면 z는 이 node를 포기합니다. 그렇지 않으면 새로운 node를 구축하여 x=x+deltaX를 nodeList에 추가해야 합니다.
구축된 AET에 따라 각 스캐너(즉 AET의 각 항목)에 대해 매번 두 개의 node를 꺼내서 (node1.x, y)에서 (node2.x, y)까지의 선을 그립니다.여기에 문제가 하나 존재한다. 만약에 다각형의 변이 수평이라면 이 스캐너와 이 변은 너무 많은 교점이 있을 것이다. 이렇게 하면 그림 효율이 너무 낮다. (그러나 이전의 논리에 따라 처리하면 문제가 생기지 않을 것 같다. 실험이 없으면 건장성이 매우 좋지 않다!!)우리는 반드시 점으로 변방을 구축할 때 이런 상황을 처리해야 한다.두 개의 y 값이 같으면 이 모서리(채우기)를 직접 그리고 이 모서리를 모서리의 데이터 구조에 넣지 않습니다.
참고했어http://blog.csdn.net/orbit/article/details/7368996문장더 분명하게 말해야 하는데...
마지막으로 코드를 붙여주세요.
1. 피드 채우기:
#define MAX_POINTS 1366*768/2CPoint stack[MAX_POINTS] ;
int top = 0 ;
stack[top].x = cp.x ;
stack[top].y = cp.y ;
pDC->SetPixel(cp,RGB(0,0,0)) ;
top++ ;
while(top != 0)
{
top-- ;
if(top >= MAX_POINTS -4)
{
MessageBox(_T("stack full")) ;
return ;
}
// cprintf("%d
",top) ;
cp.x = stack[top].x ;
cp.y = stack[top].y ;
//get the points
CPoint lp , rp , up ,bp ;
lp.x = cp.x -1 ;
lp.y = cp.y ;
rp.x = cp.x + 1 ;
rp.y = cp.y ;
up.x = cp.x ;
up.y = cp.y + 1 ;
bp.x = cp.x ;
bp.y = cp.y -1 ;
//has been filled ?
if(pDC->GetPixel(lp) != RGB(0,0,0))
{
pDC->SetPixel(lp,RGB(0,0,0)) ;
stack[top].x = lp.x ;
stack[top].y = lp.y ;
top++ ;
}
if(pDC->GetPixel(rp) != RGB(0,0,0))
{
pDC->SetPixel(rp,RGB(0,0,0)) ;
stack[top].x = rp.x ;
stack[top].y = rp.y ;
top++ ;
}
if(pDC->GetPixel(up) != RGB(0,0,0))
{
pDC->SetPixel(up,RGB(0,0,0)) ;
stack[top].x = up.x ;
stack[top].y = up.y ;
top++ ;
}
if(pDC->GetPixel(bp) != RGB(0,0,0))
{
pDC->SetPixel(bp,RGB(0,0,0)) ;
stack[top].x = bp.x ;
stack[top].y = bp.y ;
top++ ;
}
} 2. 정렬 모서리 테이블:
데이터 구조 정의
struct NETNode
{
int edgeOrder ;
struct NETNode * next ;
} ;
struct NETItem
{
int y ;
struct NETNode * nodeList ;
} ;
struct NET
{
vector<NETItem> data ;
int pos ;
} ;
struct AETNode
{
float x ;
float deltaX ;
int yMax ;
struct AETNode * next ;
} ;
struct AETItem
{
int y ;
struct AETNode * nodeList ;
} ;
class Edge
{
public :
CPoint startPnt ;
CPoint endPnt ;
float slopeReciprocal ;
bool hasAdded ;
Edge(CPoint pnt1 , CPoint pnt2 )
{
//make the point's 'y' increase
if(pnt1.y < pnt2.y)
{
startPnt.x = pnt1.x ;
startPnt.y = pnt1.y ;
endPnt.x = pnt2.x ;
endPnt.y = pnt2.y ;
}
else if(pnt1.y > pnt2.y)
{
startPnt.x = pnt2.x ;
startPnt.y = pnt2.y ;
endPnt.x = pnt1.x ;
endPnt.y = pnt1.y ;
}
else
{
return ;
}
slopeReciprocal = (static_cast<float>((endPnt.x - startPnt.x)))/(endPnt.y - startPnt.y ) ;
hasAdded = false ;
}
} ;알고리즘, 엉망진창으로 썼는데 C++의 데이터 구조는 아직 잘 쓰이지 않는다. 이전에 표준 라이브러리를 너무 적게 썼기 때문에 진정으로 물건을 쓸 때 스스로 기초적인 데이터 구조를 만드는 데 그렇게 많은 신경을 썼는지 아니면 표준으로 하는 것이 좋은지 느꼈다.
void CGraphics_1View::fillInner()
{
//first ,build the edges
vector<Edge> edges ;
for(int i = 0 ; i < pointsLen ; i++)
{
int cur = i ;
int nxt = (i+1)%pointsLen ;
if(points[cur].y != points[nxt].y)
{
Edge tmpEdge(points[cur], points[nxt]) ;
edges.push_back(tmpEdge) ;
}
else
{
//if the edge is horizontal , we don't add it to the edge table , we just draw it immediately
CDC * pDC = GetWindowDC() ;
for(int k = points[cur].x ; k < points[nxt].x ; k++)
{
pDC->SetPixel(k,points[cur].y,RGB(0,0,0)) ;
}
}
}
sort(edges.begin(),edges.end(),sortFn) ;
vector<Edge>::iterator it ;
for(it = edges.begin() ; it != edges.end() ; ++it)
{
cprintf("%d,%d,%d,%d
",it->startPnt.x,it->startPnt.y,it->endPnt.x , it->endPnt.y) ;
}
// new edge table node
NET net ;
net.pos = 0 ;
for(i = 0 ; i < edges.size() ; i++)
{
if(edges.at(i).hasAdded == true)
{
continue ;
}
int y = edges.at(i).startPnt.y ;
//by this ,we can ensure the y is the only and increase
//build the NETItem
NETItem newItem ;
newItem.y = y ;
NETNode * newNode = new NETNode ;
newNode->edgeOrder = i ;
newNode->next = NULL ;
newItem.nodeList = newNode ;
edges.at(i).hasAdded = true ;
//find the
for(int j = 0 ; j < edges.size() ; j++)
{
if(edges.at(j).hasAdded)
{
continue ;
}
if(y>= edges.at(j).startPnt.y && y <= edges.at(i).endPnt.y)
{
newNode = new NETNode ;
newNode->edgeOrder = j ;
newNode->next = newItem.nodeList ;
newItem.nodeList = newNode ;
edges.at(j).hasAdded = true ;
}
}
net.data.push_back(newItem) ;
}
for(i = 0 ; i < net.data.size() ;i++)
{
cprintf("%d\t",net.data[i].y) ;
NETNode * pos = net.data[i].nodeList ;
while(pos != NULL)
{
cprintf("%d,",pos->edgeOrder) ;
pos = pos->next ;
}
cprintf("
") ;
}
//build active edge table
int yMax = edges.at(edges.size()-1).endPnt.y ;
int yMin = edges.at(0).startPnt.y ;
int aetSize = yMax - yMin + 1 ;
vector<AETItem> aet(aetSize) ;
for(i = 0 ; i < aetSize ; i++)
{
aet[i].y = i + yMin ;
aet[i].nodeList = NULL ;
if(net.pos < net.data.size() && aet[i].y == net.data[net.pos].y)
{
//this line has new edge
//add it
NETNode * pos = net.data[net.pos].nodeList ;
while(pos != NULL)
{
AETNode * newNode = new AETNode ;
int edgeOrder = pos->edgeOrder ;
newNode->yMax = edges[edgeOrder].endPnt.y ;
newNode->x = edges[edgeOrder].startPnt.x ;
newNode->deltaX = edges[edgeOrder].slopeReciprocal ;
AETNode ** aetPos = & aet[i].nodeList ;
if(*aetPos == NULL)
{
newNode->next = NULL ;
aet[i].nodeList = newNode ;
}
else
{
while( (*aetPos) != NULL)
{
if(newNode->x <= (*aetPos)->x)
{
newNode->next = (*aetPos) ;
(*aetPos) = newNode ;
break ;
}
aetPos = &((*aetPos)->next) ;
}
if(*aetPos == NULL)
{
newNode->next = NULL ;
(*aetPos) = newNode ;
}
}
pos = pos->next ;
}
net.pos++ ;
}
//get the scan line and the polygen edge's crossover point by using the prevoius item
if(i != 0)
{
AETNode * preNodePos = aet[i-1].nodeList ;
while(preNodePos != NULL)
{
//if it is y > yMax , it will occure the white line , does not know the reason
if(aet[i].y >= preNodePos->yMax)
{
preNodePos = preNodePos->next ;
}
else
{
AETNode * newNode = new AETNode ;
newNode->deltaX = preNodePos->deltaX ;
newNode->x = preNodePos->x + preNodePos->deltaX ;
newNode->next = NULL ;
newNode->yMax = preNodePos->yMax ;
//insert
AETNode ** pForIns = & aet[i].nodeList ;
while(*pForIns != NULL)
{
if(newNode->x <= (*pForIns)->x)
{
newNode->next = *pForIns ;
(*pForIns) = newNode ;
break ;
}
pForIns = &((*pForIns)->next) ;
}
if(*pForIns == NULL)
{
(*pForIns) = newNode ;
}
preNodePos = preNodePos->next ;
}
}
}
}
//draw
CDC * pDC = GetWindowDC() ;
for(i = 0 ; i< aet.size() ; i++)
{
AETNode * pForDraw = aet[i].nodeList ;
while(pForDraw != NULL)
{
int x1 = static_cast<int>(pForDraw->x) ;
if(pForDraw->next != NULL)
pForDraw = pForDraw->next ;
int x2 = (int)pForDraw->x ;
for(int k = x1 ;k < x2 ; k++)
{
pDC->SetPixel(k,aet[i].y,RGB(0,0,0)) ;
}
if(pForDraw != NULL)
pForDraw = pForDraw->next ;
}
}
여기서 sort는 cmp 함수를 호출합니다.
bool sortFn(Edge e1 , Edge e2)
{
return e1.startPnt.y < e2.startPnt.y || e1.endPnt.y < e2.endPnt.y ;
}
좋은 웹페이지 즐겨찾기
