scan.cpp

经典算法实现

#include "Scan.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); 
	} 

}