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 >
Wrap
C/C++ Source or Header
|
1996-03-04
|
14KB
|
687 lines
/*************************************************************************
Christopher Jaynes
January 14, 1995
U.Mass RADIUS project
tours.
Search for all of the possible even-length tours in the graph.
Each tour is a possible roof hypothesis.
Mark each vertex that is part of a tour, create a Meta-vertex
for each tour.
After the tours have been marked, re-search the graph for possible
missing features, hypothesize, and complete new tours.
The final set of rooftops
will be the maximally weighted, subset of independent tours.
Graph G = (V,E).
The algorithm proceeds as follows:
***************************************************************************/
#include "../polygons.h"
#define WHITE 1
#define GREY 2
#define BLACK 3
#define RED 4
#define BLUE 5
#define T 2
#define L 3
int self_intersect(vertexList *p, cList *v);
void add_color(colorList **list, int color)
/* adds the color to a node's color list */
{
colorList *n;
n=(colorList *)malloc(sizeof(colorList));
n->color=color;
n->next = *list;
*list = n;
}
int color_in(int color, colorList *color_list)
{
if (color_list == NULL)
return(0);
else
if (color == color_list->color)
return(1);
else
return(color_in(color, color_list->next));
}
int cycle_exists(vertexList *list, cList *vertex)
/* returns a 1 if there is a chain of the same color from
vertex to vertex (a cycle is already there), otherwise 0 */
{
vertexList *hv;
colorList *hcl;
int cycle_possible;
hcl=vertex->colors;
while (hcl != NULL)
{
hv=list;
cycle_possible=1;
while (cycle_possible && (hv != NULL) && (hv->vertex != vertex))
{
if (!(color_in(hcl->color,hv->vertex->colors)))
cycle_possible=0;
else
hv=hv->next;
}
if (cycle_possible)
return(1);
else
hcl=hcl->next;
}
return(0);
}
void insert_vertex_into_polygon(cList *vertex, vertexList **cycle_list)
{
vertexList *hvl;
hvl=(vertexList *)malloc(sizeof(vertexList));
hvl->vertex=vertex;
hvl->next= *cycle_list;
*cycle_list = hvl;
}
void color_all(vertexList *list, cList *vertex, vertexList **cycle_list,
int color, double *mag, int virt)
/* add a color to all nodes in the list
NOTE: A magnitude of zero, signifies a virtual feature, do not
mark the entries as part of a polygon. */
{
if (list == NULL)
{
return;
}
if (list->vertex == vertex)
{
if (virt)
list->vertex->P = TRUE;
add_color(&(list->vertex->colors),color);
insert_vertex_into_polygon(vertex,cycle_list);
*mag = *mag + vertex->magnitude;
}
else
{
if (virt)
list->vertex->P = TRUE;
add_color(&(list->vertex->colors),color);
insert_vertex_into_polygon(list->vertex,cycle_list);
*mag = *mag + list->vertex->magnitude + list->confidence;
color_all(list->next, vertex, cycle_list, color, mag, virt);
}
}
int in_visited_list(vertexList *vl, cList *v)
{
vertexList *hl;
hl=vl;
while (hl != NULL)
{
if (hl->vertex == v)
return(1);
hl=hl->next;
}
return(0);
}
int even(int number)
{
if ((number % 2) == 0)
return(1);
else
return(0);
}
int dfs_visit(c_handle im, cList *list, int axis, int color, vertexList **visited_list, cList **graph, MGvertex **meta_graph, int depth)
{
edgeList *edges;
int current_color;
vertexList *hb;
vertexList *Cptr;
vertexList *temp;
vertexList *cycle_list;
vertexList *vertPtr; /** List pointer for the visited lsit **/
MGvertex *hmv;
double mag;
float weight; /** Weight of the edge support under the
feature.. **/
colorList *ptr;
int dir;
int i;
/**
for (i=0; i < depth; i++)
fprintf(stderr," :");
fprintf(stderr,"%d %d (",list->x,list->y);
ptr = list->colors;
while (ptr != NULL) {
fprintf(stderr,"%d,",ptr->color);
ptr = ptr->next;
}
fprintf(stderr,")\n");
**/
if (color > MAX_ALLOWED_COLOR)
{
fprintf(stderr,"max color reached, search aborted incomplete \n");
return(color);
}
edges=list->eList;
current_color=color;
/*** Changed to disallow search depth greater than MAXCHAINLEN **/
while (edges != NULL && depth <= MAXCHAINLEN)
{
if (edges->type != axis) {
if (in_visited_list(*visited_list,edges->vertex) &&
!self_intersect(*visited_list,edges->vertex)) {
if (!even(depth - edges->vertex->depth))
{
if (!cycle_exists(*visited_list,edges->vertex))
{
/** A cycle has been detected. Mark the appropriate nodes,
create a meta vertex **/
mag = 0.0;
cycle_list = NULL;
add_color(&(list->colors),current_color);
insert_vertex_into_polygon(list,&cycle_list);
color_all(*visited_list,edges->vertex,&cycle_list,current_color,
&mag,TRUE);
/* create a meta vertex */
hmv=(MGvertex *)malloc(sizeof(MGvertex));
hmv->vList = cycle_list;
hmv->eList = NULL;
hmv->next = *meta_graph;
hmv->color = current_color;
hmv->isscolor = WHITE;
hmv->confidence = mag + list->magnitude;
*meta_graph = hmv;
current_color++;
}
}
}
else {
/** If this edge doesn't cause a self-intersection.. add it
to the chain and continue search. **/
if (!self_intersect(*visited_list,list)) {
hb=(vertexList *)malloc(sizeof(vertexList));
hb->next = *visited_list;
hb->vertex = list;
hb->confidence = edges->confidence;
hb->vertex->depth = depth;
if (*visited_list != NULL)
*visited_list = hb;
else
*visited_list = hb;
current_color=dfs_visit(im, edges->vertex, edges->type,
current_color, visited_list, graph, meta_graph, depth+1);
(*visited_list) = (*visited_list)->next;
free(hb);
}
}
}
edges=edges->next;
}
return(current_color);
}
void tours(c_handle im, cList *v_list,int *curr_color, MGvertex **meta_graph)
/*
*
* Search for tours of even length in a depth first manner using each
* node in the graph as a differnet starting point for the
* depth first search.
*
*
*/
{
vertexList *back_list;
cList *nodes;
back_list=NULL;
nodes=v_list;
/** Initalize the color fields of the nodes. **/
while (nodes != NULL)
{
nodes->colors = NULL;
nodes->P = FALSE;
nodes=nodes->next;
}
nodes=v_list;
*meta_graph = NULL;
while (nodes != NULL)
{
/**
fprintf(stderr,"Cycle Search From: (%d %d)\n",
nodes->x,nodes->y);
**/
*curr_color=dfs_visit(im,nodes,AXIS1,*curr_color,&back_list,
&v_list,meta_graph,0);
/*
fprintf(stderr,"Color Return: %d\n",*curr_color);
*/
nodes=nodes->next;
}
}
int exist_dependency(MGvertex **vertex_arr, int color1, int color2)
{
MGedgeList * el;
el = vertex_arr[color1]->eList;
while (el != NULL)
{
if (el->vertex->color == color2)
return(1);
else
el=el->next;
}
return(0);
}
void build_meta_edge(MGvertex **vertex_arr, int color1, int color2)
{
MGedgeList *he;
/**
fprintf(stderr,"Meta Edge (dependency) between: %d %d\n",color1,color2);
**/
he=(MGedgeList *)malloc(sizeof(MGedgeList));
he->vertex=vertex_arr[color2];
he->next=vertex_arr[color1]->eList;
vertex_arr[color1]->eList=he;
he=(MGedgeList *)malloc(sizeof(MGedgeList));
he->vertex=vertex_arr[color1];
he->next=vertex_arr[color2]->eList;
vertex_arr[color2]->eList=he;
}
void insert_dependency(MGvertex **vertex_arr, int color1, int color2)
{
/*
fprintf(stderr,"entering insert_dependency \n");
*/
if (!exist_dependency(vertex_arr, color1, color2))
build_meta_edge(vertex_arr, color1, color2);
/*
fprintf(stderr,"after insert_dependency \n");
*/
}
void build_dependency_graph(cList *v_list, int color_no, MGvertex *meta_graph)
/* builds a dependency_graph */
{
MGvertex *h;
MGvertex **vertex_arr;
colorList *co;
colorList *hco;
int i;
cList *hv;
vertex_arr=(MGvertex **)malloc(sizeof(MGvertex *)*(color_no));
h=meta_graph;
for (i=color_no-1; i>=0; i--)
{
vertex_arr[i]=h;
h=h->next;
}
/* walk through all the vertices of the old graph and conncect the
vertices that are connected */
/* create a dependency in the meta graph */
hv= v_list;
while (hv != NULL)
{
/* go through the color list */
co=hv->colors;
while (co != NULL)
{
hco=co->next;
while (hco != NULL)
{
/**
fprintf(stderr,"before inserting a dependency between %d %d \n",
co->color,hco->color);
**/
insert_dependency(vertex_arr,co->color,hco->color);
/*
fprintf(stderr,"after inserting a dependency");
*/
hco=hco->next;
}
co=co->next;
}
hv=hv->next;
}
fprintf(stderr,"all dependencies created \n");
}
void dfs_search(MGedgeList *mgraph, MGedgeList **vertex_list,
double *mag, int color)
/*
this function returns the list off all the meta vertices that are in an
independent subset (as parameter)
*/
{
MGedgeList *hel;
MGedgeList *hvl;
MGvertex *vertex;
int neighbors_ok;
if (mgraph == NULL)
{
fprintf(stderr,"mgraph in dfs empty \n");
return;
}
vertex=mgraph->vertex;
hel=vertex->eList;
neighbors_ok=1;
if (color == RED)
{
/* if there are all neighbors not BLUE */
/* this vertex is in the ISS */
while ((hel != NULL) && (neighbors_ok))
{
if (hel->vertex->isscolor == BLUE)
neighbors_ok=0;
hel=hel->next;
}
hel=vertex->eList;
if (neighbors_ok)
{
vertex->isscolor = BLUE;
/*
fprintf(stderr,"coloring a vertex blue \n");
*/
/* include in list of vertices */
hvl=(MGedgeList *)malloc(sizeof(MGedgeList));
hvl->next= *vertex_list;
hvl->vertex=vertex;
*vertex_list = hvl;
*mag= *mag+vertex->confidence;
}
else
{
vertex->isscolor=RED;
/*
fprintf(stderr,"coloring a vertex red \n");
*/
}
}
else
{
/* this vertex is not in the ISS */
vertex->isscolor=RED;
/*
fprintf(stderr,"coloring a vertex red \n");
*/
}
while (hel != NULL)
{
if (hel->vertex->isscolor == WHITE)
dfs_search(hel, vertex_list, mag, vertex->isscolor);
hel=hel->next;
}
if (*vertex_list == NULL)
fprintf(stderr,"vertex_list empty before leaving dfs \n");
}
MGvertexList *indep_subset(MGedgeList *graph)
{
MGedgeList *el;
MGvertexList *iss;
MGedgeList *hel;
double mag;
el=graph;
mag=0;
hel=NULL;
while (el != NULL)
{
if (el->vertex->isscolor == WHITE)
{
dfs_search(el,&hel,&mag,RED);
if (hel == NULL)
fprintf(stderr,"edgelist empty after dfs in iss \n");
}
el=el->next;
}
iss=(MGvertexList *)malloc(sizeof(MGvertexList));
iss->eList=hel;
iss->confidence=mag;
iss->next=NULL;
if (iss->eList == NULL)
fprintf(stderr,"error, eList empty \n");
return(iss);
}
MGvertexList *all_indep_subsets(MGvertex *graph)
{
MGvertex *hg;
MGvertex *hga;
MGedgeList *hmgvl;
MGedgeList *mgvl;
MGvertexList *iss;
MGvertexList *hiss;
MGedgeList *hel;
double mag;
iss = NULL;
hga=graph;
while (hga != NULL)
{
hg=hga;
mgvl=NULL;
while (hg != NULL)
{
hg->isscolor=WHITE;
hmgvl = (MGedgeList *)malloc(sizeof(MGedgeList));
hmgvl->vertex = hg;
hmgvl->next=mgvl;
mgvl=hmgvl;
hg=hg->next;
}
hg=graph;
while ((hg != NULL) && (hg != hga))
{
hg->isscolor=WHITE;
hmgvl = (MGedgeList *)malloc(sizeof(MGedgeList));
hmgvl->vertex = hg;
hmgvl->next=mgvl;
mgvl=hmgvl;
hg=hg->next;
}
hiss=indep_subset(mgvl);
hiss->next=iss;
iss=hiss;
while (mgvl != NULL)
{
hmgvl=mgvl;
mgvl=mgvl->next;
free(hmgvl);
}
hga=hga->next;
}
return(iss);
}
MGvertexList *get_max_iss(MGvertexList *vertex_list)
{
double max;
MGvertexList *hvl;
MGvertexList *r;
max = 0;
hvl = vertex_list;
r=hvl;
while (hvl != NULL)
{
if (hvl->confidence > max)
{
max=hvl->confidence;
r=hvl;
}
hvl=hvl->next;
}
return(r);
}
print_tabs(int d)
{
int i;
if (d == 0)
fprintf(stderr,"START DFS\n ");
for (i=0; i < d; i++)
fprintf(stderr," ");
}
int self_intersect(vertexList *p, cList *v)
/*
* Does the addition of vertex 'v' to path 'p' create a self-intersecting
* curve ??
*
*
*/
{
double_2 Ipoint;
line l;
line testLine;
double Parms[2];
vertexList *ptr;
double angleError = 3.13;
if (p == NULL)
return(FALSE);
/* Make a line between the vertex 'v' and the last visited
node. Check to see if this line intersects any other
line in the path */
l.x1 = v->x; l.y1 = v->y;
l.x2 = p->vertex->x; l.y2 = p->vertex->y;
/** Move through all other possible lines **/
ptr = p;
while (ptr->next != NULL) {
testLine.x1 = ptr->vertex->x; testLine.y1 = ptr->vertex->y;
testLine.x2 = ptr->next->vertex->x; testLine.y2 = ptr->next->vertex->y;
intersect_point(l,testLine,&Ipoint);
computeParms(Ipoint,l,testLine,Parms);
if (Parms[0] > 0.0 && Parms[0] < 1.0 && Parms[1] > 0.0 &&
Parms[1] < 1.0) {
return(TRUE);
}
ptr = ptr->next;
}
return(FALSE);
}