13 # define EARLY_UNLINK 1
16 #define LABEL_DELTA 16384
17 /* step to increase size of labels array */
18 #define LABEL_INIT_SIZE 65536
19 /* initial size of label array */
20 int *labels, last, limit;
23 EPP *epp;/*global pointer to input file for coordinate info access*/
29 { labels=realloc(labels,(limit+=LABEL_DELTA)*sizeof(int));
31 { fprintf(stderr,"Cannot perform realloc()\n");
37 void *check_alloc(size_t size)
39 if (!(tmp=malloc(size)))
40 { fprintf(stderr,"Cannot perform malloc()\n");
45 unsigned short *alloc_buffer(int width,int *height)
46 {int i=0,l=0,h=megabytes*524288/width;
47 unsigned short *buffer;
48 buffer=malloc(h*width*sizeof(short));
52 buffer=malloc(i*width*sizeof(short));
62 buffer=malloc(i*width*sizeof(short));
70 { labels=check_alloc(LABEL_INIT_SIZE*sizeof(int));
71 limit=LABEL_INIT_SIZE;
75 int check_line(int this,int other)
77 return other==line_color;
79 int check_border(int this,int other)
84 int base_color(int color)
85 { while (labels[color]<0) color=-labels[color];
88 void report_dup(int row,int col,int class1,int class2)
89 { static int dup_count=0;
90 fprintf(stderr,"\r Duplicate label %d:",++dup_count);
92 printf("%10g %10g %6d %6d\n",
93 alt_xc(epp,col),alt_yc(epp,row),class1,class2);
96 int merge_colors(int color1,int color2,int row,int col)
97 { color1=base_color(color1);
98 color2=base_color(color2);
99 if (labels[color1]&&labels[color2]&&labels[color1]!=labels[color2])
100 report_dup(row,col,labels[color1],labels[color2]);
104 {labels[color2]=-color1;return color1;}
106 {labels[color1]=-color2;return color2;}
109 int (*is_border)(int this,int other)=check_line;
111 int first_pass(EPP *fin,EPP *temp1,EPP *temp2, int eight_way,int do_labels)
112 { int nrows,ncol,seqrow,row,col;
113 unsigned short int *in_rp1,*in_rp2;
114 long int *out_rp1,*out_rp2;
116 unsigned short int *inp1,*inp2;
119 /* set up global pointer */
121 /* calculate file sizes */
122 ncol=fin->lc-fin->fc;
123 nrows=fin->lr-fin->fr;
124 /* Allocating row buffers */
125 in_rp1=check_alloc((ncol+2)*sizeof(short int));
126 in_rp2=check_alloc((ncol+2)*sizeof(short int));
127 out_rp1=check_alloc((ncol+2)*sizeof(long int));
128 out_rp2=check_alloc((ncol+2)*sizeof(long int));
129 /* initiliazing row buffers */
130 for(i=0,cc=out_rp2,inp2=in_rp2;i<ncol+2;*(cc++)=0,*(inp2++)=line_color,i++);
131 out_rp1[0]=0;out_rp1[ncol+1]=0;
132 *in_rp1=in_rp1[ncol+1]=line_color;
134 for (seqrow=1,row=fin->fr;row<fin->lr;seqrow++,row++)
135 { /*swap output row buffers*/
136 cc=out_rp1;out_rp1=out_rp2;out_rp2=cc;
137 /* swap input row buffers*/
138 inp1=in_rp1; in_rp1=in_rp2; in_rp2=inp1;
139 /*get input file row */
140 memcpy(in_rp2+1,epp_getline(fin,fin->fc,row),ncol*sizeof(short int));
141 /* position output files */
142 epp_put(temp1,fin->fc,row,1);
143 epp_put(temp2,fin->fc,row,1);
144 /* handle progress indicator */
147 if ((exitcode=EndLineProc(row,seqrow,nrows)))
151 for(j=epp->fc,col=1,inp1=in_rp1+1,inp2=in_rp2+1,cc=out_rp2+1;
152 col<=ncol;col++,inp1++,inp2++,cc++,j++)
153 { if (*inp2==line_color) *cc=0;
155 /*check for labels with id!=0&&id!=line_color */
156 { if (do_labels&&*inp2)
157 { int* lptr=labels+base_color(*inp2);
158 if (*lptr) report_dup(row,col,*inp2,*lptr);
161 if (is_border(*inp2,*inp1)) color=0; else color= out_rp1[col];
162 if (!is_border(*inp2,*(inp2-1)))
165 color=merge_colors(*(cc-1),color,row,j);
169 { if (!is_border(*inp2,*(inp1-1)))
170 if (color) color=merge_colors(out_rp1[col-1],color,row,j);
171 else color=out_rp1[col-1];
172 if (!is_border(*inp2,*(inp1+1)))
173 if (color) color=merge_colors(out_rp1[col+1],color,row,j);
174 else color=out_rp1[col+1];
178 unsigned short int *this,*next;
179 /* no color found. Trying to get it from some right cell*/
180 for (this=inp2,next=this+1,j=col;j<=ncol&&
181 is_border(*this,in_rp1[j])
182 &&!is_border(*this,*next);this++,next++,j++);
183 if (j<=ncol&&!is_border(*this,in_rp1[j])) color=out_rp1[j];
185 { color=new_label();}
186 } else color=base_color(color);
189 } /* end of inner loop */
191 for (i=0,inp1=temp1->row,inp2=temp2->row,cc=out_rp2+1;
192 i<ncol;i++,cc++,inp1++,inp2++)
193 { *inp1=*cc & 0xFFFF;
211 /* search array of labels to actual numer of clusters */
212 /* case where there are no label points */
215 for (i=1;i<=last;i++)
218 labels[i]=labels[j]=c++;
224 { fprintf(stderr,"Count of contours exceedes EPPL limit of 65535\n");
228 printf("Temporary numbers used %d\nContours found %ld\n Output file will be %d-bit\n",
234 int remap_hard_labels()
235 /* link temporary numbers with actual labels .
236 mark each temporary contour with no labels by unique number greater than
239 returns count of classes in resulting file.
240 Side effects: label[i] contain value to fill temporary contour i;
241 Create16bit is set appropriate.
243 { long int i,j,c=65536,unlabelled=0,max=0;
247 { labels[j]=labels[i]=c++;unlabelled++;
252 if (labels[j]>max) max=labels[j];
256 printf("Temporary numbers used %d\nMaximal class is %ld\nUnlabelled polygons found %ld\n",
257 last,max,unlabelled);
260 int second_pass(EPP *temp1,EPP *temp2,EPP *fout)
261 /* creates final clusterized file in case, if no fill rules given
262 file is not from rasterize */
263 {int i,row,col,nrows,fc,secondc,exitcode;
264 unsigned short *src1,*src2,*dest;
265 nrows=fout->lr-fout->fr;
266 secondc=(fc=fout->fc)+1;
267 for (i=1,row=fout->fr;row<fout->lr;i++,row++)
269 if ((exitcode=EndLineProc(row,i,nrows))) return exitcode;
271 labels[epp_get(temp1,fc,row)|(epp_get(temp2,fc,row)<<16)]);
272 for (col=secondc,src1=epp_getline(temp1,secondc,row),
273 src2=epp_getline(temp2,secondc,row),
276 *(dest++)=labels[*(src1++)|(*(src2++)<<16)],col++);
282 void report_unlabelled(int row,int col,int class,int offsite)
284 printf("%g %g unlabelled\n",alt_xc(epp,col),alt_yc(epp,row));
285 for (i=1,lbl=labels+1;i<=last;i++,lbl++)
286 if (*lbl==class) *lbl=offsite;
288 void fill_and_save(EPP *fout,EPP *fill, unsigned short *rp1,
289 unsigned short *rp2, unsigned short *rp3, int row)
290 {int col=fout->fc,value;
291 for (rp1++,rp2++,rp3++;col<fout->lc;rp1++,rp2++,rp3++,col++)
294 switch (epp_get(fill,row,col))
295 { case 1:value=*rp1;break;
296 case 2:value=*(rp2+1);break;
297 case 3:value=*(rp1+1);break;
298 case 4:value=*(rp3);break;
299 case 6:value=*(rp3+1);break;
300 case 8:value=*(rp2-1);break;
301 case 9:value=*(rp1-1);break;
302 case 12: value=*(rp3-1);break;
304 epp_put(fout,col,row,value?value:fout->offsite);
307 int second_pass_fill(EPP *temp1,EPP *temp2,EPP *fill,EPP *fout)
308 {unsigned short *rp1,*rp2,*rp3,*rtmp;
309 int i,row,col,ncols,nrows,fc,secondc,exitcode,value;
310 unsigned short *src1,*src2,*dest;
311 nrows=fout->lr-fout->fr;
312 secondc=(fc=fout->fc)+1;
313 ncols=fout->lc-fout->fc+2;
314 /*set global pointer */
316 /* allocate buffers */
317 rp1=check_alloc(ncols*sizeof(short int));
318 rp2=check_alloc(ncols*sizeof(short int));
319 rp3=check_alloc(ncols*sizeof(short int));
320 for(i=0,rtmp=rp2;i<ncols;i++,*(rp1++)=fout->offsite);
321 *rp1=rp1[ncols-1]=*rp3=rp3[ncols-1]=fout->offsite;
322 for (row=fout->fr,i=1;row<fout->lr;i++,row++)
324 if ((exitcode=EndLineProc(row,i,nrows))) return exitcode;
327 src1=epp_getline(temp1,fc,row),
328 src2=epp_getline(temp2,fc,row);
330 dest++,src1++,src2++,col++)
331 {value=labels[*src1|(*src2<<16)];
333 report_unlabelled(row,col,value,*dest=fout->offsite);
334 else *dest=value==65534?0:value;
336 if (row>fout->fr) fill_and_save(fout,fill,rp1,rp2,rp3,row-1);
338 rp1=rp2; rp2=rp3; rp3=rtmp;
340 fill_and_save(fout,fill,rp1,rp2,rp3,fout->lc-1);
346 /* rasterize should fill this variables near its beginning */
347 int right_border, bottom_border, nrow, ncol,half_vert,half_horiz;
349 { return (((unsigned long)(x+32767))*ncol)/right_border;
351 int dgt2absrow(int y)
353 return (((unsigned long)(32767-y))*nrow)/bottom_border+1;
355 int absrow2dgt(int row)
357 return 32767-((long)((unsigned long)(row-1)*bottom_border/nrow));
359 #define CELL(buf,row,col) *(buf+row*width+col)
360 #define row2dgt(row) (absrow2dgt(row+firstrow))
361 #define dgt2row(y) (dgt2absrow(y)-firstrow)
363 int save_buffer(EPP *epp,unsigned short *buf,int firstrow,int lastrow,int width)
364 {unsigned short *b; int row;
365 for (row=firstrow,b=buf;row<lastrow;row++,b+=width)
367 epp_put(epp,1,row,epp->offsite);
368 memcpy(epp->row,b,width*sizeof(short));
371 if ((*EndLineProc)(row,row,nrow)) return -1;
380 int rasterize(DGT *dgt,EPP *fout,EPP *fill,int modulo,int divisor)
381 {unsigned short *buf,*fillbuf=NULL;
382 int width,height,firstrow,lastrow,fry,lry;
383 width=fout->lc-fout->fc;
385 nrow=fout->lr-fout->fr;
386 right_border=(fout->XRight-fout->XLeft)/(dgt->XRight-dgt->XLeft)*65535;
387 bottom_border=(fout->YBottom-fout->YTop)/(dgt->YBottom-dgt->YTop)*65535;
388 half_horiz=right_border>>1;
389 half_vert=bottom_border>>1;
390 buf=alloc_buffer(width,&height);
394 fillbuf=buf+height*width;
397 lastrow=fout->fr+height;
399 if (lastrow>fout->lc) lastrow=fout->lc;
400 memset(buf,0,width*height*sizeof(short));
401 if (fill) memset(fillbuf,0,width*height*sizeof(short));
403 fry=absrow2dgt(firstrow);
404 lry=absrow2dgt(lastrow);
405 while (!dgt_eof(dgt))
406 { if (dgt_is_point(dgt))
408 if ((y=dgt_pointy(dgt))<lry&&(y>=fry))
409 { if (divisor) id=(dgt_id(dgt)%modulo)/divisor;
412 { fprintf(stderr,"Label ID too large. Use -d or -x options\n");
416 row=dgt2row(dgt_pointx(dgt));
418 if (CELL(buf,row,col))
419 { printf("%g %g more than one object in same cell\n",alt_xc(fout,col),alt_yc(fout,row));
421 CELL(buf,row,col)=id;
425 { if (dgt_yt(dgt)>lry&&dgt_yb(dgt)<fry)
427 POINT *start,*end,p1,p2;
428 if (fill) id=line_color;
430 { if (divisor) id=(dgt_id(dgt)%modulo)/divisor;
433 { fprintf(stderr,"Line ID too large. Use -d or -x options\n");
438 /* Now we can begin an actual drawing */
439 for (i=1,start=dgt->buffer->s,end=dgt->buffer->s+1;
440 i<dgt_line_len(dgt);i++,start++,end++)
441 if((start->y>lry&&end->y<fry)||(start->y<fry&&end->y>lry))
443 if (start->y>end->y) {p1=*end;p2=*start;}
447 {int xx=(lry-p1.y)*((int)p2.x-p1.x)/((int)p2.y-p1.y)+p1.x;
452 {int xx=(fry-p1.y)*((int)p2.x-p1.x)/((int)p2.y-p1.y)+p1.x;
460 if(rc2.x==rc1.x&&rc2.y==rc1.y)
461 { CELL(buf,rc1.y,rc1.x)=id;
462 if (fill) CELL(buf,rc1.y,rc1.x)|=2;
465 if ((unsigned long)abs((int)p1.x-p2.x)*bottom_border>(unsigned long)abs((int)p1.y-p2.y)*right_border)
466 { /* ïÔÒÅÚÏË ÛÉÒÅ ÞÅÍ ÄÌÉÎÎÅÅ */
476 xn=((int)p1.x+32767)*ncol-half_horiz;
477 ndx=((int)p2.x-p1.x)*ncol;
479 for (x=rc1.x;x<=rc2.x;x++)
480 { unsigned long ybig=(32767UL-((right_border*x-xn)*dy/ndx+p1.y))*nrow;
481 y=ybig/bottom_border+1-firstrow;
485 CELL(fillbuf,y,x)|=ybig%bottom_border>half_vert?4:1;
491 yn=(32767-(int)p1.y)*nrow-half_vert;
492 ndy=((int)p2.y-p1.y)*nrow;
494 for (y=rc1.y;y<=rc2.y;y++)
495 { unsigned long xbig=(32767UL+((yn-bottom_border*
496 (y-1+firstrow))*dx /ndy+p1.x))*ncol;
500 CELL(fillbuf,y,x)|=xbig%right_border>half_horiz?8:2;
511 if (save_buffer(fout,buf,firstrow,lastrow,width)) {free(buf);return 1;};
513 if (save_buffer(fill,fillbuf,firstrow,lastrow,width)) {free(buf);return 1;};
516 } while(firstrow<fout->lc);
520 void extract_digits(int base,char *s,int *divisor,int *modulo)
526 {case '_':if (*modulo&&!*divisor)*divisor=base;
531 case 'x':if(!*modulo) *modulo=base;
533 if (*divisor) {fprintf(stderr,"Digits in -d or -x option must form continous range\n");
537 default: fprintf(stderr,"Parameter of -d or -x option must consist of ``x''-es\n"
538 "for each digit to use and ``_'' for each digit to ignore\n");
541 if (*divisor==0) *divisor=1;
542 if (*modulo/ *divisor>0x10000)
543 { fprintf(stderr,"EPP file classes cannot contain more than four digits\n");
548 # ifndef EARLY_UNLINK
550 char __tempnames[4][80];
551 char *tempnames[]={__tempnames[0],__tempnames[1],__tempnames[2],__tempnames[3]};
552 char **tempptr=tempnames;
553 void store_temp_name(char *name)
554 {strcpy(*(tempptr++),name);
556 void remove_temp_files()
557 {while(--tempptr>=tempnames)
564 "Usage: cluster [--help] [-version] [-%%8lu] [-o file] [-c color] file\n";
565 char rasterize_help[]=
566 "Usage: rasterize [--help] [-version] [-o file] [-c color] [-s size]\n"
567 "\t[-x string] [-d string] [-m megabytes] [-%%pu] file\n";
569 int main(int argc,char **argv)
570 {struct option cluster_options[]={
574 {"output-file",1,0,'o'},
575 {"line-color",1,0,'c'},
577 {"rasterize",0,0,'R'},
581 rasterize_options[]={
585 {"output-file",1,0,'o'},
586 {"cell-size",1,0,'s'},
587 {"line-color",1,0,'c'},
588 {"line-point",0,0,'p'},
590 {"hex-digits",1,0,'x'},
594 *options=cluster_options;
595 int c,index,expect_vector=0;
596 char c_opt[]="%o:c:8Rlu",
597 r_opt[]="%o:c:s:pudxm:",
600 char tempname[1024],outname[1024]="";
601 int verbose=0,eight_way=0,do_labels=0,result,maxclass;
602 EPP *fin,*ffill=NULL,*ftmp1,*ftmp2,*fout;
603 int modulo=0,divisor=0;
604 int (*remap)(void)=remap_labels;
605 double cell_size=0.0;
607 if ((basename=strrchr(argv[0],'/')))
608 basename++; else basename=argv[0];
609 if (!strcmp(basename,"rasterize"))
610 { optstring=r_opt; options=rasterize_options;
612 remap=remap_hard_labels;
615 while ((c=getopt_long(argc,argv,optstring,options,&index))!=-1)
618 case '%' :verbose=1;break;
619 case 2 : show_version("cluster","$Revision: 1.1 $");
620 case 'o':strcpy(outname,default_ext(optarg,".epp"));break;
621 case 'R':optstring=r_opt;options=rasterize_options;
622 remap=remap_hard_labels;
624 expect_vector=1;break;
625 case 'c':{char *endptr;
626 line_color=strtol(optarg,&endptr,0);
627 if (*endptr||line_color<=0||line_color>65535)
628 { fprintf(stderr,"Invalid line color %s\n",optarg);
633 case 'u':if (!expect_vector) is_border=check_border;
634 else {remap=remap_labels;do_labels=0;}
636 case '8':if (expect_vector)
637 {fprintf(stderr,"option -8 is valid only in cluster mode\n");
642 case 'l':if (expect_vector)
643 {fprintf(stderr,"option -l is valid only in cluster mode\n");
646 remap=remap_labels;do_labels=1;
648 case 's':if (!expect_vector)
649 {fprintf(stderr,"option -%c is valid only in rasterize mode\n",c);
653 cell_size=strtod(optarg,&endptr);
655 { fprintf(stderr,"Invalid cell size value %s\n",optarg);
660 case 'p': if (!expect_vector)
661 {fprintf(stderr,"option -%c is valid only in rasterize mode\n",c);
666 case 'd':if (!expect_vector)
667 {fprintf(stderr,"option -%c is valid only in rasterize mode\n",c);
670 extract_digits(10,optarg,&divisor,&modulo);
672 case 'x':if (!expect_vector)
673 {fprintf(stderr,"option -%c is valid only in rasterize mode\n",c);
676 extract_digits(16,optarg,&divisor,&modulo);
678 case 'm':if (!expect_vector)
679 {fprintf(stderr,"option -%c is valid only in rasterize mode\n",c);
683 megabytes=strtol(optarg,&endptr,0);
685 { fprintf(stderr,"Invalid integer value %s\n",optarg);
693 default: printf(expect_vector?rasterize_help:cluster_help);
696 /***********************************************************/
698 {fprintf(stderr,"No input file name given\n");
701 strcpy(tempname,default_ext(argv[optind],expect_vector?".dgt":".epp"));
703 if (expect_vector) strcpy(outname,force_ext(tempname,".epp"));
706 strcpy(outname,"cluster.out.epp");
708 strcpy(outname,"cluster.epp");
710 install_progress_indicator(verbose?show_percent:check_int);
711 /*** Zero pass,rasterizing **********************************/
713 {DGT *dgt=open_dgt(tempname);
716 if (!dgt) { fprintf(stderr,"Cannot open file %s\n",tempname);
719 /*calculating file dimensions*/
721 { /*no cell size given, defaulting to 1024 cells/line*/
722 cell_size=fabs(dgt->XRight-dgt->XLeft)/1024.0;
724 cols=ceil(fabs(dgt->XRight-dgt->XLeft)/cell_size);
725 rows=ceil(fabs(dgt->YTop-dgt->YBottom)/cell_size);
727 if (dgt->XRight<dgt->XLeft) XR=dgt->XLeft-XR;
730 if (dgt->YTop>dgt->YBottom) YB=dgt->YTop-YB;
732 fprintf(stderr,"EPP file would be %d rows by %d columns\n",rows,cols);
734 /*creating outputfile*/
737 { /*rasterized file would be temporary */
739 strcpy(tempname,force_ext(tmpnam(NULL),".epp"));
741 strcpy(tempname,outname);
742 fin=creat_epp(tempname,1,1,cols,rows,dgt->XLeft,dgt->YTop,XR,YB,
745 if (!fin) {fprintf(stderr,"Cannot create file %s\n",tempname);
748 if (expect_vector==1)
753 store_temp_name(tempname);
755 strcpy(tempname,force_ext(tmpnam(NULL),".epp"));
756 ffill=creat_epp(tempname,1,1,cols,rows,dgt->XLeft,dgt->YTop,XR,YB,
758 if (!ffill) {fprintf(stderr,"Cannot create file %s\n",tempname);
764 store_temp_name(tempname);
767 if (verbose) fprintf(stderr,"Rasterizing...\n");
768 if ((result=rasterize(dgt,fin,ffill,modulo,divisor)))
769 exit(clear_progress(result));
771 if (expect_vector==2)
772 { /* nothing more to do - close and exit */
775 if (verbose) fprintf(stderr,"\rConverting to 8 bit\n");
778 fast_convert_to_8bit(fin,outname);
780 strcpy(tempname,force_ext(outname,".8bi"));
781 fast_convert_to_8bit(fin,tempname);
783 rename(tempname,outname);
785 } else close_epp(fin);
786 exit(clear_progress(result));
793 if (!(fin=open_epp(tempname)))
794 { fprintf(stderr,"Cannot open file %s",tempname);
797 /*************** First pass -- counting unique contours ***************/
798 if (verbose) fprintf(stderr,"\rAssembling polygons...\n");
801 strcpy(tempname,force_ext(tmpnam(NULL),".epp"));
802 if(!(ftmp1=creat_epp_as(tempname,fin)))
803 { fprintf(stderr,"Cannot create file %s\n",tempname);
809 store_temp_name(tempname);
811 strcpy(tempname,default_ext(tmpnam(NULL),".epp"));
812 if(!(ftmp2=creat_epp_as(tempname,fin)))
813 { fprintf(stderr,"Cannot create file %s\n",tempname);
819 store_temp_name(tempname);
821 if (!expect_vector&&(is_border==check_border))line_color=fin->offsite;
822 if((result=first_pass(fin,ftmp1,ftmp2,eight_way,do_labels)))
823 exit(clear_progress(result));
824 /**** creating correspondence table *************/
825 if (verbose) {fputc('\r',stderr);fflush(stderr);}
827 /************* Second pass -- creating final file *****************/
828 fout=creat_epp_as(outname,ftmp1);
829 if (do_labels) fout->offsite=Create16bit?65535:255;
830 if (verbose) fprintf(stderr,"\rWriting final file...\n");
832 result=second_pass_fill(ftmp1,ftmp2,ffill,fout);
834 result=second_pass(ftmp1,ftmp2,fout);
840 return(clear_progress(result));