home *** CD-ROM | disk | FTP | other *** search
/ vis-ftp.cs.umass.edu / vis-ftp.cs.umass.edu.tar / vis-ftp.cs.umass.edu / pub / Software / ASCENDER / ascendMar8.tar / UMass / BoldtOld / MERGE / mergelines.c < prev    next >
C/C++ Source or Header  |  1995-07-22  |  12KB  |  481 lines
  1.  
  2. #include "geometry2d.h"
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <math.h>
  7.  
  8.  
  9. typedef enum flag_type {ON, OFF} FLAG;
  10.  
  11. typedef struct NODE {
  12.   POINT2D *endpt1, *endpt2;
  13.   float contrast;  
  14.   LINE2D *lineABC;
  15.   FLAG flag;
  16.   struct NODE *next;} *LINELIST;
  17.  
  18. typedef struct {
  19.   int rowcells;
  20.   int colcells;
  21.   int blockdim;
  22.   int startx;
  23.   int starty;
  24.   LINELIST *cells;} LINEGRID;
  25.  
  26. #define GRIDCELL(grid,x,y) \
  27.   (((grid)->cells)+(y)*((grid)->colcells)+(x))
  28.  
  29. #define CREATE_NODE(node) \
  30.   {node = (struct NODE *)malloc(sizeof(struct NODE)); \
  31.    node->endpt1 = (POINT2D *)malloc(sizeof(POINT2D)); \
  32.    node->endpt2 = (POINT2D *)malloc(sizeof(POINT2D)); \
  33.    node->lineABC = (LINE2D *)malloc(sizeof(LINE2D));}
  34.  
  35. #define FREE_NODE(node) \
  36.   {free(node->endpt1); \
  37.    free(node->endpt2); \
  38.    free(node->lineABC); \
  39.    free(node);}
  40.  
  41.  
  42. /**********************************************************************/
  43.  
  44.  
  45. LINELIST read_in_lines(char *filename, float startX, float startY)
  46. {
  47.   FILE *infile;
  48.   float x1,y1,x2,y2,contrast;
  49.   LINELIST head, current, node;
  50.  
  51.   if ((infile = fopen(filename,"r")) == NULL) {
  52.     perror("error opening input file");
  53.     perror(filename);
  54.     return(NULL);
  55.   }
  56.  
  57.   CREATE_NODE(current);
  58.   current->flag = OFF;
  59.   current->next = NULL;
  60.   head = current;
  61.  
  62.   while ((fscanf(infile,"%f %f %f %f %f",&x1,&y1,&x2,&y2,&contrast)) != EOF) {
  63.     CREATE_NODE(node);
  64.     set_point2d(node->endpt1,(startX + x1),(startY + y1));
  65.     set_point2d(node->endpt2,(startX + x2),(startY + y2));
  66.     node->contrast = contrast;
  67.     set_line2d_from_endpoints(node->lineABC,node->endpt1,node->endpt2);
  68.     node->flag = ON;
  69.     node->next = NULL;
  70.     current->next = node;
  71.     current = node;
  72.   }
  73.  
  74.   if (fclose(infile) == EOF) {
  75.     perror("error closing input file");
  76.     perror(filename);
  77.   }
  78.  
  79.   return(head);
  80. }
  81.  
  82.  
  83. void write_out_file_header(char *filename)
  84. {
  85.   FILE *outfile;
  86.  
  87.   if ((outfile = fopen(filename,"w")) == NULL) {
  88.     perror("error opening output file");
  89.     perror(filename);
  90.     return;
  91.   }
  92.  
  93.   fprintf(outfile,"3D: NO\n");
  94.   fprintf(outfile,"DATA:\n");
  95.  
  96.   if (fclose(outfile) == EOF) {
  97.     perror("error closing output file");
  98.     perror(filename);
  99.   }
  100.  
  101.   return;
  102. }
  103.  
  104. LINELIST write_out_lines(LINELIST linelist, char *filename, char *mode)
  105. {
  106.   FILE *outfile;
  107.   LINELIST current;
  108.  
  109.   if ((outfile = fopen(filename,mode)) == NULL) {
  110.     perror("error opening output file");
  111.     perror(filename);
  112.     return(linelist);
  113.   }
  114.  
  115.   current = linelist;
  116.  
  117.   while (current != NULL) {
  118.     if (current->flag == ON)
  119.       if (fprintf(outfile,"%.2f %.2f %.2f %.2f %.2f\n",
  120.           current->endpt1->x, current->endpt1->y,
  121.           current->endpt2->x, current->endpt2->y,
  122.           current->contrast) == EOF) {
  123.     perror("error writing to output file");
  124.     perror(filename);
  125.     return(linelist);
  126.       }
  127.     current = current->next;
  128.   }
  129.  
  130.   if (fclose(outfile) == EOF) {
  131.     perror("error closing output file");
  132.     perror(filename);
  133.   }
  134.  
  135.   return(linelist);
  136. }
  137.  
  138.  
  139. int count_lines(LINELIST linelist)
  140. {
  141.   int count;
  142.   LINELIST current;
  143.  
  144.   if (linelist == NULL) 
  145.     return(0);
  146.  
  147.   count = 0;
  148.   current = linelist;
  149.   while (current != NULL) {
  150.     if (current->flag == ON)
  151.       count++;
  152.     current = current->next;
  153.   }
  154.  
  155.   return(count);
  156. }
  157.  
  158. void free_lines(LINELIST linelist)
  159. {
  160.   LINELIST current, nextptr;
  161.  
  162.   current = linelist;
  163.  
  164.   while (current != NULL) {
  165.     nextptr = current->next;
  166.     FREE_NODE(current);
  167.     current = nextptr;
  168.   }
  169.  
  170.   return;
  171. }
  172.  
  173.  
  174. /**********************************************************************/
  175.  
  176. /* maximum absolute sine of angle between lines to merge */
  177. /* #define SIN_ANGLE_THRESHOLD 0.01745241 */  /* 1 degree */
  178.  
  179. #define SIN_ANGLE_THRESHOLD 0.034906585  /* 2 degrees */
  180.  
  181. /* maximum lateral distance in pixels between lines */
  182. #define LATERAL_DISTANCE_THRESHOLD 1.0
  183.  
  184. /* maximum longitudinal distance in pixels between lines */
  185. #define GAP_THRESHOLD 1.0
  186.  
  187.  
  188. /* Reorder 4 nearly colinear points p1,...,p4 and return them as pa,...,pd   */
  189. /* so that pa and pd are at the two extremes and pb and pc are in the middle.*/
  190.  
  191. void rearrange_endpoints(POINT2D *p1, POINT2D *p2, POINT2D *p3, POINT2D *p4,
  192.              POINT2D *pa, POINT2D *pb, POINT2D *pc, POINT2D *pd)
  193. {
  194.   POINT2D pmid;
  195.   LINE2D uvec;
  196.  
  197.   pmid.x = (p1->x + p2->x + p3->x + p4->x) / 4.0;
  198.   pmid.y = (p1->y + p2->y + p3->y + p4->y) / 4.0;
  199.   set_line2d(&uvec, p1->x - pmid.x, p1->y - pmid.y, 0.0);
  200.  
  201.   if (signed_distance_pl2d(p1,&uvec) > signed_distance_pl2d(p2,&uvec)) {
  202.     copy_point2d(pa,p1); 
  203.     copy_point2d(pb,p2);}
  204.   else {
  205.     copy_point2d(pa,p2); 
  206.     copy_point2d(pb,p1);}
  207.  
  208.   if (signed_distance_pl2d(p3,&uvec) > signed_distance_pl2d(p4,&uvec)) {
  209.     copy_point2d(pc,p3); 
  210.     copy_point2d(pd,p4);}
  211.   else {
  212.     copy_point2d(pc,p4); 
  213.     copy_point2d(pd,p3);}
  214.  
  215.   if (signed_distance_pl2d(pc,&uvec) > signed_distance_pl2d(pa,&uvec))
  216.     swap_points2d(pa,pc);
  217.  
  218.   if (signed_distance_pl2d(pd,&uvec) > signed_distance_pl2d(pb,&uvec))
  219.     swap_points2d(pb,pd);
  220.  
  221.   return;
  222. }
  223.  
  224.  
  225. /* Determine whether line1 and line2 should be merged.  If so, modify */
  226. /* line1 to be the merged line and delete line2. */
  227.  
  228. void process_line_pair (struct NODE *line1, struct NODE *line2)
  229. {
  230.   POINT2D pta,ptb,ptc,ptd;
  231.   LINE2D mergeABC;
  232.  
  233.  
  234. /*
  235.   printf("L1 = %.2f  %.2f  %.2f  %.2f \nL2 = %.2f  %.2f  %.2f  %.2f\n",
  236.      line1->endpt1->x,line1->endpt1->y,
  237.      line1->endpt2->x,line1->endpt2->y,
  238.      line2->endpt1->x,line2->endpt1->y,
  239.      line2->endpt2->x,line2->endpt2->y);
  240.   printf("sin angle is %f\n", sin_angle_ll2d(line1->lineABC,line2->lineABC));
  241. */
  242.  
  243.   if (sin_angle_ll2d(line1->lineABC,line2->lineABC) < SIN_ANGLE_THRESHOLD) {
  244.     rearrange_endpoints(line1->endpt1,line1->endpt2,
  245.             line2->endpt1,line2->endpt2,
  246.             &pta,&ptb,&ptc,&ptd);
  247.     set_line2d_from_endpoints(&mergeABC,&pta,&ptd);
  248.  
  249. /*
  250.     printf("%.2f  %.2f  %.2f  %.2f  %.2f  %.2f  %.2f  %.2f\n",
  251.        line1->endpt1->x,line1->endpt1->y,
  252.        line1->endpt2->x,line1->endpt2->y,
  253.        line2->endpt1->x,line2->endpt1->y,
  254.        line2->endpt2->x,line2->endpt2->y);
  255.     printf("%.2f  %.2f  %.2f  %.2f  %.2f  %.2f  %.2f  %.2f\n",
  256.        pta.x,pta.y,ptb.x,ptb.y,ptc.x,ptc.y,ptd.x,ptd.y);
  257.     printf("L1  = %f  %f  %f\n",line1->lineABC->a, line1->lineABC->b,
  258.        line1->lineABC->c);
  259.     printf("L2  = %f  %f  %f\n",line2->lineABC->a, line2->lineABC->b,
  260.        line2->lineABC->c);
  261.     printf("ABC = %f  %f  %f\n",mergeABC.a,mergeABC.b,mergeABC.c);
  262.     printf("%f  <  %f\n",
  263.        (sin_angle_ll2d(&mergeABC,line1->lineABC)),SIN_ANGLE_THRESHOLD);
  264.     printf("%f  <  %f\n",
  265.        (sin_angle_ll2d(&mergeABC,line2->lineABC)),SIN_ANGLE_THRESHOLD);
  266.     printf("%f  <  %f\n",
  267.        distance_pl2d(&ptb,&mergeABC),LATERAL_DISTANCE_THRESHOLD);
  268.     printf("%f  <  %f\n",
  269.        (distance_pl2d(&ptc,&mergeABC)),LATERAL_DISTANCE_THRESHOLD);
  270.     printf("%f  <  %f\n",(distance_pp2d(&pta,&ptd)),
  271.        (distance_pp2d(line1->endpt1,line1->endpt2) +
  272.         distance_pp2d(line2->endpt1,line2->endpt2) +
  273.         GAP_THRESHOLD));
  274. */
  275.  
  276.     if ((sin_angle_ll2d(&mergeABC,line1->lineABC) < SIN_ANGLE_THRESHOLD) &&
  277.     (sin_angle_ll2d(&mergeABC,line2->lineABC) < SIN_ANGLE_THRESHOLD) &&
  278.     (distance_pl2d(&ptb,&mergeABC) < LATERAL_DISTANCE_THRESHOLD) &&
  279.     (distance_pl2d(&ptc,&mergeABC) < LATERAL_DISTANCE_THRESHOLD) &&
  280.     (distance_pp2d(&pta,&ptd) <= 
  281.          (distance_pp2d(line1->endpt1,line1->endpt2) +
  282.           distance_pp2d(line2->endpt1,line2->endpt2) +
  283.           GAP_THRESHOLD)))
  284.       /* merge lines */
  285.       {
  286.  
  287. /*
  288.     printf("newpath %.2f %.2f mt %.2f %.2f lt 1 0 0 setrgbcolor stroke\n",
  289.            line1->endpt1->x,line1->endpt1->y,
  290.            line1->endpt2->x,line1->endpt2->y);
  291.     printf("newpath %.2f %.2f mt %.2f %.2f lt 0 1 0 setrgbcolor stroke\n",
  292.            line2->endpt1->x,line2->endpt1->y,
  293.            line2->endpt2->x,line2->endpt2->y);
  294. */
  295. /*
  296.     printf("newpath %.2f %.2f mt %.2f %.2f lt 0 0 1 setrgbcolor stroke\n",
  297.            pta.x,pta.y,ptd.x,ptd.y);
  298. */
  299.     copy_point2d(line1->endpt1,&pta);
  300.     copy_point2d(line1->endpt2,&ptd);
  301.     copy_line2d(line1->lineABC,&mergeABC);
  302.     line1->contrast = (line1->contrast + line2->contrast) / 2.0;
  303.  
  304.     line2->flag = OFF;
  305.       }
  306.   }
  307. }
  308.  
  309.  
  310.  
  311. void process_line_lists(LINELIST list1, LINELIST list2)
  312. {
  313.   LINELIST listptr;
  314.  
  315.   while (list1 != NULL) {
  316.     if (list1->flag == ON) {
  317.       listptr = list2;
  318.       while (listptr != NULL) {
  319.         if (listptr->flag == ON)
  320.       process_line_pair(list1,listptr);
  321.     listptr = listptr->next;
  322.       }
  323.     }
  324.     list1 = list1->next;
  325.   }
  326. }
  327.  
  328. /**********************************************************************/
  329.  
  330.  
  331. void parse_filename (char *namestring, int *x, int *y)
  332. {
  333.   char *ptr1, *ptr2;
  334.  
  335.   ptr1 = namestring;
  336.   while(*ptr1++ != NULL);
  337.   while(*(--ptr1) != '.');
  338.   ptr2 = ptr1;
  339.   while(*(--ptr2) != 'Y');
  340.   *ptr1 = '\0';
  341.   *y = atoi(ptr2+1);
  342.   *ptr1 = '.';
  343.   ptr1 = ptr2;
  344.   while(*(--ptr1) != 'X');
  345.   *ptr2 = '\0';
  346.   *x = atoi(ptr1+1);
  347.   *ptr2 = 'Y';
  348.  
  349.   return;
  350. }
  351.  
  352. int read_info(char *info_filename, char *infolabel)
  353. {
  354.   FILE *infile;
  355.   char *strptr;
  356.   char infoline[64];
  357.   int info;
  358.  
  359.   if ((infile = fopen(info_filename,"r")) == NULL) {
  360.     perror("error opening info file");
  361.     perror(info_filename);
  362.     return(-1);
  363.   }
  364.   strptr = infolabel;
  365.   while(fgets(infoline, 63, infile) != NULL)  
  366.     if (!strncmp(infoline,infolabel,strlen(infolabel)-1)) {
  367.       sscanf((infoline+strlen(infolabel)+1),"%d",&info);
  368.       fclose(infile);
  369.       return(info);
  370.     }
  371.   perror("requested info not found in info file");
  372.   perror(infolabel);
  373.   fclose(infile);
  374.   return(-1);
  375. }
  376.  
  377.  
  378. LINEGRID *init_line_grid(char *info_filename)
  379. {
  380.   LINEGRID *grid;
  381.   int rowblocks, colblocks;
  382.   int width, overlap;
  383.   int imrowmax, croprowmax, cropcolmin;
  384.  
  385.   imrowmax = read_info(info_filename,"image maxrow");
  386.   croprowmax = read_info(info_filename,"crop maxrow");
  387.   cropcolmin = read_info(info_filename,"crop mincol");
  388.   rowblocks = read_info(info_filename,"row numblocks");
  389.   colblocks = read_info(info_filename,"col numblocks");
  390.   width = read_info(info_filename,"block width");
  391.   overlap = read_info(info_filename,"block overlap");
  392.  
  393.   grid = (LINEGRID *)malloc(sizeof(LINEGRID));
  394.   grid->rowcells = rowblocks;
  395.   grid->colcells = colblocks;
  396.   grid->blockdim = width - overlap;
  397.   grid->startx = cropcolmin;
  398.   grid->starty = imrowmax - croprowmax;
  399.   grid->cells = (LINELIST *)malloc(rowblocks*colblocks*(sizeof(LINELIST))); 
  400.  
  401.  
  402.  
  403.  
  404.  
  405.   return(grid);
  406. }
  407.  
  408.  
  409. void read_line_file_into_grid(char *filename, LINEGRID *grid)
  410. {
  411.   LINELIST linelist;
  412.   int startX, startY;
  413.   int xindex, yindex;
  414.  
  415.   parse_filename(filename,&startX,&startY);
  416.  
  417.   linelist = read_in_lines(filename,(float)startX,(float)startY);
  418.   xindex = (int)((startX - grid->startx) / grid->blockdim);
  419.   yindex = (int)((startY - grid->starty) / grid->blockdim);
  420.  
  421.   *GRIDCELL(grid,xindex,yindex) = linelist;
  422.   return;
  423. }
  424.   
  425.  
  426.  
  427. /**********************************************************************/
  428.  
  429. #define INFOFILE argv[1]
  430. #define OUTPUTFILE argv[2]
  431.  
  432. void main(int argc, char *argv[])
  433. {
  434.   LINEGRID *grid;
  435.   int count = 3;
  436.   int row, col, numcells;
  437.  
  438.  
  439.   grid = init_line_grid(INFOFILE);
  440.  
  441.   while(count<argc) { 
  442.     read_line_file_into_grid(argv[count], grid);
  443.     count++;}
  444.  
  445.  
  446.   printf("\nGrid counts\n");
  447.   for (row = 0; row < grid->rowcells; row++) {
  448.     printf("  ");
  449.     for (col = 0; col < grid->colcells; col++)
  450.       printf("  %d", 
  451.          count_lines(*GRIDCELL(grid,col,(grid->rowcells - 1 - row))));
  452.     printf("\n");
  453.   }
  454.   printf("\n");
  455.  
  456.  
  457.   /* merging across columns */
  458.   for (row = 0; row < grid->rowcells; row++) 
  459.     for (col = 0; col < grid->colcells - 1; col++) {
  460.       process_line_lists(*GRIDCELL(grid,col,row),*GRIDCELL(grid,col+1,row));
  461.     }
  462.  
  463.   /* merging down rows */
  464.   for (col = 0; col < grid->colcells; col++) 
  465.     for (row = 0; row < grid->rowcells - 1; row++) {
  466.       process_line_lists(*GRIDCELL(grid,col,row),*GRIDCELL(grid,col,row+1));
  467.     }
  468.  
  469.   /* output to file */
  470.   numcells = grid->rowcells * grid->colcells;
  471.   count = 0;
  472.   write_out_file_header(OUTPUTFILE);
  473.   while (count < numcells) {
  474.     write_out_lines((grid->cells)[count],OUTPUTFILE,"a");
  475.     free_lines((grid->cells)[count]);
  476.     count++;
  477.   }
  478.  
  479.   return;
  480. }
  481.