del_impl.cpp

最新delaunay 算法源代码

     piyush::__pmesh  * tpmesh  = (piyush::__pmesh *) (fit.MyDelaunay->pmesh);
     trianglelooptype * ploop   = (trianglelooptype *)(&(fit.floop));

     vertex vertexptr = (vertex) ((ploop->tri)[plus1mod3[ploop->orient] + 3]);
     return
	( ((int *) (vertexptr))[tpmesh->vertexmarkindex] )
	-
	tpbehavior->firstnumber;
		
}


int Delaunay::Dest(fIterator const & fit){
     typedef piyush::vertex   vertex;
     typedef piyush::triangle triangle;
     typedef piyush::__otriangle trianglelooptype;

     piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *)
                                                ((fit.MyDelaunay)->pbehavior);

     piyush::__pmesh  * tpmesh  = (piyush::__pmesh *) (fit.MyDelaunay->pmesh);
     trianglelooptype * ploop   = (trianglelooptype *)(&(fit.floop));

     vertex vertexptr = (vertex) ((ploop->tri)[minus1mod3[ploop->orient] + 3]);
     return
        ( ((int *) (vertexptr))[tpmesh->vertexmarkindex] )
        -
        tpbehavior->firstnumber;

}

int Delaunay::Apex(fIterator const & fit){
     typedef piyush::vertex   vertex;
     typedef piyush::triangle triangle;
     typedef piyush::__otriangle trianglelooptype;

     piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *)
                                                ((fit.MyDelaunay)->pbehavior);

     piyush::__pmesh  * tpmesh  = (piyush::__pmesh *) (fit.MyDelaunay->pmesh);
     trianglelooptype * ploop   = (trianglelooptype *)(&(fit.floop));

     vertex vertexptr = (vertex) ((ploop->tri)[ploop->orient + 3]);
     return
        ( ((int *) (vertexptr))[tpmesh->vertexmarkindex] )
        -
        tpbehavior->firstnumber;
}


int Delaunay::Sym(fIterator const & fit, char i){
	 typedef piyush::vertex      vertex;
     typedef piyush::triangle    triangle;
     typedef piyush::__otriangle trianglelooptype;
	 triangle ptr;                         /* Temporary variable used by sym(). */

     //piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *)
     //                                           ((fit.MyDelaunay)->pbehavior);

     piyush::__pmesh  * tpmesh  = (piyush::__pmesh *) (fit.MyDelaunay->pmesh);
     trianglelooptype * ploop   = (trianglelooptype *)(&(fit.floop));

	 char oval = ploop->orient;
     ploop->orient = i;

	 trianglelooptype top;
	 sym(*ploop, top);
	 ploop->orient = oval;

	 if(top.tri != tpmesh->dummytri){
		 vertex farvertex;
		 apex(top, farvertex);
		 return ((int *)farvertex)[tpmesh->vertexmarkindex];
	 }
	 
	return -1;	 
}


Delaunay::fIterator Delaunay::Sym(fIterator const & fit){
	 fIterator retval;
	 retval.MyDelaunay = fit.MyDelaunay;

	 typedef piyush::vertex      vertex;
	 typedef piyush::triangle    triangle;
	 typedef piyush::__otriangle trianglelooptype;
	 triangle ptr;                         /* Temporary variable used by sym(). */

     piyush::__pmesh  * tpmesh  = (piyush::__pmesh *) (fit.MyDelaunay->pmesh);
     trianglelooptype * ploop   = (trianglelooptype *)(&(fit.floop));

	 
	 trianglelooptype top;
	 sym(*ploop, top);
	 

	 if(top.tri != tpmesh->dummytri){
		 retval.floop.tri = top.tri;
		 retval.floop.orient = top.orient;

		 return retval;
	 }
	 
	 retval.floop.tri = NULL;
	 retval.floop.orient = 0;
	 return retval;

}

double Delaunay::area(fIterator const & fit){
	Point torg, tdest, tapex;
	torg  = point_at_vertex_id(Org(fit));
	tdest = point_at_vertex_id(Dest(fit));
	tapex = point_at_vertex_id(Apex(fit));
	double dxod(torg[0] - tdest[0]);
	double dyod(torg[1] - tdest[1]);
	double dxda(tdest[0] - tapex[0]);
	double dyda(tdest[1] - tapex[1]);

	double area = 0.5 * (dxod * dyda - dyod * dxda);
	return area;
}

Delaunay::fIterator Delaunay::locate(int vertexid){
	fIterator retval;
	retval.MyDelaunay = this;

    typedef piyush::vertex      vertex;
    typedef piyush::triangle    triangle;
    typedef piyush::__otriangle trianglelooptype;

	trianglelooptype horiz;               /* Temporary variable for use in locate(). */
	triangle ptr;                         /* Temporary variable used by sym(). */

	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
	piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *) pbehavior;
	piyush  *pdelclass               = (piyush *)              delclass;

	horiz.tri = tpmesh->dummytri;
    horiz.orient = 0;
	symself(horiz);
	double dv[2];
	dv[0] = PList[vertexid][0];
	dv[1] = PList[vertexid][1];

	/* Search for a triangle containing `newvertex'. */
	int intersect = pdelclass->locate(tpmesh, tpbehavior, dv, &horiz);
	if(intersect != piyush::ONVERTEX) { // Not on vertex!
		cout << "Something went wrong in point location\n";
		exit(1);
	}
	
	retval.floop.tri = horiz.tri;
	retval.floop.orient = horiz.orient;

	return retval;

}

inline Delaunay::fIterator Delaunay::Lnext(fIterator const & fit){
/* lnext() finds the next edge (counterclockwise) of a triangle.        */
	typedef piyush::__otriangle trianglelooptype;

	fIterator retval;
	retval.MyDelaunay = this;

	lnext(   (*(trianglelooptype *)(&(fit.floop))), (*(trianglelooptype *)(&(retval.floop))));
	return retval;
}

inline Delaunay::fIterator Delaunay::Lprev(fIterator const & fit){
/*                                                                           */
/*  lprev:  Find the previous edge (clockwise) of a triangle.                */
/*  lprev(abc) -> cab                                                        */
/*                                                                           */
	typedef piyush::__otriangle trianglelooptype;

	fIterator retval;
	retval.MyDelaunay = this;

	lprev(   (*(trianglelooptype *)(&(fit.floop))), (*(trianglelooptype *)(&(retval.floop))));
	return retval;
}


inline Delaunay::fIterator Delaunay::Onext(fIterator const & fit){

/*  onext:  Find the next edge counterclockwise with the same origin.        */
/*  onext(abc) -> ac*                                                        */
	
	typedef piyush::__otriangle trianglelooptype;
	typedef piyush::triangle    triangle;

	triangle ptr;
	fIterator retval;
	retval.MyDelaunay = this;

	//cout << "Onext called:\n " 
	//	 << Org(fit) << "\t" << Dest(fit) << "\t" << Apex(fit) << "\n";

	onext(   (*(trianglelooptype *)(&(fit.floop))), (*(trianglelooptype *)(&(retval.floop))));

	// retval could be dummy!
	return retval;
}


inline Delaunay::fIterator Delaunay::Oprev(fIterator const & fit){

/*                                                                           */
/*  oprev:  Find the next edge clockwise with the same origin.               */
/*  oprev(abc) -> a*b                                                        */
/*                                                                           */
	typedef piyush::__otriangle trianglelooptype;
	typedef piyush::triangle    triangle;

	triangle ptr;
	fIterator retval;
	retval.MyDelaunay = this;

	oprev(   (*(trianglelooptype *)(&(fit.floop))), (*(trianglelooptype *)(&(retval.floop))));
	return retval;
}


inline bool Delaunay::isdummy(fIterator const & fit){
	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
	typedef piyush::__otriangle trianglelooptype;

	return ( ((trianglelooptype *)(&(fit.floop)))->tri == tpmesh->dummytri );
}

void Delaunay::trianglesAroundVertex(int vertexid, std::vector<int>& ivv){
	fIterator fit = locate(vertexid);
	ivv.clear();

	int start = Dest(fit);
	int linkn = Apex(fit);

	ivv.push_back(vertexid);
	ivv.push_back(start);
	ivv.push_back(linkn);

	fIterator nfit = fit;
	fIterator pnfit = fit; // follows nfit by one triangle

	while( linkn != start ){
		
		nfit = Onext(nfit);
		if (isdummy(nfit)){
			// Do another algorithm
			ivv.clear();

			// use oprev now...
			fit = pnfit;
			nfit = fit;

			start = Apex(fit);
			linkn = Dest(fit);
			
			ivv.push_back(vertexid);
			ivv.push_back(linkn);
			ivv.push_back(start);
			
			while( linkn != start ){
				nfit = Oprev(nfit);
				if(isdummy(nfit))
					return;
				int a = Org(nfit);
				int b = Dest(nfit);
				int c = Apex(nfit);
				ivv.push_back(a);
				ivv.push_back(b);
				ivv.push_back(c);
				linkn = Dest(nfit);
			}

			return;
		}
		
		pnfit = nfit;

		int a = Org(nfit);
		int b = Dest(nfit);
		int c = Apex(nfit);

		//cout << "Triangle: " << a << "\t"  << b << "\t"  << c << "\n";

		ivv.push_back(a);
		ivv.push_back(b);
		ivv.push_back(c);

		linkn = Apex(nfit);
	}

}

} // namespace tpp ends.