这里不仔细讲原理，只是把我写的算法发出来，跟大家分享下，如果有错误的话，还请大家告诉我，如果写的不好，也请指出来，一起讨论进步。
边表构造的算法:
(1) 首先构造一个纵向链表，链表的长度为多边形所占有的最大扫描线数，链表的每个结点，称为一个桶，则对应多边形覆盖的每一条扫描线。
(2) 将每条边的信息链入与该边最小y坐标相对的桶处。也就是说，若某条边的较低点为ymin，则该边就放在相应的扫描线中。
(3) 每条边的数据形成一个结点，内容包括:该扫描线与该的初始交点x(即较低端点的x值),1/k，以及该边的最大y值ymax如下：
x|ymin ymax 1/k next
(4) 同一桶中若干条边按x|ymin由小到在大排序，若x|ymin相等，则按照1/k由小到大排序。
改进的有效边表填充算法步骤如下:
(1) 初始化： 构造边表， AET表置空.
(2) 将第一个不空的ET表中的边与AET表合并。
(3) 删除AET表中y = ymax的边后再填充，按“下闭上升”的原则进行填充，此时就无需缩短任何边。然后进行填充，填充时设置一个布尔量b(初值为假)，令指针从有效边表中第一个结点到最后一个结点进行遍历一次。每访问一个结点，把b取反一次，若b为真，则把从当前结点的x值开始下一结点的x值结束的区间用多边形色填充。(填充时需要对x坐标进行四舍五入处理)。
(4) yi+1 = yi + 1,根据xi+1 = xi + 1 / k计算并修改AET表，同时合并ET表中y = yi+1桶的边，按次序插入到AET表中，形成新的AET表。
(5) AET表不空则转(3)，否则结束。
/*
* Date: 11/23/2010
*/
#include <GL/freeglut.h>
#include <iostream>
#include <vector>
#include <fstream>
std::ifstream cin ("polypoints.txt");
using std::vector;
using std::endl;
typedef struct _EdgeItem
{
float x;
int yMax;
float reverseK; // 1/k
_EdgeItem * next;
}EdgeItem;
vector<EdgeItem *> g_pItemVector;
typedef struct _Point
{
int x;
int y;
}Point;
typedef struct _EdgePtr
{
int nScanLine; // Current scan line
EdgeItem * pItem; // Pointer to edge item
}EdgePtr;
typedef struct _PolyPoints
{
Point * pPoint; // Pointer to points
int n; // Number of points
int yMax; // Max y of all points
int yMin; // Min y of all points
}PolyPoints;
EdgePtr * g_pEdgeList; // Edge list
EdgePtr * g_pActiveEdgeList; // Active edge list
PolyPoints g_polyPoints; // Storage for points of polygons
void inputPoints (void)
{
int n;
cin>>n;
if (n < 3)
{
std::cout<<"number of points can not be less than 3"<<endl;
exit (0);
}
g_polyPoints.n = n;
g_polyPoints.pPoint = new Point[n];
g_polyPoints.yMax = INT_MIN;
g_polyPoints.yMin = INT_MAX;
int x, y;
for (int i = 0; i < n; ++i)
{
cin>>x>>y;
g_polyPoints.pPoint[i].x = x;
g_polyPoints.pPoint[i].y = y;
if (g_polyPoints.yMax < y)
{
g_polyPoints.yMax = y;
}
if (g_polyPoints.yMin > y)
{
g_polyPoints.yMin = y;
}
}
}
// Calculate the reverse of k
float calculateReverseK (const Point & p1, const Point & p2)
{
return (float)(p2.x - p1.x) / (float)(p2.y - p1.y);
}
// Sort one scan line's list, first sort by x, if x is equal then sort by 1/k
void sortOneScanLineEdgeList (EdgePtr & edgePtr)
{
// Sort by x (select sort)
EdgeItem * pEdgeItem = edgePtr.pItem;
EdgeItem * pNext;
EdgeItem * pTmp;
while (pEdgeItem)
{
pNext = pEdgeItem->next;
pTmp = pEdgeItem;
while (pNext)
{
if (pNext->x < pTmp->x)
{
pTmp = pNext;
}
pNext = pNext->next;
}
if (pTmp != pEdgeItem)
{
// Swap x
float fTmp = pTmp->x;
pTmp->x = pEdgeItem->x;
pEdgeItem->x = fTmp;
// Swap yMax
int iTmp = pTmp->yMax;
pTmp->yMax = pEdgeItem->yMax;
pEdgeItem->yMax = iTmp;
// Swap 1/k
float kTmp = pTmp->reverseK;
pTmp->reverseK = pEdgeItem->reverseK;
pEdgeItem->reverseK = kTmp;
}
pEdgeItem = pEdgeItem->next;
}
// When the x is the same, then sort by 1/k
pEdgeItem = edgePtr.pItem;
EdgeItem * pStart = NULL;
EdgeItem * pEnd = NULL;
while (pEdgeItem)
{
// Find the start pointer and end pointer with the same x, then sort them
pEnd = pStart = pEdgeItem;
pNext = pStart->next;
while (pNext && (pNext->x == pStart->x))
{
pEnd = pNext;
pNext = pNext->next;
}
// Sort the edge list from pStart to pEnd by 1/k (select sort)
while (pStart != pEnd)
{
pTmp = pStart;
pNext = pTmp->next;
while (pNext != pEnd)
{
if (pNext->reverseK < pTmp->reverseK)
{
pTmp = pNext;
}
pNext = pNext->next;
}
// Swap values
if (pTmp != pStart)
{
// Swap x
float fTmp = pTmp->x;
pTmp->x = pStart->x;
pStart->x = fTmp;
// Swap yMax
int iTmp = pTmp->yMax;
pTmp->yMax = pStart->yMax;
pStart->yMax = iTmp;
// Swap 1/k
float kTmp = pTmp->reverseK;
pTmp->reverseK = pStart->reverseK;
pStart->reverseK = kTmp;
}
pStart = pStart->next;
} // while (pStart != pEnd)
pEdgeItem = pEnd->next;
}
}
// Construct the edge list
void constructEdgeList (void)
{
// Construct the edge list
int nScanLines = g_polyPoints.yMax - g_polyPoints.yMin + 1;
g_pEdgeList = new EdgePtr[nScanLines];
memset (g_pEdgeList, 0, sizeof (EdgePtr) * nScanLines);
Point * pPoint = g_polyPoints.pPoint;
int nScanLine = g_polyPoints.yMin;
EdgeItem * pEdgeItem = NULL;
for (int i = 0; i < nScanLines; ++i, ++ nScanLine)
{
g_pEdgeList[i].nScanLine = nScanLine;
for (int j = 0; j < g_polyPoints.n; ++j)
{
if (pPoint[j].y == nScanLine)
{
int j1 = (j+g_polyPoints.n-1) % g_polyPoints.n;
int j2 = (j+1) % g_polyPoints.n;
// if point j1's y > nScanLine then add this edge to the current scanline's list
if (pPoint[j1].y > nScanLine)
{
pEdgeItem = new EdgeItem;
pEdgeItem->reverseK = calculateReverseK (pPoint[j], pPoint[j1]);
pEdgeItem->x = (float)pPoint[j].x;
pEdgeItem->yMax = pPoint[j1].y;
// Add pEdgeItem to the scanline's list
pEdgeItem->next = g_pEdgeList[i].pItem;
g_pEdgeList[i].pItem = pEdgeItem;
}
// if point j2's y > nScanLine then add this edge to the curretn scanline's list
if (pPoint[j2].y > nScanLine)
{
pEdgeItem = new EdgeItem;
pEdgeItem->reverseK = calculateReverseK (pPoint[j], pPoint[j2]);
pEdgeItem->x = (float)pPoint[j].x;
pEdgeItem->yMax = pPoint[j2].y;
// Add pEdgeItem to the scanline's list
pEdgeItem->next = g_pEdgeList[i].pItem;
g_pEdgeList[i].pItem = pEdgeItem;
}
} // if (pPoints[j].y == nScanLine)
} // for (int j = 0; j < g_polyPoints.n; ++j)
sortOneScanLineEdgeList (g_pEdgeList[i]);
}
// Init the active edge list
g_pActiveEdgeList = new EdgePtr[nScanLines];
}
// free the memory
void destroy (void)
{
if (g_pActiveEdgeList)
{
delete g_pActiveEdgeList;
}
int nScanLines = g_polyPoints.yMax - g_polyPoints.yMin + 1;
EdgeItem * pItem, * pNext;
if (g_pEdgeList)
{
for (int i = 0; i < nScanLines; ++i)
{
if (g_pEdgeList[i].pItem)
{
pItem = g_pEdgeList[i].pItem;
pNext = pItem;
while (pItem)
{
pNext = pItem->next;
delete pItem;
pItem = pNext;
}
}
}
}
}
void init (void)
{
glClearColor (0.0f, 0.0f, 0.0f, 1.0f);
}
void activEdgeListFillPolygon (void)
{
int nScanLines = g_polyPoints.yMax - g_polyPoints.yMin + 1;
memset (g_pActiveEdgeList, 0, sizeof (EdgePtr) * nScanLines);
int nScanLine = g_polyPoints.yMin;
glBegin (GL_POINTS);
int i = 0;
for (;i < nScanLines; ++ nScanLine, ++ i)
{
if (g_pEdgeList[i].pItem)
{
g_pActiveEdgeList[i].pItem = g_pEdgeList[i].pItem;
break;
}
}
for (int j = i; j < nScanLines; ++j, ++ nScanLine)
{
if (g_pActiveEdgeList[j].pItem)
{
// Delete the edge where yMax = nScanLine
EdgeItem * pPre = NULL;
EdgeItem * pNext = g_pActiveEdgeList[j].pItem;
bool bEven = true;
while (pNext)
{
if (pNext->yMax == nScanLine)
{
if (!pPre)
{
g_pActiveEdgeList[j].pItem = pNext->next;
pNext = pNext->next;
}
else
{
pPre->next = pNext->next;
pNext = pNext->next;
}
}
else
{
bEven = !bEven;
pPre = pNext;
pNext = pNext->next;
}
} // while (pNext)
// Fill the scan line when bFill is true
bool bFill = false;
pNext = g_pActiveEdgeList[j].pItem;
while (pNext && bEven)
{
bFill = !bFill;
if (bFill)
{
int x1 = (int)(pNext->x + 0.5);
int x2 = (int)(pNext->next->x + 0.5);
//int x1 = pNext->x;
//int x2 = pNext->next->x;
for (int i = x1; i <= x2; ++i)
{
glVertex2i (i, nScanLine);
}
}
pNext = pNext->next;
} // while (pNext)
pNext = g_pActiveEdgeList[j].pItem;
int kk = j + 1;
if (kk < nScanLines)
{
while (pNext)
{
EdgeItem * pItem = new EdgeItem;
pItem->x = pNext->x + pNext->reverseK;
pItem->reverseK = pNext->reverseK;
pItem->yMax = pNext->yMax;
pItem->next = g_pActiveEdgeList[kk].pItem;
g_pActiveEdgeList[kk].pItem = pItem;
pNext = pNext->next;
g_pItemVector.push_back (pItem);
} // while (pNext)
// Add edge list to active edge list
pNext = g_pEdgeList[kk].pItem;
EdgeItem * pTemp = NULL;
while (pNext)
{
pTemp = new EdgeItem;
pTemp->reverseK = pNext->reverseK;
pTemp->x = pNext->x;
pTemp->yMax =pNext->yMax;
g_pItemVector.push_back (pTemp);
pTemp->next = g_pActiveEdgeList[kk].pItem;
g_pActiveEdgeList[kk].pItem = pTemp;
pNext = pNext->next;
}
sortOneScanLineEdgeList (g_pActiveEdgeList[kk]);
}
} // if (g_pActiveEdgeList[j].pItem)
}
glEnd ();
// 这里为了简单所以把分配的内存放在vector容器中，方便删除。:-)
vector<EdgeItem *>::iterator itr = g_pItemVector.begin (),
endItr = g_pItemVector.end ();
while (itr != endItr)
{
delete (*itr);
++ itr;
}
g_pItemVector.clear ();
}
void display (void)
{
glClear (GL_COLOR_BUFFER_BIT);
glLoadIdentity ();
glColor3f (1.0f, 0.0f, 0.0f);
// Fill a polygon
activEdgeListFillPolygon ();
glutSwapBuffers ();
}
void reshape (int w, int h)
{
glViewport (0, 0, (GLsizei) w, (GLsizei) h);
glMatrixMode (GL_PROJECTION);
glLoadIdentity ();
if (w <= h)
{
gluOrtho2D (-600.0, 600.0, -600.0 * (GLfloat) h / (GLfloat) w, 600.0 * (GLfloat) h / (GLfloat) w);
}
else
{
gluOrtho2D (-600.0 * (GLfloat) w / (GLfloat) h,600.0 * (GLfloat) w / (GLfloat) h, -600.0, 600.0);
}
glMatrixMode (GL_MODELVIEW);
glLoadIdentity ();
}
void keyboard (unsigned char key, int x, int y)
{
switch (key)
{
case 27: // 'VK_ESCAPE'
destroy ();
exit (0);
break;
default:
break;
}
}
int main (int argc, char ** argv)
{
glutInit (&argc, argv);
glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);
glutInitWindowSize (600, 600);
glutCreateWindow ("Optimized active edge list");
init ();
inputPoints ();
constructEdgeList ();
glutReshapeFunc (reshape);
glutDisplayFunc (display);
glutKeyboardFunc (keyboard);
glutMainLoop ();
destroy (); // 这里destroy并没有调用。
return 0;
}
polypoints.txt
中的示例内容如下:
7
30 120
10 70
30 10
60 50
80 10
120 90
70 80