#include <stdio.h>
#include <malloc.h>
#include <GL/glut.h>
#define WINDOW_HEIGHT 400
typedef struct tEdge {
int yUpper;
float xIntersect, dxPerScan;
struct tEdge * next;
} Edge;
typedef struct{
int x;
int y;
}dcPt;
int cnt=6;//عدد اضلاع البوليجون
dcPt pts[6]={{50,50},{50,100},{100,200},{280,100},{280,160},{120,100}};//多边形的顶点坐标
//dcPt pts[5]={{0,0},{50,0},{100,100},{30,80},{0,100}};//多边形的顶点坐标
/*int cnt=6;//多边形的边数
dcPt pts[6]={{20,20},{20,40},{80,60},{120,20},{80,10},{60,20}};//课本P88 5.7 */
void init(void)
{
glClearColor(0.0,1.0,1.0,0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(-200.0,200.0,-200.0,200.0);//left,right,bottom,top
}
/* Inserts edge into list in order of increasing xIntersect field. */
void insertEdge (Edge * list, Edge * edge)
{
Edge * p, * q = list;
p = q->next;
while (p != NULL) {
if (edge->xIntersect < p->xIntersect)
p = NULL;
else {
q = p;
p = p->next;
}
}
edge->next = q->next;
q->next = edge;
}
/* For an index, return y-coordinate of next nonhorizontal line */
int yNext (int k, int cnt, dcPt * pts)//下一个非水平边的y坐标
{
int j;
if ((k+1) > (cnt-1))
j = 0;
else
j = k + 1;
while (pts[k].y == pts[j].y)
if ((j+1) > (cnt-1))
j = 0;
else
j++;
return (pts[j].y);
}
/* Store lower-y coordinate and inverse slope for each edge. Adjust and store upper-y coordinate for edges that are the lower member of a monotically increasing or decreasing pair of edges */
void makeEdgeRec (dcPt lower, dcPt upper, int yComp, Edge * edge, Edge * edges[])
{
edge->dxPerScan =
(float) (upper.x - lower.x) / (upper.y - lower.y);
edge->xIntersect = lower.x;
if (upper.y < yComp) //遵循"下闭上开"原则
edge->yUpper = upper.y - 1;
else
edge->yUpper = upper.y;
insertEdge (edges[lower.y], edge);
}
void buildEdgeList (int cnt, dcPt * pts, Edge * edges[])//建立边表
{
Edge * edge;
dcPt v1, v2;
int i, yPrev = pts[cnt - 2].y;
v1.x = pts[cnt-1].x; v1.y = pts[cnt-1].y;
for (i=0; i<cnt; i++) {
v2 = pts
;
if (v1.y != v2.y) { /* nonhorizontal line */
edge = (Edge *) malloc (sizeof (Edge));
if (v1.y < v2.y) /* up-going edge */
makeEdgeRec (v1, v2, yNext (i, cnt, pts), edge, edges);//确定v1,v2边较高端点的开闭
else /* down-going edge */
makeEdgeRec (v2, v1, yPrev, edge, edges);
}
yPrev = v1.y;
v1 = v2;
}
}
void buildActiveList (int scan, Edge * active, Edge * edges[])//建立第scan条扫描线的活性边表
{
Edge * p, * q;
p = edges[scan]->next;
while (p) {
q = p->next;
insertEdge (active, p);
p = q;
}
}
void fillScan (int scan, Edge * active)
{
Edge * p1, * p2;
int i;
p1 = active->next;
while (p1) {
p2 = p1->next;
for (i=p1->xIntersect; i<p2->xIntersect; i++)
{
glBegin(GL_POINTS);
glVertex2i((int) i, scan);
glEnd();
}
p1 = p2->next;
}
glFlush();
}
void deleteAfter (Edge * q)
{
Edge * p = q->next;
q->next = p->next;
free (p);
}
/* Delete completed edges. Update 'xIntersect' field for others */
void updateActiveList (int scan, Edge * active)
{
Edge * q = active, * p = active->next;
while (p)
if (scan >= p->yUpper) {
p = p->next;
deleteAfter (q);
}
else {
p->xIntersect = p->xIntersect + p->dxPerScan;
q = p;
p = p->next;
}
}
void resortActiveList (Edge * active)
{
Edge * q, * p = active->next;
active->next = NULL;
while (p) {
q = p->next;
insertEdge (active, p);
p = q;
}
}
void scanFill (void)
{
Edge * edges[WINDOW_HEIGHT], * active;
int i, scan;
glClear(GL_COLOR_BUFFER_BIT);
for (i=0; i<WINDOW_HEIGHT; i++) {
edges
= (Edge *) malloc (sizeof (Edge));
edges
->next = NULL;
}
buildEdgeList (cnt, pts, edges);
active = (Edge *) malloc (sizeof (Edge));
active->next = NULL;
for (scan=0; scan<WINDOW_HEIGHT; scan++) {
buildActiveList (scan, active, edges);
if (active->next) {
fillScan (scan, active);
updateActiveList (scan, active);
resortActiveList (active);
}
}
/* Free edge records that have been malloc'ed ... */
}
void main(int argc,char** argv)
{
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowPosition(50,100);
glutInitWindowSize(400,400);
glutCreateWindow("扫描线多边形填充算法");
init();
glutDisplayFunc(scanFill);
glutMainLoop();
}
هذا الكود للفلينج بس انا مو فاهمنتو ممكن حدا يفهمني الكود عن طريق كومنت عليه