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 / virtualTours.c < prev   
C/C++ Source or Header  |  1996-05-30  |  8KB  |  311 lines
  1. /*************************************************************************
  2.  
  3.  
  4.    Christopher Jaynes
  5.    Feb 6, 1995
  6.    U.Mass RADIUS project
  7.  
  8.  
  9.    virtualTours
  10.  
  11.    After all of the feature tours (polygon hypotheses) have been detected,
  12.    search for tours that can be completed with a single missing feature
  13.    ie- nodes separated by 1 relation in the Feature Relation Graph.
  14.    Generate a virtual feature, check for support in the image, and
  15.    add it to the graph.
  16.  
  17. ***************************************************************************/
  18.  
  19.  
  20. #include "../polygons.h"
  21.  
  22. #define WHITE    1
  23. #define GREY    2
  24. #define BLACK    3    
  25. #define RED     4
  26. #define BLUE    5
  27.  
  28.  
  29. #define T    2
  30. #define L    3
  31.  
  32. int virtualSelf_intersect(vertexList *p, cList *virtual,cList *e1, cList *e2);
  33. cList *createVirtualFeature(cList *first, cList *next,Point p, double weight);
  34.  
  35.  
  36. void virtualTours(c_handle im, cList *v_list, int *curr_color,
  37.                                                         MGvertex **meta_graph)
  38. /*
  39.  * Once all of the tours have been detected in the Feature Relation
  40.  * Graph.  Perform a tour search again, this time, attempt to generate
  41.  * virtual features between existing node that will complete cycles.
  42.  *
  43.  * Virtual features cannot be generated between nodes that are both
  44.  * in the same cycle.
  45.  *
  46.  */
  47. {
  48.         vertexList *back_list;
  49.         cList *nodes;
  50.          
  51.         back_list=NULL;
  52.         nodes=v_list;
  53.  
  54.         while (nodes != NULL)
  55.         {
  56.                 *curr_color=virtualTour(im,nodes,AXIS1,*curr_color,&back_list,
  57.                                  &v_list,meta_graph,0);
  58.  
  59.                 nodes=nodes->next;
  60.         }
  61. }
  62.  
  63.  
  64. int virtualTour(c_handle im, cList *list, int axis, int color, vertexList **visited_list, cList **graph, MGvertex **meta_graph, int depth)
  65.      
  66. {
  67.  
  68.   edgeList *edges;
  69.   int current_color;
  70.   vertexList *hb;
  71.   vertexList *cycle_list;
  72.   vertexList *Vptr;
  73.   vertexList *tempPtr;
  74.   vertexList *first;        /** List pointer for the visited lsit **/
  75.   MGvertex *hmv;
  76.   double mag;
  77.   double weight, weight1, weight2;
  78.   int  virtualFeature=FALSE;
  79.   double height;
  80.   Point gPoint;  
  81.   colorList *ptr;
  82.   vertexList *pt;
  83.  
  84.   int fDepth;
  85.   int dir;
  86.   cList *vNode;
  87.   int i;
  88.  
  89.   if (color > MAX_ALLOWED_COLOR)
  90.   {
  91.     fprintf(stderr,"max color reached, search aborted incomplete \n");
  92.     return(color);
  93.   }
  94.  
  95.   edges=list->eList;
  96.   current_color=color;
  97.  
  98.   /*** Changed to disallow search depth greater than MAXCHAINLEN **/
  99.   while (edges != NULL && depth <= MAXCHAINLEN)    
  100.   {
  101.     /* Follow a different axis out of the current node **/
  102.     if (edges->type != axis)  {
  103.       if (!in_visited_list(*visited_list,edges->vertex) &&
  104.           !self_intersect(*visited_list,edges->vertex)) {  
  105.  
  106.       hb=(vertexList *)malloc(sizeof(vertexList));
  107.           hb->next = *visited_list;
  108.           hb->vertex = list;
  109.           hb->confidence = edges->confidence;
  110.           hb->vertex->depth = depth;
  111.              *visited_list = hb;
  112.  
  113.           fDepth = depth+1;
  114.         if ((fDepth > 1) && !(fDepth % 2)) {
  115.         first = *visited_list;  /* Set first node in visited list */
  116.         while (first->next != NULL){
  117.           first = first->next;
  118.     
  119.         }
  120.  
  121.           /** The first and last nodes must be at least 1
  122.            node apart for virtual feature production.  Also,
  123.            the current node cannot take part in a virtual cycle. **/
  124.           if ( ((fDepth - first->vertex->depth > 1) &&
  125.          (edges->vertex->P != TRUE || first->vertex->P != TRUE)) ) {
  126.         
  127.         if (!K_CYCLES || ((edges->vertex->P != TRUE) &&
  128.             first->vertex->P != TRUE)) {
  129.     
  130.         
  131.           gPoint = TfeatureGap(edges->vertex,edges->type,first->vertex);
  132.           if (goodFeature(gPoint) ) {
  133.             /** Valid corner, now see if there is enough 
  134.             image support/
  135.             if ( (weight1 =virtualTokenSupport(gPoint,edges->vertex)) &&
  136.                  (weight2 =virtualTokenSupport(gPoint,first->vertex))) {
  137.                  weight = weight1+weight2;
  138.                 virtualFeature=TRUE;
  139.             } else **/
  140.             if ( (weight = 
  141.              virtualSupport(im,&gPoint,edges->vertex, edges->type,
  142.               first->vertex,&dir)))  {
  143.                 virtualFeature = TRUE;
  144.             }
  145.             else {
  146.                 virtualFeature = FALSE;
  147.            }
  148.             
  149.              if (virtualFeature) {
  150.  
  151.             vNode = createVirtualFeature(first->vertex,
  152.                         edges->vertex, gPoint,0.0);
  153.             
  154.             if (virtualSelf_intersect(*visited_list, vNode,
  155.                edges->vertex,first->vertex)){
  156.                 free(vNode);
  157.             }
  158.             else {  /* Good feature, add this polygon */
  159.                             vNode->next = *graph;
  160.                             *graph = vNode;
  161.                            cycle_list = NULL; mag = 0.0;
  162.                             add_color(&(edges->vertex->colors),current_color);
  163.                           add_color(&(list->colors),current_color);
  164.                           add_color(&(vNode->colors),current_color);
  165.                            insert_vertex_into_polygon(vNode,&cycle_list);
  166.                            insert_vertex_into_polygon(edges->vertex,&cycle_list);
  167.                    /*        insert_vertex_into_polygon(list,&cycle_list);
  168.             */
  169.                           color_all(*visited_list,NULL,&cycle_list,
  170.                         current_color,&mag,TRUE);
  171.                           hmv=(MGvertex *)malloc(sizeof(MGvertex));
  172.                           hmv->vList = cycle_list;
  173.                           hmv->eList = NULL;
  174.                           hmv->next = *meta_graph;
  175.                           hmv->color = current_color;
  176.                           hmv->isscolor = WHITE;
  177.                           hmv->confidence = mag + edges->vertex->magnitude
  178.                             + edges->confidence
  179.                                             + list->magnitude
  180.                                             + vNode->magnitude;
  181.                           *meta_graph = hmv;
  182.               current_color++;
  183.             } /* No self intersection */
  184.               } /* Enough Support */
  185.            } /* Good Feature (in boundaries) */
  186.          }
  187.             } /* Deep enough, vertex not already in polygon */
  188.          } /* Valid even depth */
  189.  
  190.  
  191.          current_color = virtualTour(im, edges->vertex, edges->type,
  192.                 current_color,visited_list,graph,meta_graph,
  193.                 depth+1);
  194.          (*visited_list) = (*visited_list)->next;
  195.          free(hb);
  196.     } /** In visited list **/
  197.       } /** Correct Axis **/
  198.       edges = edges->next;
  199.    } /* While */
  200.  
  201.    return(current_color);
  202.  
  203. }
  204.  
  205. int virtualSelf_intersect(vertexList *p, cList *v, cList *end1, cList *end2)
  206. /*
  207.  * 
  208.  * Return TRUE if there is an intersection between the new virtual
  209.  * feature and any of the other lines between nodes in the visited
  210.  * list.
  211.  * Return FALSE otherwise.
  212.  *
  213.  */
  214.  
  215.  
  216. {
  217.  
  218.     line l;
  219.         line testLine;
  220.         double Parms[2];
  221.     double_2 Ipoint;
  222.         vertexList *ptr;
  223.     double_2 *res;
  224.     double angleError = 3.13;
  225.  
  226.         if (p == NULL)
  227.                 return(FALSE);
  228.  
  229.  
  230.         /* Make a line between the vertex 'virtual' and the last visited
  231.            node.  Check to see if this line intersects any other
  232.            line in the path */
  233.         l.x1 = v->x; l.y1 = v->y;
  234.         l.x2 = end1->x; l.y2 = end1->y;
  235.  
  236.         /** Move through all other possible lines **/
  237.         ptr = p;
  238.         while (ptr->next != NULL && ptr->vertex != NULL) {
  239.             testLine.x1 = ptr->vertex->x; testLine.y1 = ptr->vertex->y;
  240.             testLine.x2 = ptr->next->vertex->x;
  241.         testLine.y2 = ptr->next->vertex->y;
  242.     
  243.         intersect_point(l,testLine,&Ipoint);
  244.         computeParms(Ipoint,l,testLine,Parms);
  245.  
  246.         if (Parms[0] > 0.0 && Parms[0] < 1.0 && Parms[1] > 0.0
  247.         && Parms[1] < 1.0) {
  248.                         return(TRUE);
  249.         }
  250.  
  251.         ptr = ptr->next;
  252.     }
  253.  
  254.         l.x1 = v->x; l.y1 = v->y;
  255.         l.x2 = end2->x; l.y2 = end2->y;
  256.         ptr = p;
  257.         while (ptr->next != NULL && ptr->vertex != NULL) {
  258.             testLine.x1 = ptr->vertex->x; testLine.y1 = ptr->vertex->y;
  259.             testLine.x2 = ptr->next->vertex->x;
  260.         testLine.y2 = ptr->next->vertex->y;
  261.  
  262.         intersect_point(l,testLine,&Ipoint);
  263.         computeParms(Ipoint,l,testLine,Parms);
  264.  
  265.         if (Parms[0] > 0.0 && Parms[0] < 1.0 && Parms[1] > 0.0
  266.         && Parms[1] < 1.0) {
  267.             free(res);
  268.                         return(TRUE);
  269.         }
  270.  
  271.         ptr = ptr->next;
  272.     }
  273.     
  274.     
  275.  
  276.  
  277.     return(FALSE);
  278. }
  279.  
  280.  
  281. cList *createVirtualFeature(cList *first, cList *next,Point p, double weight)
  282. {
  283.  
  284.     cList *v;
  285.  
  286.  
  287.     v = (cList *) malloc( sizeof(cList));
  288.     v->x = (int) p.x;
  289.     v->y = (int) p.y;
  290.     v->height = (first->height + next->height)/2.0;
  291.     v->magnitude = weight;
  292.     v->colors = NULL;
  293.     v->next = NULL;
  294.  
  295.     return(v);
  296. }
  297.  
  298.  
  299.  
  300. int goodFeature(Point p)
  301. {
  302.  
  303.    if ( (p.x > xstart && p.y > ystart && p.x < xstop && p.y < ystop) &&
  304.         p.z != NONE)
  305.         return(TRUE);
  306.     
  307.     
  308.    return(FALSE);
  309. }
  310.     
  311.