Voronoi程序.zip

/* * The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T * Bell Laboratories. * Permission to use, copy, modify, and distribute this software for any * purpose without fee is hereby granted, provided that this entire notice * is included in all copies of any software which is or includes a copy * or modification of this software and in all copies of the supporting * documentation for such software. * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ /* * This code was originally written by Stephan Fortune in C code. I, Shane O'Sullivan, * have since modified it, encapsulating it in a C++ class and, fixing memory leaks and * adding accessors to the Voronoi Edges. * Permission to use, copy, modify, and distribute this software for any * purpose without fee is hereby granted, provided that this entire notice * is included in all copies of any software which is or includes a copy * or modification of this software and in all copies of the supporting * documentation for such software. * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ #include "VoronoiDiagramGenerator.h" VoronoiDiagramGenerator::VoronoiDiagramGenerator() { siteidx = 0; sites = 0; allMemoryList = new FreeNodeArrayList; allMemoryList->memory = 0; allMemoryList->next = 0; currentMemoryBlock = allMemoryList; allEdges = 0; iteratorEdges = 0; minDistanceBetweenSites = 0; } VoronoiDiagramGenerator::~VoronoiDiagramGenerator() { cleanup(); cleanupEdges(); if(allMemoryList != 0) delete allMemoryList; } bool VoronoiDiagramGenerator::generateVoronoi(float *xValues, float *yValues, int numPoints, float minX, float maxX, float minY, float maxY, float minDist) { cleanup(); cleanupEdges(); int i; minDistanceBetweenSites = minDist; nsites=numPoints; plot = 0; triangulate = 0; debug = 1; sorted = 0; freeinit(&sfl, sizeof (Site)); sites = (struct Site *) myalloc(nsites*sizeof( *sites)); if(sites == 0) return false; xmin = xValues[0]; ymin = yValues[0]; xmax = xValues[0]; ymax = yValues[0]; for(i = 0; i< nsites; i++) { sites[i].coord.x = xValues[i]; sites[i].coord.y = yValues[i]; sites[i].sitenbr = i; sites[i].refcnt = 0; if(xValues[i] < xmin) xmin = xValues[i]; else if(xValues[i] > xmax) xmax = xValues[i]; if(yValues[i] < ymin) ymin = yValues[i]; else if(yValues[i] > ymax) ymax = yValues[i]; //printf("\n%f %f\n",xValues[i],yValues[i]); } qsort(sites, nsites, sizeof (*sites), scomp); siteidx = 0; geominit(); float temp = 0; if(minX > maxX) { temp = minX; minX = maxX; maxX = temp; } if(minY > maxY) { temp = minY; minY = maxY; maxY = temp; } borderMinX = minX; borderMinY = minY; borderMaxX = maxX; borderMaxY = maxY; siteidx = 0; voronoi(triangulate); return true; } bool VoronoiDiagramGenerator::ELinitialize() { int i; freeinit(&hfl, sizeof **ELhash); ELhashsize = 2 * sqrt_nsites; ELhash = (struct Halfedge **) myalloc ( sizeof *ELhash * ELhashsize); if(ELhash == 0) return false; for(i=0; i<ELhashsize; i +=1) ELhash[i] = (struct Halfedge *)NULL; ELleftend = HEcreate( (struct Edge *)NULL, 0); ELrightend = HEcreate( (struct Edge *)NULL, 0); ELleftend -> ELleft = (struct Halfedge *)NULL; ELleftend -> ELright = ELrightend; ELrightend -> ELleft = ELleftend; ELrightend -> ELright = (struct Halfedge *)NULL; ELhash[0] = ELleftend; ELhash[ELhashsize-1] = ELrightend; return true; } struct Halfedge* VoronoiDiagramGenerator::HEcreate(struct Edge *e,int pm) { struct Halfedge *answer; answer = (struct Halfedge *) getfree(&hfl); answer -> ELedge = e; answer -> ELpm = pm; answer -> PQnext = (struct Halfedge *) NULL; answer -> vertex = (struct Site *) NULL; answer -> ELrefcnt = 0; return(answer); } void VoronoiDiagramGenerator::ELinsert(structHalfedge *lb, struct Halfedge *newHe) { newHe -> ELleft = lb; newHe -> ELright = lb -> ELright; (lb -> ELright) -> ELleft = newHe; lb -> ELright = newHe; } /* Get entry from hash table, pruning any deleted nodes */ struct Halfedge * VoronoiDiagramGenerator::ELgethash(int b) { struct Halfedge *he; if(b<0 || b>=ELhashsize) return((struct Halfedge *) NULL); he = ELhash[b]; if (he == (struct Halfedge *) NULL || he->ELedge != (struct Edge *) DELETED ) return (he); /* Hash table points to deleted half edge. Patch as necessary. */ ELhash[b] = (struct Halfedge *) NULL; if ((he -> ELrefcnt -= 1) == 0) makefree((Freenode*)he, &hfl); return ((struct Halfedge *) NULL); } struct Halfedge * VoronoiDiagramGenerator::ELleftbnd(struct Point *p) { int i, bucket; struct Halfedge *he; /* Use hash table to get close to desired halfedge */ bucket = (int)((p->x - xmin)/deltax * ELhashsize);//use the hash function to find the place in the hash map that this HalfEdge should be if(bucket<0) bucket =0;//make sure that the bucket position in within the range of the hash array if(bucket>=ELhashsize) bucket = ELhashsize - 1; he = ELgethash(bucket); if(he == (struct Halfedge *) NULL)//if the HE isn't found, search backwards and forwards in the hash map for the first non-null entry { for(i=1; 1 ; i += 1) { if ((he=ELgethash(bucket-i)) != (struct Halfedge *) NULL) break; if ((he=ELgethash(bucket+i)) != (struct Halfedge *) NULL) break; }; totalsearch += i; }; ntry += 1; /* Now search linear list of halfedges for the correct one */ if (he==ELleftend || (he != ELrightend && right_of(he,p))) { do { he = he -> ELright; } while (he!=ELrightend && right_of(he,p));//keep going right on the list until either the end is reached, or you find the 1st edge which the point he = he -> ELleft;//isn't to the right of } else //if the point is to the left of the HalfEdge, then search left for the HE just to the left of the point do { he = he -> ELleft; } while (he!=ELleftend && !right_of(he,p)); /* Update hash table and reference counts */ if(bucket > 0 && bucket <ELhashsize-1) { if(ELhash[bucket] != (struct Halfedge *) NULL) { ELhash[bucket] -> ELrefcnt -= 1; } ELhash[bucket] = he; ELhash[bucket] -> ELrefcnt += 1; }; return (he); } /* This delete routine can't reclaim node, since pointers from hash table may be present. */ void VoronoiDiagramGenerator::ELdelete(struct Halfedge *he) { (he -> ELleft) -> ELright = he -> ELright; (he -> ELright) -> ELleft = he -> ELleft; he -> ELedge = (struct Edge *)DELETED; } struct Halfedge * VoronoiDiagramGenerator::ELright(struct Halfedge *he) { return (he -> ELright); } struct Halfedge * VoronoiDiagramGenerator::ELleft(struct Halfedge *he) { return (he -> ELleft); } struct Site * VoronoiDiagramGenerator::leftreg(struct Halfedge *he) { if(he -> ELedge == (struct Edge *)NULL) return(bottomsite); return( he -> ELpm == le ? he -> ELedge -> reg[le] : he -> ELedge -> reg[re]); } struct Site * VoronoiDiagramGenerator::rightreg(struct Halfedge *he) { if(he -> ELedge == (struct Edge *)NULL) //if this halfedge has no edge, return the bottom site (whatever that is) return(bottomsite); //if the ELpm field is zero, return the site 0 that this edge bisects, otherwise return site number 1 return( he -> ELpm == le ? he -> ELedge -> reg[re] : he -> ELedge -> reg[le]); } void VoronoiDiagramGenerator::geominit() { float sn;