随笔 - 87  文章 - 279  trackbacks - 0
<2007年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 191355
  • 排名 - 117

最新评论

阅读排行榜

评论排行榜

该算法有几个可学习的地方:
(1)正负1思想
(2)对边界条件的处理
(3)数据结构的选择

code:
sweep.h

#ifndef SWEEP_H
#define SWEEP_H

struct Edge {
    
int nxty;
    
int curx;
    
int dx, dy; // 所在扫描线的增量
    Edge *nxt;
}
;

//扫描线主算法
void sweep(int p[][2], int n, void (*setPixel)(intint));
#endif
sweep.cpp
#include "sweep.h"
#include 
<algorithm>
using namespace std;

const int MAXN = 1024;

int cp[MAXN][2], n;
inline 
bool cmp(int i, int j) {
    
return cp[i][1< cp[j][1|| (cp[i][1== cp[j][1&& cp[i][0< cp[j][0]);
}



Edge 
* e[MAXN], *h, *ph, *data;
void insert(int ly, int px, int ind) {
    
int y1,y2,y, nxt, pre, flag=0;

    nxt 
= (ind + 1% n; pre = (ind - 1 + n) % n;
    y 
= cp[ind][1]; y1 = cp[nxt][1]; y2 = cp[pre][1];
    
if (y1 > y2) swap(y1, y2);
    
if (y1 < y && y < y2) {
        
//需缩短一个单位
        flag = 1;
    }


    h 
= e[ly]; ph=NULL;
    
while (h) {
        
if (h->dy > cp[ind][1|| (h->dy == cp[ind][1&& h->dx > cp[ind][0])) break;
        ph 
= h;
        h 
= h->nxt;
    }

    
    data 
= new Edge;
    data
->curx = px; data->nxty = cp[ind][1]; data->dx = cp[ind][0- px; data->dy = cp[ind][1- ly; data->nxt = NULL;
    
if (flag) data->nxty--;

    
if (ph) {    
        data
->nxt = ph->nxt;
        ph
->nxt = data;
    }
 else {
        data
->nxt = e[ly];
        e[ly] 
= data;
    }

    

}


int ex[MAXN][MAXN], ne[MAXN];
inline 
int abs(int a) {
    
return a > 0 ? a : -a;
}

void makepoint(int line, Edge *h) {
    
int dx = h->dx, dy = h->dy, cnt=0;
    
int x, y, flag=1;
    
if ((h->dx)*(h->dy)<0) flag=0;
    
for (y=line, x=h->curx; y<=h->nxty; y++{
        ex[y][ne[y]
++= x;
        cnt 
+= 2*abs(dx);
        
while (cnt>=2*abs(dy)) {
            cnt 
-= 2*abs(dy);
            
if (flag) x++;
            
else x--;
        }

    }

}


void sweep(int p[][2], int nn, void (*setPixel)(intint)) {
    
//对所有点按y坐标递增排序,y坐标相等的按x坐标递增排序
    n = nn;
    
int i, j, k, ind, nxt, pre;
    
int *num = new int[n];    //点索引;
    for (i=0; i<n; i++) num[i] = i;
    memcpy(cp, p, 
sizeof(cp));
    sort(num, num
+n, cmp);

    
//建立有序边表
    memset(e, 0sizeof(e));
    
for (i=0; i<n; i++{
        ind 
= num[i]; 
        nxt 
= (ind + 1% n; 
        pre 
= (ind - 1 + n) % n;
        
if (p[nxt][1> p[ind][1]) insert(p[ind][1], p[ind][0], nxt);
        
if (p[pre][1> p[ind][1]) insert(p[ind][1], p[ind][0], pre);
    }


    
//处理active edge list
    memset(ne, 0sizeof(ne));
    
for (i=0; i<MAXN; i++{
        h 
= e[i]; ph = NULL;

        
while (h) {
            makepoint(i, h);
            h 
= h->nxt;
        }

        sort(ex[i], ex[i]
+ne[i]);
        
for (j=0; j<ne[i]; j+=2
            
for (k=ex[i][j]; k<=ex[i][j+1]; k++)
                setPixel(k,i);
    }


}
sweepline.cpp
#include <stdlib.h>
#include 
<stdio.h>
#include 
<GL/glut.h>
#include 
"sweep.h"

void myInit();

void setPixel(int x, int y);

void myDisplay();

int main(int argc, char **argv) {
    glutInit(
&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE
|GLUT_RGB);
    glutInitWindowSize(
640480);
    glutInitWindowPosition (
100150);
    glutCreateWindow(
"SweepLine");
    glutDisplayFunc(myDisplay);
    myInit();
    glutMainLoop();
    
return 0;
}



void setPixel(int x, int y) {
    glBegin(GL_POINTS);
    glVertex2i(x, y);
    glEnd();
}


void myInit() {
    glClearColor(
1.01.01.00.0);
    glColor3f(
0.00.00.0);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluOrtho2D(
0.0640.00.0480.0);
}



void myDisplay() {
    
int i, j;
    glClear(GL_COLOR_BUFFER_BIT);
    
int p[5][2];
    p[
0][0= 100; p[0][1= 300;
    p[
1][0= 200; p[1][1= 50;
    p[
2][0= 300; p[2][1= 100;
    p[
3][0= 400; p[3][1= 0;
    p[
4][0= 350; p[4][1= 470;
    sweep(p, 
5, setPixel);
    glFlush();
}

posted on 2007-10-20 22:33 阅读(6967) 评论(3)  编辑 收藏 引用 所属分类: 计算机图形学

FeedBack:
# re: 扫描线-通用多边形填充算法 2007-12-15 14:32 wa
谢谢哦,真的很感谢!我一直很想学好CG的,但是不大熟悉这些资源,耽误了很多的时间,现在有点时间不等人大的感觉!  回复  更多评论
  
# re: 扫描线-通用多边形填充算法 2008-10-15 21:13 
奇怪了,这个程序,为什么我在C_FREE上调不通呢。
有什么需要我注意的吗?  回复  更多评论
  
# re: 扫描线-通用多边形填充算法 2009-04-03 12:17 组织者
以后写算法建议用纯C写。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理