del_impl.cpp

最新delaunay 算法源代码

/*! \file del_impl.cpp
        \brief The implementation of the 2D delaunay triangulation class.

		This class is a wrapper on the triangle package.
 */
#include <iostream>
#include <triangle_impl.hpp>
#include <del_interface.hpp>
#include <new>

#define REAL double

namespace tpp {

using std::cout;
using std::cerr;



void Delaunay::Triangulate(std::string& triswitches){
	typedef struct triangulateio  TriangStruct;
	typedef struct triangulateio* pTriangStruct;

	in = new TriangStruct;

	pTriangStruct pin = (struct triangulateio *)in;
	

	pin->numberofpoints = (int)PList.size();
  	pin->numberofpointattributes = (int)0;
	pin->pointlist = static_cast<double *> ((void *)(&PList[0])) ;
  	pin->pointattributelist = NULL;
  	pin->pointmarkerlist = (int *) NULL;
 	pin->numberofsegments = 0;
  	pin->numberofholes = 0;
  	pin->numberofregions = 0;
  	pin->regionlist = (REAL *) NULL;

	delclass = new piyush;
	piyush *pdelclass = (piyush *)delclass;
	triswitches.push_back('\0');
	char *ptris = &triswitches[0];

	pmesh = new piyush::__pmesh;
	pbehavior = new piyush::__pbehavior;

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

	pdelclass->triangleinit(tpmesh);
	pdelclass->parsecommandline(1, &ptris, tpbehavior);

	pdelclass->transfernodes(tpmesh, tpbehavior, pin->pointlist, 
		pin->pointattributelist,
                pin->pointmarkerlist, pin->numberofpoints,
                pin->numberofpointattributes);
	tpmesh->hullsize = pdelclass->delaunay(tpmesh, tpbehavior);

  /* Ensure that no vertex can be mistaken for a triangular bounding */
  /*   box vertex in insertvertex().                                 */
  	tpmesh->infvertex1 = (piyush::vertex) NULL;
  	tpmesh->infvertex2 = (piyush::vertex) NULL;
  	tpmesh->infvertex3 = (piyush::vertex) NULL;

	/* Calculate the number of edges. */
	tpmesh->edges = (3l * tpmesh->triangles.items + tpmesh->hullsize) / 2l;
	pdelclass->numbernodes(tpmesh, tpbehavior);

	Triangulated = true;
}


Delaunay::~Delaunay(){
        struct triangulateio *pin = (struct triangulateio *)in;

	piyush *pdelclass =  (piyush *)delclass;

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

	pdelclass->triangledeinit(tpmesh, tpbehavior);

	delete tpmesh;
	delete tpbehavior;
	delete pin;
	delete pdelclass;	
}

void Delaunay::writeoff(std::string& fname){
	if(!Triangulated) {
		cerr << "FATAL: Write called before triangulation\n";
		exit(1);
	}
        piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
        piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *) pbehavior;
	piyush *pdelclass =  (piyush *)delclass;
	char *pfname = new char[fname.size()+1];
	strcpy(pfname , fname.c_str());

	pdelclass->writeoff(tpmesh, tpbehavior, pfname, 0, NULL);
	delete [] pfname;
}

int Delaunay::nedges(){
	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
	return tpmesh->edges;
}

int Delaunay::ntriangles(){
	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
	return tpmesh->triangles.items;	
}

int Delaunay::nvertices(){
	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
        piyush::__pbehavior * tpbehavior = (piyush::__pbehavior *) pbehavior;
	int outvertices;

	if (tpbehavior->jettison) {
	    outvertices = tpmesh->vertices.items - tpmesh->undeads;
	} else {
	    outvertices = tpmesh->vertices.items;
	}

	return outvertices;
}

int Delaunay::hull_size(){
	piyush::__pmesh     * tpmesh     = (piyush::__pmesh *)     pmesh;
	return  tpmesh->hullsize;	
}

int Delaunay::vertexId(vIterator const &vit){
 piyush::__pmesh     * tpmesh     = (piyush::__pmesh *) vit.MyDelaunay->pmesh;
 return ((int *)vit.vloop)[tpmesh->vertexmarkindex];
}




///////////////////////////////
//
// Vertex Iterator Impl.
//
///////////////////////////////


Delaunay::vIterator::vIterator(Delaunay* adel) {
     typedef piyush::vertex vertex;
     MyDelaunay = adel;

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

     pdelclass->traversalinit(&( tpmesh->vertices ) );
     vloop = pdelclass->vertextraverse(tpmesh);

     while
    	(
		 tpbehavior->jettison || 
	   	(
		  ((int *)vloop)[tpmesh->vertexmarkindex+1] == UNDEADVERTEX
		)
	) 
	vloop = (void *) pdelclass->vertextraverse(tpmesh);
}

Delaunay::vIterator::~vIterator(){
}


Delaunay::vIterator Delaunay::vend(){
	vIterator vit;
	vit.vloop = ((piyush::vertex) NULL);
	return vit;
}



Delaunay::vIterator Delaunay::vIterator::operator++() {
     typedef piyush::vertex vertex;	

     piyush::__pmesh     * tpmesh     = (piyush::__pmesh *) MyDelaunay->pmesh;
     piyush::__pbehavior * tpbehavior = 
				(piyush::__pbehavior *) MyDelaunay->pbehavior;

     piyush *pdelclass =  (piyush *) MyDelaunay->delclass;

     while
        (
                 tpbehavior->jettison ||
                (
                  ((int *)vloop)[tpmesh->vertexmarkindex+1] == UNDEADVERTEX
                )
        )
        vloop = (void *) pdelclass->vertextraverse(tpmesh);
        vloop = (void *) pdelclass->vertextraverse(tpmesh);

		vIterator vit;
		vit.vloop = vloop;
		vit.MyDelaunay = MyDelaunay;

		return vit;
}

Delaunay::Point & Delaunay::vIterator::operator*() const{
	return *((Point *)vloop);
}


bool operator==(Delaunay::vIterator const &vit1,
	        Delaunay::vIterator const &vit2) {
	if (vit1.vloop == vit2.vloop) return true;
	return false;
}


bool operator!=(Delaunay::vIterator const &vit1,
	        Delaunay::vIterator const &vit2) {
	if (vit1.vloop != vit2.vloop) return true;
	return false;
}




///////////////////////////////
//
// Face Iterator Impl.
//
///////////////////////////////



Delaunay::fIterator::fIterator(Delaunay* adel) {
     typedef piyush::vertex vertex;
     typedef piyush::__otriangle trianglelooptype;

     MyDelaunay = adel;

     piyush::__pmesh     * tpmesh     = (piyush::__pmesh *) adel->pmesh;
     piyush *pdelclass =  (piyush *)adel->delclass;

     pdelclass->traversalinit(&( tpmesh->triangles ) );
     // floop = new trianglelooptype;
     trianglelooptype *ploop = (trianglelooptype *)(&floop);
     ploop->tri    = pdelclass->triangletraverse(tpmesh);
     ploop->orient = 0;

}

Delaunay::fIterator::~fIterator(){
}

Delaunay::fIterator Delaunay::fend(){
        fIterator fit;
		typedef piyush::__otriangle trianglelooptype;
        fit.floop.tri = (double ***) NULL;
        return fit;
}

void Delaunay::fIterator::operator++() {
	 // cout << "++ called\n";
     typedef piyush::vertex   vertex;
     typedef piyush::triangle triangle;
     typedef piyush::__otriangle trianglelooptype;

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

     ploop->tri = pdelclass->triangletraverse(tpmesh);
	 // cout << "tri val = " << ploop->tri << endl;
}

bool operator==(Delaunay::fIterator const &fit1,
                Delaunay::fIterator const &fit2) {

    return (fit1.floop.tri == fit2.floop.tri);

}

bool operator!=(Delaunay::fIterator const &fit1,
                Delaunay::fIterator const &fit2) {
		return !( operator==(fit1,fit2) );
}


/*  A triangle abc has origin (org) a,destination (dest) b, and apex (apex)  */
/*  c.  These vertices occur in counterclockwise order about the triangle.   */
int Delaunay::Org (fIterator const & fit){
     typedef piyush::vertex   vertex;
     typedef piyush::triangle triangle;
     typedef piyush::__otriangle trianglelooptype;

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