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 / tours.c < prev    next >
C/C++ Source or Header  |  1996-03-04  |  14KB  |  687 lines
  1. /*************************************************************************
  2.  
  3.  
  4.    Christopher Jaynes
  5.    January 14, 1995
  6.    U.Mass RADIUS project
  7.  
  8.  
  9.    tours.
  10.  
  11.    Search for all of the possible even-length tours in the graph.
  12.    Each tour is a possible roof hypothesis.
  13.    Mark each vertex that is part of a tour, create a Meta-vertex
  14.    for each  tour.
  15.  
  16.    After the tours have been marked, re-search the graph for possible
  17.    missing features, hypothesize, and complete new tours.
  18.  
  19.    The final set of rooftops
  20.    will be the maximally weighted, subset of independent tours.
  21.  
  22.    Graph G = (V,E).  
  23.  
  24.    The algorithm proceeds as follows:
  25.  
  26.  
  27. ***************************************************************************/
  28.  
  29.  
  30. #include "../polygons.h"
  31.  
  32. #define WHITE    1
  33. #define GREY    2
  34. #define BLACK    3    
  35. #define RED     4
  36. #define BLUE    5
  37.  
  38.  
  39. #define T    2
  40. #define L    3
  41.  
  42. int self_intersect(vertexList *p, cList *v);
  43.  
  44. void add_color(colorList **list, int color)
  45.  
  46. /* adds the color to a node's color list */
  47. {
  48.   colorList *n;
  49.  
  50.   n=(colorList *)malloc(sizeof(colorList)); 
  51.   n->color=color;
  52.   n->next = *list;    
  53.   *list = n; 
  54. }
  55.  
  56.  
  57. int color_in(int color, colorList *color_list)
  58. {
  59.   if (color_list == NULL)
  60.     return(0);
  61.   else
  62.     if (color == color_list->color)
  63.       return(1);
  64.     else  
  65.       return(color_in(color, color_list->next)); 
  66. }
  67.  
  68.  
  69. int cycle_exists(vertexList *list, cList *vertex)
  70. /* returns a 1 if there is a chain of the same color from
  71.    vertex to vertex (a cycle is already there), otherwise 0 */
  72. {
  73.   vertexList *hv;
  74.   colorList *hcl;
  75.   int cycle_possible;
  76.  
  77.  
  78.   hcl=vertex->colors;
  79.  
  80.   while (hcl != NULL)
  81.   {
  82.     hv=list;
  83.     cycle_possible=1;
  84.     while (cycle_possible && (hv != NULL) && (hv->vertex != vertex))
  85.     {
  86.       if (!(color_in(hcl->color,hv->vertex->colors)))
  87.         cycle_possible=0;    
  88.       else
  89.         hv=hv->next;
  90.  
  91.     }
  92.     if (cycle_possible) 
  93.       return(1);
  94.     else
  95.       hcl=hcl->next;
  96.   }
  97.   return(0);
  98. }
  99.  
  100.  
  101. void insert_vertex_into_polygon(cList *vertex, vertexList **cycle_list)
  102. {
  103.   vertexList *hvl;
  104.  
  105.   hvl=(vertexList *)malloc(sizeof(vertexList));
  106.   hvl->vertex=vertex;
  107.   hvl->next= *cycle_list;
  108.   *cycle_list = hvl;
  109. }
  110.  
  111.  
  112. void color_all(vertexList *list, cList *vertex, vertexList **cycle_list, 
  113.                int color, double *mag, int virt)
  114.  
  115. /* add a color to all nodes in the list 
  116.    NOTE:  A magnitude of zero, signifies a virtual feature, do not 
  117.           mark the entries as part of a polygon. */
  118. {
  119.  
  120.   if (list == NULL)
  121.   {
  122.     return;
  123.   }
  124.   if (list->vertex == vertex)
  125.   {
  126.     if (virt)
  127.     list->vertex->P = TRUE;
  128.     add_color(&(list->vertex->colors),color); 
  129.     insert_vertex_into_polygon(vertex,cycle_list);
  130.     *mag = *mag + vertex->magnitude; 
  131.  
  132.   }
  133.   else
  134.   {
  135.  
  136.     if (virt)
  137.     list->vertex->P = TRUE;
  138.     add_color(&(list->vertex->colors),color); 
  139.     insert_vertex_into_polygon(list->vertex,cycle_list);
  140.     *mag = *mag + list->vertex->magnitude + list->confidence; 
  141.     color_all(list->next, vertex, cycle_list, color, mag, virt); 
  142.  
  143.   }
  144. }
  145.  
  146.  
  147.  
  148.  
  149. int in_visited_list(vertexList *vl, cList *v)
  150. {
  151.   vertexList *hl;
  152.  
  153.   hl=vl;
  154.   while (hl != NULL)
  155.   {
  156.     if (hl->vertex == v)
  157.       return(1);
  158.     hl=hl->next;
  159.   }
  160.   return(0);
  161. }
  162.  
  163.  
  164. int even(int number)
  165. {
  166.   if ((number % 2) == 0)
  167.     return(1);
  168.   else
  169.     return(0);
  170. }
  171.  
  172.  
  173. int dfs_visit(c_handle im, cList *list, int axis, int color, vertexList **visited_list, cList **graph, MGvertex **meta_graph, int depth)
  174.      
  175. {
  176.  
  177.   edgeList *edges;
  178.   int current_color;
  179.   vertexList *hb;
  180.   vertexList *Cptr;
  181.   vertexList *temp;
  182.   vertexList *cycle_list;
  183.   vertexList *vertPtr;        /** List pointer for the visited lsit **/
  184.   MGvertex *hmv;
  185.   double mag;
  186.   float weight;            /** Weight of the edge support under the 
  187.                       feature.. **/
  188.   colorList *ptr;
  189.   int dir;
  190.   int i;
  191.  
  192. /**
  193.   for (i=0; i < depth; i++)
  194.     fprintf(stderr,"  :");
  195.   fprintf(stderr,"%d %d (",list->x,list->y);
  196.   ptr = list->colors;
  197.   while (ptr != NULL) {
  198.     fprintf(stderr,"%d,",ptr->color);
  199.     ptr = ptr->next;
  200.   }
  201.   fprintf(stderr,")\n");
  202. **/
  203.   
  204.   if (color > MAX_ALLOWED_COLOR)
  205.   {
  206.     fprintf(stderr,"max color reached, search aborted incomplete \n");
  207.     return(color);
  208.   }
  209.  
  210.   edges=list->eList;
  211.   current_color=color;
  212.  
  213.   /*** Changed to disallow search depth greater than MAXCHAINLEN **/
  214.   while (edges != NULL && depth <= MAXCHAINLEN)    
  215.   {
  216.     if (edges->type != axis) {
  217.       if (in_visited_list(*visited_list,edges->vertex) &&
  218.      !self_intersect(*visited_list,edges->vertex))  {
  219.         if (!even(depth - edges->vertex->depth)) 
  220.         {
  221.           if (!cycle_exists(*visited_list,edges->vertex))
  222.           {
  223.     
  224.         /** A cycle has been detected.  Mark the appropriate nodes,
  225.             create a meta vertex **/
  226.             mag = 0.0;
  227.             cycle_list = NULL;
  228.  
  229.         add_color(&(list->colors),current_color);
  230.  
  231.             insert_vertex_into_polygon(list,&cycle_list);
  232.             color_all(*visited_list,edges->vertex,&cycle_list,current_color,
  233.                 &mag,TRUE);
  234.  
  235.  
  236.             /* create a meta vertex */
  237.  
  238.             hmv=(MGvertex *)malloc(sizeof(MGvertex));
  239.             hmv->vList = cycle_list;
  240.             hmv->eList = NULL;
  241.             hmv->next = *meta_graph; 
  242.             hmv->color = current_color;
  243.             hmv->isscolor = WHITE;
  244.             hmv->confidence = mag + list->magnitude; 
  245.             *meta_graph = hmv;
  246.     
  247.  
  248.  
  249.             current_color++; 
  250.     
  251.         
  252.           }
  253.           
  254.         }
  255.       }
  256.       else {
  257.     /** If this edge doesn't cause a self-intersection.. add it 
  258.           to the chain and continue search. **/
  259.         if (!self_intersect(*visited_list,list)) {  
  260.        hb=(vertexList *)malloc(sizeof(vertexList));
  261.            hb->next = *visited_list;
  262.            hb->vertex = list;
  263.            hb->confidence = edges->confidence;
  264.            hb->vertex->depth = depth;
  265.            if (*visited_list != NULL)
  266.              *visited_list = hb; 
  267.            else
  268.              *visited_list = hb;
  269.            current_color=dfs_visit(im, edges->vertex, edges->type,
  270.                                  current_color, visited_list, graph, meta_graph,                                 depth+1);
  271.            (*visited_list) = (*visited_list)->next;
  272.            free(hb);
  273.     }
  274.       }
  275.     }
  276.     edges=edges->next;
  277.   }
  278.   return(current_color);
  279. }
  280.  
  281.  
  282. void tours(c_handle im, cList *v_list,int *curr_color, MGvertex **meta_graph)
  283. /* 
  284.  * 
  285.  * Search for tours of even length in a depth first manner using each
  286.  * node in the graph as a differnet starting point for the 
  287.  * depth first search.
  288.  *
  289.  *
  290.  */
  291. {
  292.  
  293.       vertexList *back_list;
  294.       cList *nodes;
  295.         
  296.       back_list=NULL;
  297.       nodes=v_list;
  298.  
  299.       /** Initalize the color fields of the nodes. **/
  300.       while (nodes != NULL)
  301.       {
  302.            nodes->colors = NULL;
  303.        nodes->P = FALSE;
  304.            nodes=nodes->next;
  305.       }
  306.   
  307.       nodes=v_list;
  308.       *meta_graph = NULL;
  309.  
  310.       while (nodes != NULL)
  311.       {
  312. /**
  313.         fprintf(stderr,"Cycle Search From: (%d %d)\n",
  314.                     nodes->x,nodes->y);
  315. **/
  316.             *curr_color=dfs_visit(im,nodes,AXIS1,*curr_color,&back_list,
  317.                  &v_list,meta_graph,0);
  318. /*
  319.         fprintf(stderr,"Color Return: %d\n",*curr_color);
  320. */
  321.             nodes=nodes->next;
  322.       }
  323. }
  324.  
  325.  
  326. int exist_dependency(MGvertex **vertex_arr, int color1, int color2)
  327. {
  328.   MGedgeList * el; 
  329.  
  330.   el = vertex_arr[color1]->eList; 
  331.   while (el != NULL)
  332.   {
  333.     if (el->vertex->color == color2)
  334.       return(1);
  335.     else
  336.       el=el->next;
  337.   } 
  338.  
  339.   return(0);
  340. }
  341.  
  342.  
  343. void build_meta_edge(MGvertex **vertex_arr, int color1, int color2)
  344. {
  345.   MGedgeList *he;
  346.  
  347.  
  348.  
  349. /**
  350.   fprintf(stderr,"Meta Edge (dependency) between: %d %d\n",color1,color2);
  351. **/
  352.  
  353.   he=(MGedgeList *)malloc(sizeof(MGedgeList));
  354.   he->vertex=vertex_arr[color2];
  355.   he->next=vertex_arr[color1]->eList;
  356.   vertex_arr[color1]->eList=he; 
  357.  
  358.   he=(MGedgeList *)malloc(sizeof(MGedgeList));
  359.   he->vertex=vertex_arr[color1];
  360.   he->next=vertex_arr[color2]->eList;
  361.   vertex_arr[color2]->eList=he; 
  362.  
  363. }    
  364.  
  365.  
  366. void insert_dependency(MGvertex **vertex_arr, int color1, int color2)
  367. {
  368. /*
  369.   fprintf(stderr,"entering insert_dependency \n");
  370. */
  371.   if (!exist_dependency(vertex_arr, color1, color2))
  372.     build_meta_edge(vertex_arr, color1, color2); 
  373. /*
  374.   fprintf(stderr,"after insert_dependency \n");
  375. */
  376. }
  377.  
  378. void build_dependency_graph(cList *v_list, int color_no, MGvertex *meta_graph)
  379.  
  380. /* builds a dependency_graph */
  381. {
  382.   MGvertex *h;
  383.   MGvertex **vertex_arr;
  384.   colorList *co;
  385.   colorList *hco;
  386.   int i;
  387.   cList *hv;
  388.  
  389.  
  390.   vertex_arr=(MGvertex **)malloc(sizeof(MGvertex *)*(color_no));
  391.  
  392.   
  393.   h=meta_graph;
  394.  
  395.   for (i=color_no-1; i>=0; i--)
  396.   {
  397.     vertex_arr[i]=h;
  398.     h=h->next;
  399.   } 
  400.  
  401.   /* walk through all the vertices of the old graph and conncect the 
  402.      vertices that are connected */
  403.  
  404.  
  405.   /* create a dependency in the meta graph */
  406.  
  407.   hv= v_list; 
  408.   while (hv != NULL)
  409.   {
  410.     /* go through the color list */
  411.     co=hv->colors;
  412.     while (co != NULL) 
  413.     {
  414.       hco=co->next;
  415.       while (hco != NULL)
  416.       {
  417. /**
  418.         fprintf(stderr,"before inserting a dependency between %d %d \n",
  419.         co->color,hco->color);
  420. **/
  421.         insert_dependency(vertex_arr,co->color,hco->color);
  422. /*
  423.         fprintf(stderr,"after inserting a dependency");
  424. */
  425.         hco=hco->next;
  426.       } 
  427.       co=co->next;
  428.     }
  429.     hv=hv->next;
  430.   } 
  431.  
  432.   fprintf(stderr,"all dependencies created \n");
  433. }
  434.  
  435.  
  436. void dfs_search(MGedgeList *mgraph, MGedgeList **vertex_list, 
  437.                 double *mag, int color) 
  438. /*
  439.   this function returns the list off all the meta vertices that are in an
  440.   independent subset (as parameter) 
  441. */
  442. {
  443.   MGedgeList *hel;
  444.   MGedgeList *hvl; 
  445.   MGvertex *vertex;
  446.   int neighbors_ok;
  447.  
  448.   if (mgraph == NULL)
  449.   {
  450.     fprintf(stderr,"mgraph in dfs empty \n");
  451.     return;
  452.   }
  453.   vertex=mgraph->vertex; 
  454.   hel=vertex->eList;
  455.   neighbors_ok=1;
  456.  
  457.   if (color == RED)
  458.   {
  459.     /* if there are all neighbors not BLUE */  
  460.     /* this vertex is in the ISS */ 
  461.     
  462.     while ((hel != NULL) && (neighbors_ok))
  463.     {
  464.       if (hel->vertex->isscolor == BLUE)
  465.         neighbors_ok=0;
  466.       hel=hel->next;
  467.     }
  468.     hel=vertex->eList; 
  469.     if (neighbors_ok)
  470.     {
  471.       vertex->isscolor = BLUE;
  472.  
  473. /*
  474.       fprintf(stderr,"coloring a vertex blue \n");
  475. */
  476.  
  477.       /* include in list of vertices */
  478.   
  479.       hvl=(MGedgeList *)malloc(sizeof(MGedgeList));
  480.       hvl->next= *vertex_list;
  481.       hvl->vertex=vertex;
  482.       *vertex_list = hvl; 
  483.       *mag= *mag+vertex->confidence;  
  484.     }
  485.     else
  486.     {
  487.       vertex->isscolor=RED;
  488. /*
  489.       fprintf(stderr,"coloring a vertex red \n");
  490. */
  491.     }
  492.   }
  493.   else 
  494.   {
  495.     /* this vertex is not in the ISS */
  496.     vertex->isscolor=RED;
  497. /*
  498.     fprintf(stderr,"coloring a vertex red \n");
  499. */
  500.   }
  501.  
  502.   while (hel != NULL) 
  503.   {
  504.     if (hel->vertex->isscolor == WHITE)
  505.       dfs_search(hel, vertex_list, mag, vertex->isscolor); 
  506.     hel=hel->next; 
  507.   }
  508.   if (*vertex_list == NULL)
  509.     fprintf(stderr,"vertex_list empty before leaving dfs \n");
  510. }
  511.  
  512.  
  513. MGvertexList *indep_subset(MGedgeList *graph)
  514. {
  515.  
  516.   MGedgeList *el;
  517.   MGvertexList *iss;
  518.   MGedgeList *hel;
  519.   double mag;
  520.  
  521.     
  522.   el=graph;  
  523.   mag=0;
  524.   hel=NULL;
  525.   while (el != NULL) 
  526.   {
  527.     if (el->vertex->isscolor == WHITE)
  528.     {
  529.       dfs_search(el,&hel,&mag,RED);
  530.       if (hel == NULL)
  531.         fprintf(stderr,"edgelist empty after dfs in iss  \n");
  532.     }
  533.     el=el->next;
  534.   }
  535.     
  536.   iss=(MGvertexList *)malloc(sizeof(MGvertexList));
  537.   iss->eList=hel;
  538.   iss->confidence=mag;
  539.   iss->next=NULL;
  540.   if (iss->eList == NULL)
  541.     fprintf(stderr,"error, eList empty \n");
  542.   return(iss);
  543. }
  544.  
  545.  
  546. MGvertexList *all_indep_subsets(MGvertex *graph)
  547.  
  548. {
  549.  
  550.   MGvertex *hg;
  551.   MGvertex *hga;
  552.   MGedgeList *hmgvl;
  553.   MGedgeList *mgvl;
  554.   MGvertexList *iss;
  555.   MGvertexList *hiss;
  556.   MGedgeList *hel;
  557.   double mag;
  558.  
  559.     
  560.   iss = NULL;
  561.   hga=graph;
  562.   while (hga != NULL) 
  563.   {  
  564.     hg=hga;
  565.     mgvl=NULL;
  566.     while (hg != NULL)
  567.     {
  568.       hg->isscolor=WHITE;
  569.       hmgvl = (MGedgeList *)malloc(sizeof(MGedgeList));
  570.       hmgvl->vertex = hg;
  571.       hmgvl->next=mgvl; 
  572.       mgvl=hmgvl;
  573.       hg=hg->next;
  574.     }
  575.     hg=graph;
  576.     while ((hg != NULL) && (hg != hga))
  577.     {
  578.       hg->isscolor=WHITE;
  579.       hmgvl = (MGedgeList *)malloc(sizeof(MGedgeList));
  580.       hmgvl->vertex = hg;
  581.       hmgvl->next=mgvl; 
  582.       mgvl=hmgvl;
  583.       hg=hg->next;
  584.     }
  585.     
  586.     
  587.     hiss=indep_subset(mgvl);
  588.     hiss->next=iss;
  589.     iss=hiss;
  590.  
  591.     while (mgvl != NULL)
  592.     {
  593.       hmgvl=mgvl;
  594.       mgvl=mgvl->next;
  595.       free(hmgvl);
  596.     }
  597.     hga=hga->next;
  598.   }
  599.   return(iss);
  600. }
  601.  
  602.  
  603.  
  604. MGvertexList *get_max_iss(MGvertexList *vertex_list)
  605. {
  606.   double max;
  607.   MGvertexList *hvl;
  608.   MGvertexList *r;
  609.  
  610.   max = 0;
  611.   hvl = vertex_list;
  612.  
  613.   r=hvl;
  614.   while (hvl != NULL)  
  615.   {
  616.     if (hvl->confidence > max)
  617.     {
  618.       max=hvl->confidence;
  619.       r=hvl;
  620.     }
  621.     hvl=hvl->next;
  622.   }
  623.   return(r);
  624. }
  625.  
  626.  
  627. print_tabs(int d)
  628. {
  629.  
  630.     int i;
  631.  
  632.     if (d == 0) 
  633.         fprintf(stderr,"START DFS\n ");
  634.     for (i=0; i < d; i++)
  635.         fprintf(stderr,"  ");
  636. }
  637.  
  638.  
  639. int self_intersect(vertexList *p, cList *v)
  640. /* 
  641.  * Does the addition of vertex 'v' to path 'p' create a self-intersecting
  642.  * curve ??
  643.  *
  644.  *
  645.  */
  646. {
  647.  
  648.     double_2 Ipoint;
  649.     line l;
  650.     line testLine;
  651.     double Parms[2];
  652.     vertexList *ptr;
  653.     double angleError = 3.13;
  654.  
  655.     if (p == NULL) 
  656.         return(FALSE);
  657.  
  658.  
  659.  
  660.     /* Make a line between the vertex 'v' and the last visited
  661.        node.  Check to see if this line intersects any other 
  662.        line in the path */
  663.     l.x1 = v->x; l.y1 = v->y;
  664.     l.x2 = p->vertex->x; l.y2 = p->vertex->y;
  665.     
  666.     /** Move through all other possible lines **/
  667.     ptr = p;
  668.     while (ptr->next != NULL) {
  669.  
  670.  
  671.         testLine.x1 = ptr->vertex->x; testLine.y1 = ptr->vertex->y;
  672.         testLine.x2 = ptr->next->vertex->x; testLine.y2 = ptr->next->vertex->y;
  673.  
  674.         intersect_point(l,testLine,&Ipoint);
  675.         computeParms(Ipoint,l,testLine,Parms);
  676.  
  677.         if (Parms[0] > 0.0 && Parms[0] < 1.0 && Parms[1] > 0.0 &&
  678.             Parms[1] < 1.0) {
  679.            return(TRUE);
  680.         }
  681.        
  682.         ptr = ptr->next;
  683.     }
  684.  
  685.     return(FALSE);
  686. }
  687.