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 >
Wrap
C/C++ Source or Header
|
1994-01-25
|
6KB
|
332 lines
#include "../polygons.h"
/***************************************************************************
buildGraph
Takes a corner list and the 2D corner array, builds the corner
hypothesis graph. Each vertex in the graph represents a
corner, each edge a valid link.
G = (V,E)
V in G if V in corner Set.
E =(u,v). If Corner u has an axis that points at v and vise-versa.
And the "edge support" > MIN_EDGE SUPPORT.
This graph will contain all the possible legal groupings. Note:
the SSC of G will be probable rooftops.
*****************************************************************************/
void buildGraph(cList *list,c_handle im, c_handle pane)
{
cList *ptr;
int count=0;
ptr = list;
if (ptr == NULL)
return;
/** Move through the list, check if an edge should exist. ***/
while (ptr->next != NULL) {
count += buildEdges(ptr, ptr->next, im, pane);
ptr = ptr->next;
}
fprintf(stderr,"Built %d edges in the FRG\n",count);
}
int buildEdges(cList *ptr, cList *list, c_handle im, c_handle pane)
{
cList *candidate;
float str;
int built=0;
int pos;
int dir;
int ax;
candidate = list;
while (candidate != NULL) {
/*** Attempt to fit either axis to the candiate. If no edge
exists and the corners are compatible, create one. ***/
if ( (!linkedByEdge(ptr,candidate)) &&
(ax = cornersCompatible(ptr,candidate))) {
if ( (str = enoughSupport(im,ptr,candidate,ax,&pos, &dir))) {
buildEdge(ptr,candidate,str, ax, pane, pos, dir);
built++;
}
else
if ( (str = enoughSupport(im,candidate,ptr,ax,&pos, &dir))) {
buildEdge(ptr,candidate,str, ax, pane, pos, dir);
built++;
}
}
candidate = candidate->next;
}
return(built);
}
int
buildEdge(cList *v1, cList *v2, float str, int axis, c_handle pane, int pos, int dir)
{
edgeList *edge;
edgeList *newEdge;
double_2 *p1, *p2;
double_2 *temp1, *temp2;
temp1 = (double_2 *) transform_point(view_trans,(double)v1->x,
(double)v1->y,0);
temp2 = (double_2 *) transform_point(view_trans,(double)v2->x,
(double)v2->y,0);
p1 = (double_2 *) inverse_transform_point(image_trans,
(double)temp1->d1,(double)temp1->d2,0);
p2 = (double_2 *) inverse_transform_point(image_trans,
(double)temp2->d1, (double)temp2->d2,0);
draw_fat_line(pane,p1->d1,p1->d2,p2->d1,p2->d2,2.0);
flush_display(pane);
newEdge = (edgeList *) malloc(sizeof(edgeList));
edge = v1->eList;
v1->eList = newEdge;
v1->eList->confidence = str;
v1->eList->type = axis;
v1->eList->vertex = v2;
v1->eList->position = pos;
v1->eList->dir = dir;
v1->eList->next = edge;
newEdge = (edgeList *) malloc(sizeof(edgeList));
edge = v2->eList;
v2->eList = newEdge;
v2->eList->confidence = str;
v2->eList->type = axis;
v2->eList->vertex = v1;
v2->eList->position = pos;
v2->eList->dir = dir;
v2->eList->next = edge;
}
/*
*
* linkedByEdge
*
* Check if an edge has already been constructed between the two
* corner features. c1, c2.
*
*/
int linkedByEdge(cList *c1, cList *c2)
{
edgeList *ptr, *ptr2;
/* Compare the edge lists of the two features,
* if they both have the same edge, they are connected.
*
ptr = c1->eList;
while (ptr != NULL) {
ptr2 = c2->eList;
while (ptr2 != NULL) {
if (ptr2 == ptr) {
return(TRUE);
}
ptr2 = ptr2->next;
}
ptr = ptr->next;
}
*/
ptr = c1->eList;
while (ptr != NULL) {
if (ptr->vertex == c2)
return(TRUE);
ptr = ptr->next;
}
ptr = c2->eList;
while (ptr != NULL) {
if (ptr->vertex == c1)
return(TRUE);
ptr = ptr->next;
}
return(FALSE);
}
double
transLine(int line, cList *vertex)
{
double Dx, Dy;
mat_4x1 vector;
mat_4x1 lineVec;
vector[0] = (double) vertex->x;
vector[1] = (double) vertex->y;
vector[2] = 0.0;
vector[3]= 1.0;
project_2d_to_3d(IMAGE_NAME,vector,vector);
lineVec[0] = (double) vertex->x + line;
lineVec[1] = (double) vertex->y;
lineVec[2] = 0.0;
lineVec[3] = 1.0;
project_2d_to_3d(IMAGE_NAME,lineVec,lineVec);
Dx = fabs(lineVec[0] - vector[0]);
Dy = fabs(lineVec[1] - vector[1]);
if (Dy > Dx)
return(Dy);
else
return(Dx);
}
double idealY(int Dx, int Dy, RotMatrix Forward, RotMatrix Back)
{
Point vec;
vec.x = Dx;
vec.y = Dy;
vec.z = 0.0;
vec.r = 1.0;
/*** Transform the Dx, into the world system ***/
vector_matrix_multiply(&vec,Back);
vec.y = 0.0;
vec.z = 0.0; /** Not sure ?? **/
vec.r = 0.0;
/*** Now transform this vector into the perspective
to find the expected Dy ***/
vector_matrix_multiply(&vec,Forward);
return(vec.y);
}
double idealX(int Dx, int Dy, RotMatrix Forward, RotMatrix Back)
{
int i,j;
Point vec;
vec.x = Dx;
vec.y = Dy;
vec.z = 0.0;
vec.r = 1.0;
/*** Transform the Dy, into the world system ***/
vector_matrix_multiply(&vec,Back);
vec.x = 0.0;
vec.z = 0.0; /** Not Sure ??**/
vec.r = 1.0;
/*** Now transform this vector into the perspective
to find expected Dx ***/
vector_matrix_multiply(&vec,Forward);
return(vec.x);
}
float enoughSupport(c_handle im, cList *c1, cList *c2, int axis, int *position,
int *image_dir)
{
float value=0.0;
float Dx, Dy;
if (axis == AXIS1) {
Dx = (float) c1->leg1Dx;
Dy = (float) c1->leg1Dy;
} else {
Dx = (float) c1->leg2Dx;
Dy = (float) c1->leg2Dy;
}
/**
value=tokenSupport(c1,c2);
fprintf(stderr,"Token Value: %f\n",value);
if (value == 0.0) {
fprintf(stderr,"Image Value: %f\n",value);
**/
value = support_val(im, c1,image_dir,c2->x,c2->y,Dx,Dy,position, 0);
/**
}
**/
if (value >= MIN_LINE_SUPPORT) {
return(value);
}
else
return(0.0);
}
double perfectY(cList *c1, cList *c2)
{
mat_4x1 vec1, vec2;
vec1[0] = (double) c1->x;
vec1[1] = (double) c1->y;
vec1[2] = 0.0;
vec1[3] = 1.0;
vec2[0] = (double) c2->x;
vec2[1] = (double) c2->y;
vec2[2] = 0.0;
vec2[3] = 1.0;
/** Project into ideal 3 Space **/
project_2d_to_3d(IMAGE_NAME,vec1,vec1);
project_2d_to_3d(IMAGE_NAME,vec2,vec2);
vec1[0] = vec2[0];
project_3d_to_2d(IMAGE_NAME,vec1,vec1);
return(vec1[1]);
}