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 / BuildingFinder / Staging / graph.c < prev    next >
C/C++ Source or Header  |  1994-01-25  |  6KB  |  332 lines
  1. #include "../polygons.h"
  2. /***************************************************************************
  3.     
  4.     buildGraph
  5.  
  6.     Takes a corner list and the 2D corner array, builds the corner
  7.     hypothesis graph.  Each vertex in the graph represents a 
  8.     corner, each edge a valid link.  
  9.  
  10.     G = (V,E)
  11.  
  12.     V in G if V in corner Set.
  13.     E =(u,v).  If Corner u has an axis that points at v and vise-versa.
  14.                And the "edge support" > MIN_EDGE SUPPORT.
  15.  
  16.     This graph will contain all the possible legal groupings.  Note:
  17.     the SSC of G will be probable rooftops.
  18.            
  19. *****************************************************************************/
  20.  
  21. void buildGraph(cList *list,c_handle im, c_handle pane)
  22. {
  23.  
  24.     cList *ptr; 
  25.     int count=0;
  26.  
  27.  
  28.     ptr = list;
  29.  
  30.  
  31.     if (ptr == NULL)
  32.         return;
  33.     
  34.     /** Move through the list, check if an edge should exist. ***/
  35.     while (ptr->next != NULL) {
  36.        count += buildEdges(ptr, ptr->next, im, pane);
  37.        ptr = ptr->next;
  38.     }
  39.  
  40.     fprintf(stderr,"Built %d edges in the FRG\n",count);
  41.  
  42. }
  43.  
  44. int buildEdges(cList *ptr, cList *list, c_handle im, c_handle pane)
  45. {
  46.  
  47.      cList *candidate;
  48.      float str;
  49.      int built=0;
  50.      int pos;
  51.      int dir;
  52.      int ax;
  53.  
  54.      candidate = list;
  55.  
  56.      
  57.  
  58.      while (candidate != NULL) {
  59.     /*** Attempt to fit either axis to the candiate.  If no edge
  60.              exists and the corners are compatible, create one. ***/
  61.     if ( (!linkedByEdge(ptr,candidate)) && 
  62.             (ax = cornersCompatible(ptr,candidate))) {
  63.       if ( (str = enoughSupport(im,ptr,candidate,ax,&pos, &dir)))  {
  64.            buildEdge(ptr,candidate,str, ax, pane, pos, dir);
  65.            built++;
  66.         }
  67.      else 
  68.       if ( (str = enoughSupport(im,candidate,ptr,ax,&pos, &dir)))  {
  69.            buildEdge(ptr,candidate,str, ax, pane, pos, dir);
  70.            built++;
  71.       }
  72.  
  73.     }
  74.     candidate = candidate->next;
  75.     }
  76.     return(built);
  77. }
  78.  
  79.  
  80. int
  81. buildEdge(cList *v1, cList *v2, float str, int axis, c_handle pane, int pos, int dir)
  82. {
  83.  
  84.     edgeList *edge;
  85.     edgeList *newEdge;
  86.     double_2  *p1, *p2;
  87.     double_2  *temp1, *temp2;
  88.  
  89.     temp1 = (double_2 *) transform_point(view_trans,(double)v1->x,
  90.                 (double)v1->y,0);
  91.     temp2 = (double_2 *) transform_point(view_trans,(double)v2->x,
  92.                 (double)v2->y,0);
  93.  
  94.     p1 = (double_2 *) inverse_transform_point(image_trans,
  95.             (double)temp1->d1,(double)temp1->d2,0);
  96.     p2 = (double_2 *) inverse_transform_point(image_trans,
  97.             (double)temp2->d1, (double)temp2->d2,0);
  98.  
  99.     
  100.  
  101.     draw_fat_line(pane,p1->d1,p1->d2,p2->d1,p2->d2,2.0);
  102.     flush_display(pane);
  103.  
  104.     newEdge = (edgeList *) malloc(sizeof(edgeList));
  105.  
  106.     edge = v1->eList;
  107.  
  108.     v1->eList = newEdge;
  109.     v1->eList->confidence = str;
  110.         v1->eList->type = axis; 
  111.     v1->eList->vertex = v2;
  112.     v1->eList->position = pos;
  113.     v1->eList->dir = dir;
  114.     v1->eList->next = edge;
  115.  
  116.  
  117.  
  118.     newEdge = (edgeList *) malloc(sizeof(edgeList));
  119.  
  120.     edge = v2->eList;
  121.  
  122.     v2->eList = newEdge;
  123.     v2->eList->confidence = str;
  124.            v2->eList->type = axis; 
  125.     v2->eList->vertex = v1;
  126.     v2->eList->position = pos;
  127.     v2->eList->dir = dir;
  128.     v2->eList->next = edge;
  129.  
  130.  
  131. }
  132.  
  133.  
  134.  
  135.  
  136. /*
  137.  *
  138.  * linkedByEdge
  139.  *
  140.  * Check if an edge has already been constructed between the two 
  141.  * corner features. c1, c2.
  142.  *
  143.  */
  144. int linkedByEdge(cList *c1, cList *c2)
  145. {
  146.  
  147.    edgeList *ptr, *ptr2;
  148.  
  149.    /* Compare the edge lists of the two features, 
  150.     * if they both have the same edge, they are connected.
  151.     * 
  152.    ptr = c1->eList;
  153.    while (ptr != NULL) {
  154.        ptr2 = c2->eList;
  155.     while (ptr2 != NULL) {
  156.        if (ptr2 == ptr) {
  157.         return(TRUE);
  158.        }
  159.        ptr2 = ptr2->next;
  160.     }
  161.  
  162.     ptr = ptr->next;
  163.    }
  164.     */
  165.  
  166.    ptr = c1->eList;
  167.    while (ptr != NULL) {
  168.     if (ptr->vertex == c2)
  169.         return(TRUE);
  170.     ptr = ptr->next;
  171.    }
  172.  
  173.    ptr = c2->eList;
  174.    while (ptr != NULL) {
  175.     if (ptr->vertex == c1)
  176.         return(TRUE);
  177.     ptr = ptr->next;
  178.    }
  179.  
  180.    return(FALSE);
  181.     
  182.  
  183. }
  184.  
  185.  
  186.  
  187.  
  188. double
  189. transLine(int line, cList *vertex)
  190. {
  191.  
  192.     double Dx, Dy;
  193.     mat_4x1 vector;
  194.     mat_4x1 lineVec;
  195.  
  196.     
  197.     vector[0] = (double) vertex->x;
  198.     vector[1] = (double) vertex->y;
  199.     vector[2] = 0.0;
  200.     vector[3]= 1.0;
  201.     
  202.     project_2d_to_3d(IMAGE_NAME,vector,vector);
  203.     
  204.     lineVec[0] = (double) vertex->x + line;
  205.     lineVec[1] = (double) vertex->y;
  206.     lineVec[2] = 0.0;
  207.     lineVec[3] = 1.0;
  208.  
  209.     project_2d_to_3d(IMAGE_NAME,lineVec,lineVec);
  210.  
  211.     Dx = fabs(lineVec[0] - vector[0]);
  212.     Dy = fabs(lineVec[1] - vector[1]);
  213.  
  214.     if (Dy > Dx)
  215.         return(Dy);
  216.     else
  217.         return(Dx);
  218. }
  219.  
  220.  
  221. double idealY(int Dx, int Dy, RotMatrix Forward, RotMatrix Back)
  222. {
  223.  
  224.     Point vec;
  225.  
  226.  
  227.     vec.x = Dx;
  228.     vec.y = Dy;
  229.     vec.z = 0.0;
  230.     vec.r = 1.0;
  231.  
  232.     /*** Transform the Dx, into the world system ***/
  233.     vector_matrix_multiply(&vec,Back);
  234.  
  235.     vec.y = 0.0;
  236.     vec.z = 0.0; /** Not sure ?? **/
  237.     vec.r = 0.0;
  238.  
  239.     /*** Now transform this vector into the perspective
  240.          to find the expected Dy ***/
  241.     vector_matrix_multiply(&vec,Forward);
  242.     
  243.     return(vec.y);
  244. }
  245.  
  246. double idealX(int Dx, int Dy, RotMatrix Forward, RotMatrix Back)
  247. {
  248.  
  249.     int i,j;
  250.     Point vec;
  251.  
  252.     vec.x = Dx;
  253.     vec.y = Dy;
  254.     vec.z = 0.0;
  255.     vec.r = 1.0;
  256.  
  257.     /*** Transform the Dy, into the world system ***/
  258.     vector_matrix_multiply(&vec,Back);
  259.  
  260.     vec.x = 0.0;
  261.     vec.z = 0.0;  /** Not Sure ??**/
  262.     vec.r = 1.0;
  263.     
  264.     /*** Now transform this vector into the perspective
  265.          to find expected Dx ***/
  266.     vector_matrix_multiply(&vec,Forward);
  267.     
  268.     return(vec.x);
  269. }
  270.  
  271. float enoughSupport(c_handle im, cList *c1, cList *c2, int axis, int *position,
  272.                             int *image_dir)
  273. {
  274.  
  275.     float value=0.0;
  276.     float Dx, Dy;
  277.  
  278.  
  279.     if (axis == AXIS1) {
  280.        Dx = (float) c1->leg1Dx;
  281.        Dy = (float) c1->leg1Dy;
  282.     } else {
  283.        Dx = (float) c1->leg2Dx;
  284.        Dy = (float) c1->leg2Dy;
  285.     }
  286.  
  287. /**
  288.     value=tokenSupport(c1,c2);
  289.     fprintf(stderr,"Token Value: %f\n",value);
  290.     if (value == 0.0) {
  291.  
  292.       fprintf(stderr,"Image Value: %f\n",value);
  293. **/
  294.        value = support_val(im, c1,image_dir,c2->x,c2->y,Dx,Dy,position, 0);
  295. /**
  296.     }
  297. **/
  298.  
  299.  
  300.     if (value >= MIN_LINE_SUPPORT) {
  301.         return(value);
  302.     }
  303.     else
  304.         return(0.0);
  305. }
  306.   
  307. double perfectY(cList *c1, cList *c2)
  308. {
  309.     mat_4x1 vec1, vec2;
  310.  
  311.     vec1[0] = (double) c1->x;
  312.     vec1[1] = (double) c1->y;
  313.     vec1[2] = 0.0;
  314.     vec1[3] = 1.0;
  315.  
  316.     vec2[0] = (double) c2->x;
  317.     vec2[1] = (double) c2->y;
  318.     vec2[2] = 0.0;
  319.     vec2[3] = 1.0;
  320.  
  321.     /** Project into ideal 3 Space **/
  322.     project_2d_to_3d(IMAGE_NAME,vec1,vec1);
  323.     project_2d_to_3d(IMAGE_NAME,vec2,vec2);
  324.  
  325.         vec1[0] = vec2[0];
  326.     
  327.     project_3d_to_2d(IMAGE_NAME,vec1,vec1);
  328.     return(vec1[1]);
  329. }
  330.  
  331.  
  332.