Lo tenía por ahí y antes de que se heche a perder...
#include
#include
#include
#include
#include
#include
#include
#include
/***********************************************/
/* Deficinicio de les estructures del programa */
/***********************************************/
typedef struct Punt { int x,y; } Punt;
typedef struct Poligon { int n,color; Punt *p; } Poligon;
typedef struct Xwindow { int x0,x1,y0,y1; } Xwindow;
typedef struct Pila
{ Punt *p;
struct Pila *anterior;
} Pila;
typedef struct Costat
{ float x, dx;
int ymax;
struct Costat *seg;
} Costat;
/***********************************************/
int llegir_poligon (char *, Poligon *);
void alliberar_poligon(Poligon *);
void llegir_comandes(char *, char *);
void inicialitzar(void);
void finalitzar(void);
int cls(void);
int mode_grafic(void);
int mode_texte(void);
/********************************************************************/
/* PROTOTIPUS DE LES FUNCIONS */
/********************************************************************/
/* Prototipus del retall Sutherland-Hogman */
void retall_SH(int,int,int,int,Poligon *);
void interseccio(Punt *,Punt *,Xwindow *,int);
int dintre(int,int,Xwindow *,int);
/* Llavor millorada (iterativament i amb una pila dinamica) */
void llavor_millorat(int,int,Poligon *,int);
void vei(int *,int,int,int);
void lineas_adjacents(int,int,int,Pila **,int);
Poligon* intercambiar(Poligon** pol);
void Finestra(Xwindow *,int);
void DibuixaPoligon(Poligon *,int);
float pendent(int,int,int,int);
/* Prototipus per a la pila que sutilitza en la llavor millorada */
Pila* Crear_node();
void Push(Pila **,Punt);
Punt Pop(Pila **);
/* Prototipus del algorisme Y-X */
void emplenat_Y_X(Poligon *);
void Y_max_min(int *max,int *min,Poligon *pol);
Costat** crear_TC(Poligon *pol,int max,int min);
void iniciar_a_null(Costat **tabla,unsigned int valor);
Costat* crear_lado(Poligon *pol,unsigned int *vertice,unsigned int *min,long
int *dy);
void guardar_TC(Costat** TC, Costat* lado,unsigned int y_min);
int alliberar_TC(Costat **taula);
void afegir_costats_LCA(Costat* lista,Costat** LCA);
Costat *ordenar_LCA(Costat* llista);
Costat* mezclar_listas(Costat* lista1,Costat* lista2);
int eliminar_lados_LCA(Costat** llista,int y_actual);
void actualizar_LCA(Costat** llista);
void pintar(Costat* lista,int posicion_y);
/* -----------------------------------------------------------------*/
/*************************************************/
/* M A I N */
/*************************************************/
void main(int argc,char *argv[])
{
if(argc!=3)
{
printf("Us: prac \n");
exit(0);
}
inicialitzar();
llegir_comandes(argv[1],argv[2]);
finalitzar();
}
void llegir_comandes(char *nom_fitxer,char *nom_poligon){
FILE *fp;
Poligon pol;
char comanda[256], comentari[256];
int x0, y0, x1, y1, color;
if ((fp=fopen(nom_fitxer,"rt"))==NULL)
{
printf("Error en obrir el fitxer de comandes\n");
getch();
finalitzar();
exit(0);
}
if (strcmp(nom_poligon,""))
{ if (!llegir_poligon(nom_poligon,&pol))
{ printf("Error en obrir el poligon \n");
getch();
finalitzar();
exit(0);
}
}
while (fscanf(fp,"%s",comanda)!=EOF)
{ /* COMANDES GENERALS */
if (strcmp(comanda,"REM")==0) fgets(comentari,256,fp);
else if (strcmp(comanda,"CLS")==0) {cls();}
else if (strcmp(comanda,"PAUSA")==0) {getch();}
else if (strcmp(comanda,"RETALLA")==0)
{ fscanf(fp,"%d",&x0);
fscanf(fp,"%d",&y0);
fscanf(fp,"%d",&x1);
fscanf(fp,"%d",&y1);
retall_SH(x0,y0,x1,y1,&pol);
}
else if (strcmp(comanda,"OMPLE")==0)
{ emplenat_Y_X(&pol);
getch();
cls();
DibuixaPoligon(&pol,4);
}
else if (strcmp(comanda,"LLAVOR")==0)
{ fscanf(fp,"%d",&x0);
fscanf(fp,"%d",&y0);
fscanf(fp,"%d",&color);
llavor_millorat(x0,y0,&pol,color);
getch();
}
/* COMANDO NO RECONOCIDO */
else {printf("comanda: %s no reconeguda\n",comanda);}
} if (strcmp(nom_poligon,"")!=0) alliberar_poligon(&pol);
}
void inicialitzar()
{ if(mode_grafic()==0)
{ printf("Error en inicialitzar");
exit(0);}
}
void finalitzar()
{ if(mode_texte()==0)
{ printf("Error en finalitzar");
exit(0);}
}
int llegir_poligon(char *nom_fitxer, Poligon *pol){
FILE *fitx_in;
int i;
pol->n=0;
pol->color=0;
pol->p=NULL;
fitx_in=fopen(nom_fitxer,"rt");
if(!fitx_in) return 0; /* No s'ha pogut obrir */
if(fscanf(fitx_in,"%d",&pol->n)!=1){
pol->n=0;
fclose(fitx_in);
return 0;
} /* No pot llegir */
/*Reserva de memoria pels punts del poligon*/
pol->p=(Punt *)malloc(sizeof(Punt)*pol->n);
if(!pol->p){
pol->n=0;
fclose(fitx_in);
return 0;
} /* No es pot aconseguir memoria */
for(i=0;in;i++) {
if(fscanf(fitx_in,"%d %d",&(pol->p[i].x),&(pol->p[i].y))!=2){
pol->n=0;
free(pol->p);
pol->p=NULL;
fclose(fitx_in);
return 0;
}
}
return 1;
}
void alliberar_poligon(Poligon *pol)
{
if( (pol->p) != NULL )
{
free(pol->p);
pol->p=NULL;
pol->color=NULL;
pol->n=0;
}
}
int cls()
{ cleardevice();
return 1;
}
int mode_grafic()
{ int gdriver=DETECT,gmode,errorcode;
initgraph(&gdriver,&gmode,"h:\\");
errorcode=graphresult();
if (errorcode!=grOk)
{ printf("Error: %s\n",grapherrormsg(errorcode));
printf("Prem una tecla per continuar");
getch();
return 0;
}
return 1;
}
int mode_texte(){
closegraph();
return 1;
}
/*********************************************************/
/* Nomes incloure codi a partir d'aquest punt */
/*********************************************************/
void retall_SH(int x0,int y0,int x1,int y1,Poligon *pol)
{
int vertex,recta,anterior,actual,last,i;
Poligon tmp;
Xwindow window1;
Punt s;
if (pol->n==0){/*Es por si nos pasa un poligono vacio*/
printf("Poligon inexistent");
exit(1);
}
tmp.p=(Punt *)malloc( sizeof(Punt) * 2 * (pol->n) );
if( (tmp.p) == NULL) {printf("RAM1 out");exit(0);}
tmp.n=0;
tmp.color=0;
window1.x0 = x0;
window1.x1 = x1;
window1.y0 = y0;
window1.y1 = y1;
DibuixaPoligon(pol,6);
Finestra(&window1,2);
for(recta=0;recta<4;recta++)
{
last=0;
s=(pol->p[(pol->n)-1]);
for(vertex=0;vertexn;vertex++)
{
anterior=dintre(s.x,s.y,&window1,recta);
actual=dintre(pol->p[vertex].x,pol->p[vertex].y,&window1,recta);
if (anterior==1 && actual==1) /*s i p a dintre => fikar p a tmp*/
{
tmp.p[last].x=pol->p[vertex].x;
tmp.p[last].y=pol->p[vertex].y;
last++;
}
else if(anterior==1 && actual==0) /*s->adintre i p->afora => interseccio
a tmp*/
{ interseccio(&s,&pol->p[vertex],&window1,recta);
tmp.p[last].x=s.x;
tmp.p[last].y=s.y;
last++;
}
else if(anterior==0 && actual==1) /*s->afora i p->adintre =>
interseccion i p a tmp*/
{
interseccio(&s,&pol->p[vertex],&window1,recta);
tmp.p[last].x=s.x;
tmp.p[last].y=s.y;
last++;
tmp.p[last].x=pol->p[vertex].x;
tmp.p[last].y=pol->p[vertex].y;
last++;
}
s=(pol->p[vertex]);
}
alliberar_poligon(pol);
if (last==0){/*Es por si al recortar da un poligono vacio*/
printf("Poligon inexistent");
exit(1);
}
pol->p=(Punt *)malloc(sizeof(Punt)*(last) );
if(pol->p==NULL) {printf("RAM2 out");exit(0);}
pol->n=last;
pol->color=tmp.color;
for(i=0;in;i++)
{ pol->p[i].x=tmp.p[i].x;
pol->p[i].y=tmp.p[i].y;
}
}
alliberar_poligon(&tmp);
DibuixaPoligon(pol,4);
getch();
cleardevice();
DibuixaPoligon(pol,4);
getch();
}
float pendent(int s0,int s1,int p0,int p1)
{
if(s0==p0) return(0);
else return( (float)(s1-p1) / (float)(s0-p0) );
}
void llavor_millorat(int x0,int y0,Poligon * pol,int color)
{
int cont_e,cont_d,color_ini;
Punt *s=NULL;
Pila *stack=NULL;
s=(Punt *)malloc(sizeof(Punt));
s->x=x0;
s->y=y0;
color_ini=getpixel(x0,y0);
DibuixaPoligon(pol,4);
setcolor(color);
Push(&stack,*s);
while(stack!=NULL)
{ *s=Pop(&stack);
cont_e=s->x; cont_d=s->x;
vei(&cont_e,s->y,color_ini,-1);
vei(&cont_d,s->y,color_ini,1);
line(cont_e,s->y,cont_d,s->y);
if( (s->y>=0) && (s->y<=getmaxy()) ){
lineas_adjacents(cont_e,cont_d,(s->y)-1,&stack,color_ini);
lineas_adjacents(cont_e,cont_d,(s->y)+1,&stack,color_ini);
}
}
free(s);
}
void lineas_adjacents(int xe,int xd,int y,Pila **stack,int color)
{
int out,axx,ayy;
Punt tmp;
out=xe;
while(out<=xd)
{ getpixel(out,y);
if( getpixel(out,y)==color )
{ vei(&out,y,color,1);
tmp.x = out;
tmp.y = y;
Push(&(*stack),tmp);
out++;
} else out++;
}
}
void Finestra(Xwindow *wind,int color)
{
setcolor(color);
rectangle(wind->x0,wind->y0,wind->x1,wind->y1);
}
void DibuixaPoligon(Poligon *poli,int color)
{
int tmp,tmp2;
tmp2=getcolor();
setcolor(color);
for(tmp=0;tmp<(poli->n)-1;tmp++)
line(poli->p[tmp].x,poli->p[tmp].y,poli->p[tmp+1].x,poli->p[tmp+1].y);
line(
poli->p[(poli->n)-1].x,poli->p[(poli->n)-1].y,poli->p[0].x,poli->p[0].y);
setcolor(tmp2);
}
int dintre (int x0,int y0,Xwindow *fines,int codig)
{ /* 0=arriba 1=derecha 2=abajo 3=izquierda */
if(codig==0)
{ if ( (y0) > (fines->y0) ) return 1;
else return 0;}
if(codig==1)
{ if ( (x0) < (fines->x1) ) return 1;
else return 0;}
if(codig==2)
{ if ( (y0) < (fines->y1) ) return 1;
else return 0;}
if(codig==3)
{ if ( (x0) > (fines->x0) ) return 1;
else return 0;}
return 0;
}
Pila* Crear_node()
{
Pila *aux=(Pila *)malloc(sizeof(Pila));
if(aux==NULL)
{ printf("No hi ha memoria RAM lliure disponible...\n");
getche();
exit(1);
}
return aux;
}
void Push(Pila **cab,Punt s)
{
Pila *aux=Crear_node();
aux->p->x=s.x;
aux->p->y=s.y;
if(cab==NULL) aux->anterior=NULL;
else
{ aux->anterior=*cab;
*cab=aux;}
}
Punt Pop(Pila **cab)
{
Pila *aux;
Punt s;
//s=(Punt *)malloc(sizeof(Punt));
if(*cab==NULL)
printf("Error: pila buida\n");
else
{ aux=*cab;
*cab=(*cab)->anterior;
s.x=aux->p->x;
s.y=aux->p->y;
free(aux);
}
return s;
}
void interseccio(Punt *s, Punt *p, Xwindow *wind,int recta)
{
float x_one=0, y_one=0;
Punt *intersec;
if(recta==0)
//calcula_int();
{ if(s->x==p->x)
{ x_one = p->x;
y_one = wind->y0;
}
else
{ x_one = p->x + (float)(wind->y0 - p->y) * pendent(s->y,s->x,p->y,p->x);
y_one = wind->y0;
}
}
if(recta==1)
{ y_one = p->y + (float)(wind->x1 - p->x) * pendent(s->x,s->y,p->x,p->y);
x_one = wind->x1;
}
if(recta==2)
{ if(s->x==p->x)
{ x_one = p->x;
y_one = wind->y1;
}
else
{ x_one = p->x + (float)(wind->y1 - p->y) * pendent(s->y,s->x,p->y,p->x);
y_one = wind->y1;
}
}
if(recta==3)
{ y_one = p->y + (float)(wind->x0 - p->x) * pendent(s->x,s->y,p->x,p->y);
x_one = wind->x0;
}
s->x=(int)(x_one+0.5);
s->y=(int)(y_one+0.5);
}
void vei(int *x,int y,int color_a,int suma)
{ while( (getpixel(*x,y)==color_a)&&((*x)<=getmaxx())&&((*x)>=0) )
{ (*x)=(*x)+suma; }
(*x)=(*x)-suma;
}
void emplenat_Y_X(Poligon * pol){
Costat **TC,*LCA=NULL,*aux;
int y_max=0,y_min=getmaxy(),i,out=0;
DibuixaPoligon(pol,1);
setcolor(14);
Y_max_min(&y_max, &y_min, pol);
TC=crear_TC(pol,y_max,y_min);
for(i=0;i {
if(TC[i])
afegir_costats_LCA(TC[i],&LCA);
/* if((i)==190){
aux=LCA;
while(aux){
printf(" %f %f %d\n",aux->x,aux->dx,aux->ymax);
aux=aux->seg;
}
printf("\n");
}*/
LCA=ordenar_LCA(LCA);
/* if((i)==190){
aux=LCA;
while(aux){
printf(" %f %f %d\n",aux->x,aux->dx,aux->ymax);
aux=aux->seg;
}
printf("\n");
}*/
pintar(LCA,i+y_min);
do{
out=eliminar_lados_LCA(&LCA,i+y_min);
}while(out);
/* if((i)==189){
aux=LCA;
while(aux){
printf(" %f %f %d\n",aux->x,aux->dx,aux->ymax);
aux=aux->seg;
}
printf("\n");
}*/
actualizar_LCA(&LCA);
}
if(!alliberar_TC(TC))
printf("Error al liberar la TC");
}
void afegir_costats_LCA(Costat* lista,Costat** LCA){
Costat *auxiliar=*LCA;
if(*LCA){/*La LCA tiene como minimo un campo*/
while(auxiliar->seg) auxiliar=auxiliar->seg;
auxiliar->seg=lista;
}else/*La LCA esta a vacia*/
*LCA=lista;
}
Costat *ordenar_LCA(Costat *llista){
Costat *llista1, *llista2;
if (!(llista->seg) || !(llista))
return llista;
llista1 = llista;
llista2 = llista1->seg->seg;
while (llista2 && llista2->seg ) {
llista1 = llista1->seg;
llista2 = llista2->seg->seg;
}
llista2 = llista1->seg;
llista1->seg = NULL;
llista1 =ordenar_LCA(llista);
llista2 =ordenar_LCA(llista2);
llista = mezclar_listas(llista1, llista2);
return llista;
}
Costat* mezclar_listas(Costat* lista1,Costat* lista2){
Costat *lista, *auxiliar;
if (lista1->x > lista2->x){
lista= lista2;
lista2 = lista2->seg;
}else{
lista = lista1;
lista1 = lista1->seg;
}
auxiliar = lista;
while (lista1 && lista2) {
if (lista1->x > lista2->x) {
auxiliar->seg = lista2;
lista2 = lista2->seg;
}else {
auxiliar->seg = lista1;
lista1 = lista1->seg;
}
auxiliar = auxiliar->seg;
}
if (lista1)
auxiliar->seg = lista1;
else if (lista2)
auxiliar->seg = lista2;
return lista;
}
int eliminar_lados_LCA(Costat** llista,int y_actual){
Costat* auxiliar=*llista,*temporal;
int salida=0;
if(auxiliar->ymax<=y_actual){
temporal=*llista;
(*llista)=(*llista)->seg;
free(temporal);
salida=1;
}else{
while(auxiliar){
if(auxiliar->seg->ymax<=y_actual){
temporal=auxiliar->seg;
if(auxiliar->seg->seg)
auxiliar->seg=auxiliar->seg->seg;
else
auxiliar->seg=NULL;
free(temporal);
salida=1;
}
auxiliar=auxiliar->seg;
}
}
return(salida);
}
void actualizar_LCA(Costat** llista){
Costat *auxiliar=*llista;
while(auxiliar){
auxiliar->x+=auxiliar->dx;
auxiliar=auxiliar->seg;
}
}
void pintar(Costat* lista,int posicion_y){
Costat *auxiliar=lista;
while(auxiliar){
line((int)(auxiliar->x+0.5),(int)(posicion_y+0.5),(int)(auxiliar->seg->x+0.5),(int)(posicion_y+0.5));
auxiliar=auxiliar->seg->seg;
}
}
void Y_max_min(int *max,int *min,Poligon *pol){
int cont;
*max=0;
*min=getmaxy();
for(cont=0;contn;cont++){
if( *max <>p[cont].y){/*Saca la y maxima del poligon*/
*max=pol->p[cont].y;
}
if(*min>pol->p[cont].y){/*Saca la y minima del poligon*/
*min=pol->p[cont].y;
}
}
}
Costat** crear_TC(Poligon *pol,int max,int min){
Costat **taula;
Costat *A,*B,*inicio;
unsigned int y_min_lado,vertex=1;
long int dyA,dyB,dyI;
taula= (Costat**) malloc(sizeof(Costat*) * (max-min));
iniciar_a_null(taula,max-min);
A=crear_lado(pol, &vertex, &y_min_lado, &dyA);
inicio=crear_lado(pol, &vertex, &y_min_lado, &dyI);
guardar_TC(taula, A, y_min_lado-min);
vertex++;
while((vertex<=pol->n) && (B=crear_lado(pol, &vertex, &y_min_lado, &dyB))){
if(dyB * dyA>=0){/*Mismo signo, sacamos un punto a B*/
if(dyB>0){/*Baja*/
y_min_lado++;
(B->x)+=(B->dx);
}else{/*Sube*/
(B->ymax)--;
}
}
if(vertex==pol->n){
if(dyB * dyI>=0){/*Mismo signo, sacamos un punto a B*/
if(dyI>0){/*Baja*/
(B->ymax)--;
}else{/*Sube*/
y_min_lado++;
(B->x)+=(B->dx);
}
}
}
guardar_TC(taula,B,y_min_lado-min);
dyA=dyB;
A=B;
vertex++;
}
if (inicio)
free(inicio);
return(taula);
}
void iniciar_a_null(Costat **tabla,unsigned int valor)
{ unsigned int cont=0;
for(cont=0;cont /*Recorremos toda la TC poniendo sus punteros a NULL*/
}
Costat* crear_lado(Poligon *pol,unsigned int *vertice,unsigned int *min,long
int *dy){
Costat *lado;
float m;
if(*verticen){/*Del 1er vertice al penultimo*/
m=pendent(pol->p[*vertice].x,pol->p[*vertice].y,pol->p[*vertice-1].x,pol->p[*vertice-1].y);
if(pol->p[*vertice-1].y!=pol->p[*vertice].y){/*Mira si es horizontal*/
lado=(Costat*) malloc(sizeof(Costat));
lado->seg=NULL;
if(m==0)
lado->dx=0;
else
lado->dx=1.0/m;
if(pol->p[*vertice-1].yp[*vertice].y){/*Baja*/
lado->x=pol->p[*vertice-1].x;
lado->ymax=pol->p[*vertice].y;
*min=pol->p[*vertice-1].y;
}else{/*Sube*/
lado->x=pol->p[*vertice].x;
lado->ymax=pol->p[*vertice-1].y;
*min=pol->p[*vertice].y;
}
*dy=(pol->p[*vertice].y)-(pol->p[*vertice-1].y);
}else{/*Es horizontal*/
(*vertice)++;
lado=crear_lado(pol,vertice,min,dy);
}
}else{/*El ultimo vertice es pasado de parametro*/
m=pendent(pol->p[0].x,pol->p[0].y,pol->p[*vertice-1].x,pol->p[*vertice-1].y);
if(pol->p[*vertice-1].y!=pol->p[0].y){/*Para saber si es horizontal*/
lado=(Costat*) malloc(sizeof(Costat));
lado->seg=NULL;
if(m==0)
lado->dx=0;
else
lado->dx=1.0/m;
if(pol->p[*vertice-1].yp[0].y){/*Baja*/
lado->x=pol->p[*vertice-1].x;
lado->ymax=pol->p[0].y;
*min=pol->p[*vertice-1].y;
}else{/*Sube*/
lado->x=pol->p[0].x;
lado->ymax=pol->p[*vertice-1].y;
*min=pol->p[0].y;
}
*dy=(pol->p[0].y)-(pol->p[*vertice-1].y);
}else lado=NULL; /*Es horizontal y es el ultimo lado*/
}
return(lado);
}
void guardar_TC(Costat** TC, Costat* lado,unsigned int y_min){
Costat* aux=NULL;
if(!(TC[y_min])){/*La lista de este punto esta vacia*/
TC[y_min]=lado;
}else{/*La lista de este punto tiene como minimo un lado*/
aux=TC[y_min];
while(aux->seg){
aux=aux->seg;
}
aux->seg=lado;
}
}
int alliberar_TC(Costat ** taula){
if (taula)
free(taula);
return(1);
}
