create.c

该程序主要用于三角网

	}
	
	/* create two vertex-uses, one for each end of edge */
	vu = (VertexUse*)malloc(sizeof(VertexUse));  vu->vua = NULL;
	vu->v = v2;
	vu->vuPrev = vu2;
	vu->vuNext = vu2->vuNext;
	vu2->vuNext->vuPrev = vu;
	vu2->vuNext = vu;
	vum = (VertexUse*)malloc(sizeof(VertexUse));  vum->vua = NULL;
	vum->v = v1;
	vum->vuPrev = vu1;
	vum->vuNext = vu1->vuNext;
	vu1->vuNext->vuPrev = vum;
	vu1->vuNext = vum;
	
	/* create edge and two edge-uses, one for each side of edge */
	eu1 = vu1->eu;
	eu2 = vu2->eu;
	e = (Edge*)malloc(sizeof(Edge));  e->ea = NULL;
	e->eu = eu = (EdgeUse*)malloc(sizeof(EdgeUse));  eu->eua = NULL;
	e->fixed = 0;
	eum = (EdgeUse*)malloc(sizeof(EdgeUse));  eum->eua = NULL;
	eu->e = eum->e = e;
	eu->vu = vu;
	vu->eu = eu;
	eum->vu = vum;
	vum->eu = eum;
	eu->euMate = eum;
	eum->euMate = eu;
	eu->euCW = eu1;
	eu->euCCW = eu2->euCCW;
	eum->euCW = eu2;
	eum->euCCW = eu1->euCCW;
	eu1->euCCW->euCW = eum;
	eu2->euCCW->euCW = eu;
	eu1->euCCW = eu;
	eu2->euCCW = eum;
	
	/* create a face */
	f = eu1->f;
	fm = (Face*)malloc(sizeof(Face));  fm->fa = NULL;
	fm->eu = eum;
	fm->fPrev = f;
	fm->fNext = f->fNext;
	f->fNext->fPrev = fm;
	f->fNext = fm;
	fm->m = f->m;
	
	/* make all edge-uses owned by the appropriate faces */
	f->eu = eu1;
	eu->f = f;
	eum->f = fm;
	for (eut=eu2; eut->f!=fm; eut=eut->euCW)
		eut->f = fm;
	
	/* set output values */
	*enew = e;
	*fnew = fm;
}

void makeEdgeVertex (Vertex *v1, float x, float y, Face *f, 
	Edge **enew, Vertex **vnew)
/******************************************************************************
makeEdgeVertex - Create an edge connecting an existing vertex (v1) to a
                 new vertex (with coordinates x,y) in a specified face f. 
                 Return the new edge and the new vertex.
*******************************************************************************
Input:
v1		existing Vertex
x		x-coordinate of new vertex
y		y-coordinate of new vertex
f		specified Face

Output:
enew		new Edge
vnew		new Vertex

*******************************************************************************
Author:  Dave Hale, Colorado School of Mines, 07/09/90
******************************************************************************/
{
	Vertex *v;
	VertexUse *vu,*vum,*vu1;
	Edge *e;
	EdgeUse *eu,*eum,*eu1;
	
	/* determine which use of vertex v1 is adjacent to face f */
	for (vu1=v1->vu; vu1->eu->f!=f; vu1=vu1->vuNext);
	
	/* create a new vertex and vertex-use */
	v = (Vertex*)malloc(sizeof(Vertex));  v->va = NULL;
	vu = (VertexUse*)malloc(sizeof(VertexUse));  vu->vua = NULL;
	v->x = x;
	v->y = y;
	v->fixed = 0;
	v->vu = vu;
	vu->v = v;
	vu->vuNext = vu->vuPrev = vu;
	
	/* create a new vertex-use for existing vertex */
	vum = (VertexUse*)malloc(sizeof(VertexUse));  vum->vua = NULL;
	vum->v = v1;
	vum->vuPrev = vu1;
	vum->vuNext = vu1->vuNext;
	vu1->vuNext->vuPrev = vum;
	vu1->vuNext = vum;
	
	/* create edge and two edge-uses, one for each side of edge */
	eu1 = vu1->eu;
	e = (Edge*)malloc(sizeof(Edge));  e->ea = NULL;
	e->eu = eu = (EdgeUse*)malloc(sizeof(EdgeUse));  eu->eua = NULL;
	e->fixed = 0;
	eum = (EdgeUse*)malloc(sizeof(EdgeUse));  eum->eua = NULL;
	eu->e = eum->e = e;
	eu->f = eum->f = f;
	eu->vu = vu;
	vu->eu = eu;
	eum->vu = vum;
	vum->eu = eum;
	eu->euMate = eum;
	eum->euMate = eu;
	eu->euCW = eu1;
	eu->euCCW = eum;
	eum->euCW = eu;
	eum->euCCW = eu1->euCCW;
	eu1->euCCW->euCW = eum;
	eu1->euCCW = eu;
	
	/* set output values */
	*enew = e;
	*vnew = v;
}

Vertex *addVertexToModel (Model *m, float x, float y)
/*****************************************************************************
addVertexToModel - Add a vertex to model, and return pointer to new vertex
******************************************************************************
Input:
m		model
x		x-coordinate of new vertex
y		y-coordinate of new vertex
******************************************************************************
Notes:
If the new vertex is close to an existing vertex, this function returns NULL.
******************************************************************************
Author:  Dave Hale, Colorado School of Mines, 07/09/90
******************************************************************************/
{
	int first,fixed=0;
	Vertex *v,*vo,*v1,*v2,*v3,*v1fixed=NULL,*v2fixed=NULL;
	VertexUse *vu;
	Edge *e,*e1,*e2,*e3,*eb=NULL;
	EdgeUse *eu,*euo;
	Face *f,*fs,*f1,*f2,*f3;
	
	/* find existing vertex nearest to new vertex */
	v = nearestVertexInModel(m,NULL,x,y);
	
	/* if new vertex is too close to existing vertex, return existing */
	if (sqrt((v->x-x)*(v->x-x)+(v->y-y)*(v->y-y))<m->eps) return NULL;
	
	/* find triangle that contains new vertex */
	f = (v->vu->eu->f!=NULL?v->vu->eu->f:v->vu->eu->euMate->f);
	f = insideTriInModel(m,f,x,y);
	
	/* if the edge nearest new vertex is a fixed edge and very nearby */
	e = nearestEdgeInModel(m,f->eu->e,x,y);
	if (e->fixed && distanceToEdge(e,x,y)<m->eps) {
		
		/* remember the endpoints of the fixed edge */
		v1fixed = e->eu->vu->v;
		v2fixed = e->eu->euCW->vu->v;
		
		/* unfix the fixed edge */
		e->fixed = 0;
		
		/* project new vertex onto edge */
		projectToEdge(e,&x,&y);
		
		/* remember edge was fixed */
		fixed = 1;
		
		/* if edge is on boundary, remember to delete it later */
		if (e->eu->f==NULL || e->eu->euMate->f==NULL) eb = e;
	}
	
	/* this triangle will be deleted */
	if (m->tDel!=NULL) m->tDel(m,f);
	
	/* make edges from new vertex to vertices of this triangle */
	vu = f->eu->vu;
	v1 = vu->v;
	v2 = vu->eu->euCW->vu->v;
	v3 = vu->eu->euCCW->vu->v;
	f1 = f;
	makeEdgeVertex(v1,x,y,f1,&e1,&v);
	makeEdgeFace(v2,v,&e2,&f2);
	makeEdgeFace(v3,v,&e3,&f3);
	
	/* 3 triangles were made */
	if (m->tAdd!=NULL) {
		m->tAdd(m,f1);
		m->tAdd(m,f2);
		m->tAdd(m,f3);
	}
	
	/* compute circumcircles of the 3 new triangles */
	vu = v->vu;
	do {
		circumTri(vu->eu->f);
		vu = vu->vuNext;
	} while (vu!=v->vu);
	
	/* loop over vertex-uses (triangles) in clockwise direction */
	vu = v->vu;
	first = 1;
	do {
		/* determine edge-uses and edge opposite new vertex */
		eu = vu->eu->euCW;
		euo = eu->euMate;
		e = eu->e;
		
		/* if opposite triangle's circumcircle contains new vertex */
		if (euo->f!=NULL && 
			!euo->e->fixed && 
			inCircumTri(x,y,euo->f)) {
			
			/* determine vertex opposite edge */
			vo = euo->euCCW->vu->v;
			
			/* 2 triangles will be deleted */
			if (m->tDel!=NULL) {
				m->tDel(m,e->eu->f);
				m->tDel(m,e->eu->euMate->f);
			}
			
			/* kill opposite edge */
			killEdge(e,&fs);
			
			/* make edge connecting new and opposite vertices */
			makeEdgeFace(v,vo,&e,&f);
			
			/* 2 triangles were created */
			if (m->tAdd!=NULL) {
				m->tAdd(m,e->eu->f);
				m->tAdd(m,e->eu->euMate->f);
			}
			
			/* compute circumcircles of 2 new triangles */
			circumTri(e->eu->f);
			circumTri(e->eu->euMate->f);
		
		/* else, go to next vertex-use (triangle) clockwise */
		} else {
			vu = vu->eu->euCCW->euMate->vu;
			first = 0;
		}
		
	} while (vu!=v->vu || first);
	
	/* if new vertex was added on an edge that was fixed */
	if (fixed) {
		
		/* loop over vertex uses of new vertex */
		vu = v->vu;
		do {
			/* edge use */
			eu = vu->eu;
			
			/* fix edge if it was part of fixed edge */
			if (eu->euCCW->vu->v==v1fixed)
				eu->euCCW->e->fixed = 1;
			if (eu->euCW->vu->v==v2fixed)
				eu->e->fixed = 1;
			
			/* next vertex use */
			vu = vu->vuNext;
			
		} while (vu!=v->vu);
	}
	
	/* if edge on boundary needs to be deleted, delete it */
	if (eb!=NULL) killBoundaryEdge(eb);
	
	/* if specified, do add vertex function */
	if (m->vAdd!=NULL) m->vAdd(m,v);
	
	/* debug */
	/* checkModel(m); */
	
	/* return pointer to vertex */
	return v;
}

Tri* insideTriInModel (Model *m, Tri *start, float x, float y)
/*****************************************************************************
insideTriInModel - return pointer to triangle in model containing
                   specified (x,y) coordinates
******************************************************************************
Input:
m		Model
start		triangle to look at first (NULL to begin looking anywhere)
x		x-coordinate
y		y-coordinate

******************************************************************************
Notes:
Points on an edge of a triangle are assumed to be inside that triangle.
An edge may be used by two triangles, so two triangles may "contain"
a point that lies on an edge.  The first triangle found to contain
the specified point is returned.
******************************************************************************
Author:  Dave Hale, Colorado School of Mines, 09/11/90
******************************************************************************/
{
	int inside=0;
	float x1,y1,x2,y2,x3,y3,s1,s2;
	Vertex *v1,*v2,*v3;
	EdgeUse *eu;
	Tri *t;
	
	/* start at some face in model */
	t = (start==NULL ? m->f : start);
	
	/* loop over triangles until point is inside */
	while (!inside) {
		
		/* loop over all edge-uses in triangle */
		eu = t->eu;
		do {
		
			/* vertices at ends of edge */
			v1 = eu->vu->v;  x1 = v1->x;  y1 = v1->y;
			v2 = eu->euCW->vu->v;  x2 = v2->x;  y2 = v2->y;
			
			/* other vertex */
			v3 = eu->euCCW->vu->v;  x3 = v3->x;  y3 = v3->y;
			
			/* cross-products */
			s1 = (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
			s2 = (x2-x1)*(y-y1)-(x-x1)*(y2-y1);
			
			/* if cross-products have different sign */
			if (s1*s2<0.0) {
				
				/* if triangle opposite current edge exists */
				if (eu->euMate->f!=NULL) {
				
					/* look at that triangle next */
					t = eu->euMate->f;
					break;
				}
			}	
						
			/* next edge-use */
			eu = eu->euCW;
			
		} while (eu!=t->eu);
		
		/* if did not break, then point is inside triangle */
		if (eu==t->eu) inside = 1;
	}
	
	/* return pointer to triangle containing point */
	return t;
}