该算法有几个可学习的地方：
（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)(int, int));
#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)(int, int)) {
//对所有点按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, 0, sizeof(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, 0, sizeof(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(640, 480);
glutInitWindowPosition (100, 150);
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.0, 1.0, 1.0, 0.0);
glColor3f(0.0, 0.0, 0.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, 640.0, 0.0, 480.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
豪 阅读(7785)
评论(3) 编辑 收藏 引用 所属分类:
计算机图形学