// PolyFillView.cpp : implementation of the CPolyFillView class
//

#include "stdafx.h"
#include "PolyFill.h"

#include "PolyFillDoc.h"
#include "PolyFillView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView

IMPLEMENT_DYNCREATE(CPolyFillView, CView)

BEGIN_MESSAGE_MAP(CPolyFillView, CView)
	//{{AFX_MSG_MAP(CPolyFillView)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView construction/destruction

CPolyFillView::CPolyFillView()
{
	// TODO: add construction code here

}

CPolyFillView::~CPolyFillView()
{
}

BOOL CPolyFillView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView drawing

void CPolyFillView::OnDraw(CDC* pDC)
{
	CPolyFillDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	const int POINTNUM=6;      //多邊形點數.

/******定義結構體用于活性邊表AET和新邊表NET***********************************/
	typedef struct XET
	{
		float x;
		float dx,ymax;
		XET* next;
	}AET,NET;
/******定義點結構體point******************************************************/
	struct point
	{
		float x;
		float y;
	}polypoint[POINTNUM]={250,50,550,150,550,400,250,250,100,350,100,100};//多邊形頂點
	//mypoint[POINTNUM]={100,100,200,100,200,200,100,200};//正方形
	
/******計算最高點的y坐標(掃描到此結束)****************************************/
	int MaxY=0;
	int i;
	for(i=0;i<POINTNUM;i++)
		if(polypoint[i].y>MaxY)
			MaxY=polypoint[i].y;
		
/*******初始化AET表***********************************************************/
		AET *pAET=new AET;
		pAET->next=NULL;
		
/******初始化NET表************************************************************/
		NET *pNET[1024];
		for(i=0;i<=MaxY;i++)
		{
			pNET[i]=new NET;
			pNET[i]->next=NULL;
		}
/******掃描并建立NET表*********************************************************/
		for(i=0;i<=MaxY;i++)
		{
			for(int j=0;j<POINTNUM;j++)
				if(polypoint[j].y==i)
				{					
					if(polypoint[(j-1+POINTNUM)%POINTNUM].y>polypoint[j].y)
					{
						NET *p=new NET;
						p->x=polypoint[j].x;
						p->ymax=polypoint[(j-1+POINTNUM)%POINTNUM].y;
						p->dx=(polypoint[(j-1+POINTNUM)%POINTNUM].x-polypoint[j].x)/(polypoint[(j-1+POINTNUM)%POINTNUM].y-polypoint[j].y);
						p->next=pNET[i]->next;
						pNET[i]->next=p;
						
					}
					if(polypoint[(j+1+POINTNUM)%POINTNUM].y>polypoint[j].y)
					{
						NET *p=new NET;						
						p->x=polypoint[j].x;
						p->ymax=polypoint[(j+1+POINTNUM)%POINTNUM].y;
						p->dx=(polypoint[(j+1+POINTNUM)%POINTNUM].x-polypoint[j].x)/(polypoint[(j+1+POINTNUM)%POINTNUM].y-polypoint[j].y);
						p->next=pNET[i]->next;
						pNET[i]->next=p;
					}
				}
		}
/******建立并更新活性邊表AET*****************************************************/
		for(i=0;i<=MaxY;i++)
		{
	//計算新的交點x,更新AET********************************************************/
			NET *p=pAET->next;
			while(p)
			{
				p->x=p->x + p->dx;
				p=p->next;
			}
	//更新后新AET先排序*************************************************************/
				//斷表排序,不再開辟空間
			AET *tq=pAET;
			p=pAET->next;
			tq->next=NULL;
			while(p)
			{
				while(tq->next && p->x >= tq->next->x)
					tq=tq->next;
				NET *s=p->next;
				p->next=tq->next;
				tq->next=p;
				p=s;
				tq=pAET;
			}
	//(改進算法)先從AET表中刪除ymax==i的結點****************************************/
			AET *q=pAET;
			p=q->next;
			while(p)
			{
				if(p->ymax==i)
				{
					q->next=p->next;
					delete p;
					p=q->next;
				}
				else
				{
					q=q->next;
					p=q->next;
				}
			}
	//將NET中的新點加入AET,并用插入法按X值遞增排序**********************************/
			p=pNET[i]->next;
			q=pAET;
			while(p)
			{
				while(q->next && p->x >= q->next->x)
					q=q->next;
				NET *s=p->next;
				p->next=q->next;
				q->next=p;
				p=s;
				q=pAET;
			}
/******配對填充顏色***************************************************************/
			p=pAET->next;
			while(p && p->next)
			{
				for(float j=p->x;j<=p->next->x;j++)
					pDC->SetPixel(static_cast<int>(j),i,RGB(255,0,0));
				p=p->next->next;//考慮端點情況
			}	
		}
}

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView printing

BOOL CPolyFillView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CPolyFillView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CPolyFillView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView diagnostics

#ifdef _DEBUG
void CPolyFillView::AssertValid() const
{
	CView::AssertValid();
}

void CPolyFillView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CPolyFillDoc* CPolyFillView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CPolyFillDoc)));
	return (CPolyFillDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CPolyFillView message handlers