-/*\r
-* The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T\r
-* Bell Laboratories.\r
-* Permission to use, copy, modify, and distribute this software for any\r
-* purpose without fee is hereby granted, provided that this entire notice\r
-* is included in all copies of any software which is or includes a copy\r
-* or modification of this software and in all copies of the supporting\r
-* documentation for such software.\r
-* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED\r
-* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY\r
-* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY\r
-* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.\r
-*/\r
-\r
-/* \r
-* This code was originally written by Stephan Fortune in C code. I, Shane O'Sullivan, \r
-* have since modified it, encapsulating it in a C++ class and, fixing memory leaks and \r
-* adding accessors to the Voronoi Edges.\r
-* Permission to use, copy, modify, and distribute this software for any\r
-* purpose without fee is hereby granted, provided that this entire notice\r
-* is included in all copies of any software which is or includes a copy\r
-* or modification of this software and in all copies of the supporting\r
-* documentation for such software.\r
-* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED\r
-* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY\r
-* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY\r
-* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.\r
-*/\r
-\r
-#include "VoronoiDiagramGenerator.h"\r
-#include <stdio.h>\r
-#include <sys/mman.h>\r
-\r
-VoronoiDiagramGenerator::VoronoiDiagramGenerator()\r
-{\r
- siteidx = 0;\r
- sites = 0;\r
-\r
- allMemoryList = new FreeNodeArrayList;\r
- allMemoryList->memory = 0;\r
- allMemoryList->next = 0;\r
- currentMemoryBlock = allMemoryList;\r
- allEdges = 0;\r
- iteratorEdges = 0;\r
- minDistanceBetweenSites = 0;\r
-}\r
-\r
-VoronoiDiagramGenerator::~VoronoiDiagramGenerator()\r
-{\r
- cleanup();\r
- cleanupEdges();\r
-\r
- if(allMemoryList != 0)\r
- delete allMemoryList;\r
-}\r
-\r
-bool VoronoiDiagramGenerator::generateVoronoi(struct SourcePoint* srcPoints, int numPoints, float minX, float maxX, float minY, float maxY, float minDist)\r
-{\r
- cleanup();\r
- cleanupEdges();\r
- int i;\r
-\r
- minDistanceBetweenSites = minDist;\r
-\r
- nsites = numPoints;\r
- plot = 0;\r
- triangulate = 0;\r
- debug = 1;\r
- sorted = 0;\r
- freeinit(&sfl, sizeof (Site));\r
-\r
- sites = (struct Site *) myalloc(nsites * sizeof(*sites));\r
- polygons = (struct Polygon *) myalloc(nsites * sizeof(*polygons));\r
-\r
- if(sites == 0) return false;\r
-\r
- xmin = srcPoints[0].x;\r
- ymin = srcPoints[0].y;\r
- xmax = srcPoints[0].x;\r
- ymax = srcPoints[0].y;\r
-\r
- for(i = 0; i < nsites; i++)\r
- {\r
- sites[i].coord.x = srcPoints[i].x;\r
- sites[i].coord.y = srcPoints[i].y;\r
- sites[i].weight = srcPoints[i].weight;\r
- sites[i].sitenbr = i;\r
- sites[i].refcnt = 0; // prevent reuse?\r
-\r
- if(sites[i].coord.x < xmin)\r
- xmin = sites[i].coord.x;\r
- else if(sites[i].coord.x > xmax)\r
- xmax = sites[i].coord.x;\r
-\r
- if(sites[i].coord.y < ymin)\r
- ymin = sites[i].coord.y;\r
- else if(sites[i].coord.y > ymax)\r
- ymax = sites[i].coord.y;\r
-\r
- polygons[i].coord.x = sites[i].coord.x;\r
- polygons[i].coord.y = sites[i].coord.y;\r
- polygons[i].numpoints = 0;\r
- polygons[i].pointlist = NULL;\r
- polygons[i].boundary = 0;\r
-\r
- //printf("\n%lf %lf\n", sites[i].coord.x, sites[i].coord.y);\r
- }\r
-\r
- qsort(sites, nsites, sizeof (*sites), scomp);\r
-\r
- siteidx = 0;\r
- geominit();\r
- float temp = 0;\r
- if(minX > maxX)\r
- {\r
- temp = minX;\r
- minX = maxX;\r
- maxX = temp;\r
- }\r
- if(minY > maxY)\r
- {\r
- temp = minY;\r
- minY = maxY;\r
- maxY = temp;\r
- }\r
- borderMinX = minX;\r
- borderMinY = minY;\r
- borderMaxX = maxX;\r
- borderMaxY = maxY;\r
-\r
- corners[0].x = borderMinX;\r
- corners[0].y = borderMinY;\r
- corners[1].x = borderMinX;\r
- corners[1].y = borderMaxY;\r
- corners[2].x = borderMaxX;\r
- corners[2].y = borderMaxY;\r
- corners[3].x = borderMaxX;\r
- corners[3].y = borderMinY;\r
-\r
- siteidx = 0;\r
- voronoi(triangulate);\r
-\r
- return true;\r
-}\r
-\r
-bool VoronoiDiagramGenerator::ELinitialize()\r
-{\r
- int i;\r
- freeinit(&hfl, sizeof **ELhash);\r
- ELhashsize = 2 * sqrt_nsites;\r
- ELhash = (struct Halfedge **) myalloc ( sizeof *ELhash * ELhashsize);\r
-\r
- if(ELhash == 0)\r
- return false;\r
-\r
- for(i=0; i<ELhashsize; i +=1) ELhash[i] = (struct Halfedge *)NULL;\r
- ELleftend = HEcreate( (struct Edge *)NULL, 0);\r
- ELrightend = HEcreate( (struct Edge *)NULL, 0);\r
- ELleftend -> ELleft = (struct Halfedge *)NULL;\r
- ELleftend -> ELright = ELrightend;\r
- ELrightend -> ELleft = ELleftend;\r
- ELrightend -> ELright = (struct Halfedge *)NULL;\r
- ELhash[0] = ELleftend;\r
- ELhash[ELhashsize-1] = ELrightend;\r
-\r
- return true;\r
-}\r
-\r
-\r
-struct Halfedge* VoronoiDiagramGenerator::HEcreate(struct Edge *e,int pm)\r
-{\r
- struct Halfedge *answer;\r
- answer = (struct Halfedge *) getfree(&hfl);\r
- answer -> ELedge = e;\r
- answer -> ELpm = pm;\r
- answer -> PQnext = (struct Halfedge *) NULL;\r
- answer -> vertex = (struct Site *) NULL;\r
- answer -> ELrefcnt = 0;\r
- return(answer);\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::ELinsert(struct Halfedge *lb, struct Halfedge *newHe)\r
-{\r
- newHe -> ELleft = lb;\r
- newHe -> ELright = lb -> ELright;\r
- (lb -> ELright) -> ELleft = newHe;\r
- lb -> ELright = newHe;\r
-}\r
-\r
-/* Get entry from hash table, pruning any deleted nodes */\r
-struct Halfedge * VoronoiDiagramGenerator::ELgethash(int b)\r
-{\r
- struct Halfedge *he;\r
-\r
- if(b<0 || b>=ELhashsize)\r
- return((struct Halfedge *) NULL);\r
- he = ELhash[b];\r
- if (he == (struct Halfedge *) NULL || he->ELedge != (struct Edge *) DELETED )\r
- return (he);\r
-\r
- /* Hash table points to deleted half edge. Patch as necessary. */\r
- ELhash[b] = (struct Halfedge *) NULL;\r
- if ((he -> ELrefcnt -= 1) == 0) \r
- makefree((Freenode*)he, &hfl);\r
- return ((struct Halfedge *) NULL);\r
-}\r
-\r
-struct Halfedge * VoronoiDiagramGenerator::ELleftbnd(struct Point *p)\r
-{\r
- int i, bucket;\r
- struct Halfedge *he;\r
-\r
- /* Use hash table to get close to desired halfedge */\r
- bucket = (int)((p->x - xmin)/deltax * ELhashsize); //use the hash function to find the place in the hash map that this HalfEdge should be\r
-\r
- if(bucket<0) bucket =0; //make sure that the bucket position in within the range of the hash array\r
- if(bucket>=ELhashsize) bucket = ELhashsize - 1;\r
-\r
- he = ELgethash(bucket);\r
- 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\r
- {\r
- for(i=1; 1 ; i += 1)\r
- {\r
- if ((he=ELgethash(bucket-i)) != (struct Halfedge *) NULL)\r
- break;\r
- if ((he=ELgethash(bucket+i)) != (struct Halfedge *) NULL)\r
- break;\r
- };\r
- totalsearch += i;\r
- };\r
- ntry += 1;\r
- /* Now search linear list of halfedges for the correct one */\r
- if (he==ELleftend || (he != ELrightend && right_of(he,p)))\r
- {\r
- do \r
- {\r
- he = he -> ELright;\r
- } 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\r
- he = he -> ELleft; //isn't to the right of\r
- }\r
- else //if the point is to the left of the HalfEdge, then search left for the HE just to the left of the point\r
- do\r
- {\r
- he = he -> ELleft;\r
- } while (he!=ELleftend && !right_of(he,p));\r
-\r
- /* Update hash table and reference counts */\r
- if(bucket > 0 && bucket <ELhashsize-1)\r
- {\r
- if(ELhash[bucket] != (struct Halfedge *) NULL) \r
- {\r
- ELhash[bucket] -> ELrefcnt -= 1;\r
- }\r
- ELhash[bucket] = he;\r
- ELhash[bucket] -> ELrefcnt += 1;\r
- };\r
- return (he);\r
-}\r
-\r
-\r
-/* This delete routine can't reclaim node, since pointers from hash\r
-table may be present. */\r
-void VoronoiDiagramGenerator::ELdelete(struct Halfedge *he)\r
-{\r
- (he -> ELleft) -> ELright = he -> ELright;\r
- (he -> ELright) -> ELleft = he -> ELleft;\r
- he -> ELedge = (struct Edge *)DELETED;\r
-}\r
-\r
-\r
-struct Halfedge * VoronoiDiagramGenerator::ELright(struct Halfedge *he)\r
-{\r
- return (he -> ELright);\r
-}\r
-\r
-struct Halfedge * VoronoiDiagramGenerator::ELleft(struct Halfedge *he)\r
-{\r
- return (he -> ELleft);\r
-}\r
-\r
-\r
-struct Site * VoronoiDiagramGenerator::leftreg(struct Halfedge *he)\r
-{\r
- if(he -> ELedge == (struct Edge *)NULL)\r
- return(bottomsite);\r
- return( he -> ELpm == le ?\r
- he -> ELedge -> reg[le] : he -> ELedge -> reg[re]);\r
-}\r
-\r
-struct Site * VoronoiDiagramGenerator::rightreg(struct Halfedge *he)\r
-{\r
- if(he -> ELedge == (struct Edge *)NULL) //if this halfedge has no edge, return the bottom site (whatever that is)\r
- return(bottomsite);\r
-\r
- //if the ELpm field is zero, return the site 0 that this edge bisects, otherwise return site number 1\r
- return( he -> ELpm == le ? he -> ELedge -> reg[re] : he -> ELedge -> reg[le]);\r
-}\r
-\r
-void VoronoiDiagramGenerator::geominit()\r
-{\r
- float sn;\r
-\r
- freeinit(&efl, sizeof(Edge));\r
- nvertices = 0;\r
- nedges = 0;\r
- sn = (float)nsites+4;\r
- sqrt_nsites = (int)sqrt(sn);\r
- deltay = ymax - ymin;\r
- deltax = xmax - xmin;\r
-}\r
-\r
-\r
-struct Edge * VoronoiDiagramGenerator::bisect(struct Site *s1,struct Site *s2)\r
-{\r
- float dx,dy,adx,ady;\r
- struct Edge *newedge;\r
-\r
- newedge = (struct Edge *) getfree(&efl);\r
-\r
- newedge -> reg[0] = s1; //store the sites that this edge is bisecting\r
- newedge -> reg[1] = s2;\r
- ref(s1);\r
- ref(s2);\r
- newedge -> ep[0] = (struct Site *) NULL; //to begin with, there are no endpoints on the bisector - it goes to infinity\r
- newedge -> ep[1] = (struct Site *) NULL;\r
-\r
- dx = s2->coord.x - s1->coord.x; //get the difference in x dist between the sites\r
- dy = s2->coord.y - s1->coord.y;\r
- adx = dx>0 ? dx : -dx; //make sure that the difference in positive\r
- ady = dy>0 ? dy : -dy;\r
- newedge -> c = (float)(s1->coord.x * dx + s1->coord.y * dy + (dx*dx + dy*dy)*0.5);//get the slope of the line\r
-\r
- if (adx>ady)\r
- {\r
- newedge -> a = 1.0; newedge -> b = dy/dx; newedge -> c /= dx;//set formula of line, with x fixed to 1\r
- }\r
- else\r
- {\r
- newedge -> b = 1.0; newedge -> a = dx/dy; newedge -> c /= dy;//set formula of line, with y fixed to 1\r
- };\r
-\r
- newedge -> edgenbr = nedges;\r
-\r
- //printf("\nbisect(%d) ((%f,%f) and (%f,%f)",nedges,s1->coord.x,s1->coord.y,s2->coord.x,s2->coord.y);\r
-\r
- nedges += 1;\r
- return(newedge);\r
-}\r
-\r
-//create a new site where the HalfEdges el1 and el2 intersect - note that the Point in the argument list is not used, don't know why it's there\r
-struct Site * VoronoiDiagramGenerator::intersect(struct Halfedge *el1, struct Halfedge *el2, struct Point *p)\r
-{\r
- struct Edge *e1,*e2, *e;\r
- struct Halfedge *el;\r
- float d, xint, yint;\r
- int right_of_site;\r
- struct Site *v;\r
-\r
- e1 = el1 -> ELedge;\r
- e2 = el2 -> ELedge;\r
- if(e1 == (struct Edge*)NULL || e2 == (struct Edge*)NULL)\r
- return ((struct Site *) NULL);\r
-\r
- //if the two edges bisect the same parent, return null\r
- if (e1->reg[1] == e2->reg[1])\r
- return ((struct Site *) NULL);\r
-\r
- d = e1->a * e2->b - e1->b * e2->a;\r
- if (-1.0e-10<d && d<1.0e-10)\r
- return ((struct Site *) NULL);\r
-\r
- xint = (e1->c*e2->b - e2->c*e1->b)/d;\r
- yint = (e2->c*e1->a - e1->c*e2->a)/d;\r
-\r
- if( (e1->reg[1]->coord.y < e2->reg[1]->coord.y) ||\r
- (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&\r
- e1->reg[1]->coord.x < e2->reg[1]->coord.x) )\r
- {\r
- el = el1;\r
- e = e1;\r
- }\r
- else\r
- {\r
- el = el2;\r
- e = e2;\r
- };\r
-\r
- right_of_site = xint >= e -> reg[1] -> coord.x;\r
- if ((right_of_site && el -> ELpm == le) || (!right_of_site && el -> ELpm == re))\r
- return ((struct Site *) NULL);\r
-\r
- //create a new site at the point of intersection - this is a new vector event waiting to happen\r
- v = (struct Site *) getfree(&sfl);\r
- v -> refcnt = 0;\r
- v -> coord.x = xint;\r
- v -> coord.y = yint;\r
- return(v);\r
-}\r
-\r
-/* returns 1 if p is to right of halfedge e */\r
-int VoronoiDiagramGenerator::right_of(struct Halfedge *el,struct Point *p)\r
-{\r
- struct Edge *e;\r
- struct Site *topsite;\r
- int right_of_site, above, fast;\r
- float dxp, dyp, dxs, t1, t2, t3, yl;\r
-\r
- e = el -> ELedge;\r
- topsite = e -> reg[1];\r
- right_of_site = p -> x > topsite -> coord.x;\r
- if(right_of_site && el -> ELpm == le) return(1);\r
- if(!right_of_site && el -> ELpm == re) return (0);\r
- if (e->a == 1.0)\r
- {\r
- dyp = p->y - topsite->coord.y;\r
- dxp = p->x - topsite->coord.x;\r
- fast = 0;\r
- if ((!right_of_site & (e->b<0.0)) | (right_of_site & (e->b>=0.0)) )\r
- {\r
- above = dyp>= e->b*dxp;\r
- fast = above;\r
- }\r
- else\r
- {\r
- above = p->x + p->y*e->b > e-> c;\r
- if(e->b<0.0) above = !above;\r
- if (!above) fast = 1;\r
- }\r
-\r
- if (!fast)\r
- {\r
- dxs = topsite->coord.x - (e->reg[0])->coord.x;\r
- above = e->b * (dxp*dxp - dyp*dyp) <\r
- dxs*dyp*(1.0+2.0*dxp/dxs + e->b*e->b);\r
- if(e->b<0.0) above = !above;\r
- }\r
- }\r
- else /*e->b==1.0 */\r
- {\r
- yl = e->c - e->a*p->x;\r
- t1 = p->y - yl;\r
- t2 = p->x - topsite->coord.x;\r
- t3 = yl - topsite->coord.y;\r
- above = t1*t1 > t2*t2 + t3*t3;\r
- }\r
- return (el->ELpm==le ? above : !above);\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::endpoint(struct Edge *e,int lr,struct Site * s)\r
-{\r
- e -> ep[lr] = s;\r
- ref(s);\r
- return;\r
-\r
- if(e -> ep[re-lr]== (struct Site *) NULL)\r
- return;\r
-\r
- clip_line(e);\r
-\r
- deref(e->reg[le]);\r
- deref(e->reg[re]);\r
- makefree((Freenode*)e, &efl);\r
-}\r
-\r
-void VoronoiDiagramGenerator::endpoint(struct Edge *e1,int lr,struct Site * s, struct Edge *e2, struct Edge *e3)\r
-{\r
- e1 -> ep[lr] = s;\r
- ref(s);\r
-\r
- s->coordout.x = s->coord.x;\r
- s->coordout.y = s->coord.y;\r
-\r
- if(e1 -> ep[le] != (struct Site *) NULL && e1 -> ep[re] != (struct Site *) NULL)\r
- {\r
- clip_line(e1);\r
- deref(e1->reg[le]);\r
- deref(e1->reg[re]);\r
- makefree((Freenode*)e1, &efl);\r
- }\r
-\r
- if(e2 -> ep[le] != (struct Site *) NULL && e2 -> ep[re] != (struct Site *) NULL)\r
- {\r
- clip_line(e2);\r
- deref(e2->reg[le]);\r
- deref(e2->reg[re]);\r
- makefree((Freenode*)e2, &efl);\r
- }\r
-\r
- if(e3 -> ep[le] != (struct Site *) NULL && e3 -> ep[re] != (struct Site *) NULL)\r
- {\r
- clip_line(e3);\r
- deref(e3->reg[le]);\r
- deref(e3->reg[re]);\r
- makefree((Freenode*)e3, &efl);\r
- }\r
-\r
- return; \r
-}\r
-\r
-\r
-float VoronoiDiagramGenerator::dist(struct Site *s,struct Site *t)\r
-{\r
- float dx,dy;\r
- dx = s->coord.x - t->coord.x;\r
- dy = s->coord.y - t->coord.y;\r
- return (float)(sqrt(dx*dx + dy*dy));\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::makevertex(struct Site *v)\r
-{\r
- v -> sitenbr = nvertices;\r
- nvertices += 1;\r
- out_vertex(v);\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::deref(struct Site *v)\r
-{\r
- v -> refcnt -= 1;\r
- if (v -> refcnt == 0 ) \r
- makefree((Freenode*)v, &sfl);\r
-}\r
-\r
-void VoronoiDiagramGenerator::ref(struct Site *v)\r
-{\r
- v -> refcnt += 1;\r
-}\r
-\r
-//push the HalfEdge into the ordered linked list of vertices\r
-void VoronoiDiagramGenerator::PQinsert(struct Halfedge *he,struct Site * v, float offset)\r
-{\r
- struct Halfedge *last, *next;\r
-\r
- he -> vertex = v;\r
- ref(v);\r
- he -> ystar = (float)(v -> coord.y + offset);\r
- last = &PQhash[PQbucket(he)];\r
- while ((next = last -> PQnext) != (struct Halfedge *) NULL &&\r
- (he -> ystar > next -> ystar ||\r
- (he -> ystar == next -> ystar && v -> coord.x > next->vertex->coord.x)))\r
- {\r
- last = next;\r
- }\r
- he -> PQnext = last -> PQnext;\r
- last -> PQnext = he;\r
- PQcount += 1;\r
-}\r
-\r
-//remove the HalfEdge from the list of vertices\r
-void VoronoiDiagramGenerator::PQdelete(struct Halfedge *he)\r
-{\r
- struct Halfedge *last;\r
-\r
- if(he -> vertex != (struct Site *) NULL)\r
- {\r
- last = &PQhash[PQbucket(he)];\r
- while (last -> PQnext != he)\r
- last = last -> PQnext;\r
-\r
- last -> PQnext = he -> PQnext;\r
- PQcount -= 1;\r
- deref(he -> vertex);\r
- he -> vertex = (struct Site *) NULL;\r
- };\r
-}\r
-\r
-int VoronoiDiagramGenerator::PQbucket(struct Halfedge *he)\r
-{\r
- int bucket;\r
-\r
- bucket = (int)((he->ystar - ymin)/deltay * PQhashsize);\r
- if (bucket<0) bucket = 0;\r
- if (bucket>=PQhashsize) bucket = PQhashsize-1 ;\r
- if (bucket < PQmin) PQmin = bucket;\r
- return(bucket);\r
-}\r
-\r
-int VoronoiDiagramGenerator::PQempty()\r
-{\r
- return(PQcount==0);\r
-}\r
-\r
-\r
-struct Point VoronoiDiagramGenerator::PQ_min()\r
-{\r
- struct Point answer;\r
-\r
- while(PQhash[PQmin].PQnext == (struct Halfedge *)NULL) {PQmin += 1;};\r
- answer.x = PQhash[PQmin].PQnext -> vertex -> coord.x;\r
- answer.y = PQhash[PQmin].PQnext -> ystar;\r
- return (answer);\r
-}\r
-\r
-struct Halfedge * VoronoiDiagramGenerator::PQextractmin()\r
-{\r
- struct Halfedge *curr;\r
-\r
- curr = PQhash[PQmin].PQnext;\r
- PQhash[PQmin].PQnext = curr -> PQnext;\r
- PQcount -= 1;\r
- return(curr);\r
-}\r
-\r
-\r
-bool VoronoiDiagramGenerator::PQinitialize()\r
-{\r
- int i;\r
-\r
- PQcount = 0;\r
- PQmin = 0;\r
- PQhashsize = 4 * sqrt_nsites;\r
- PQhash = (struct Halfedge *) myalloc(PQhashsize * sizeof *PQhash);\r
-\r
- if(PQhash == 0)\r
- return false;\r
-\r
- for(i=0; i<PQhashsize; i+=1) PQhash[i].PQnext = (struct Halfedge *)NULL;\r
-\r
- return true;\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::freeinit(struct Freelist *fl,int size)\r
-{\r
- fl -> head = (struct Freenode *) NULL;\r
- fl -> nodesize = size;\r
-}\r
-\r
-char * VoronoiDiagramGenerator::getfree(struct Freelist *fl)\r
-{\r
- int i;\r
- struct Freenode *t;\r
-\r
- if(fl->head == (struct Freenode *) NULL)\r
- {\r
- t = (struct Freenode *) myalloc(sqrt_nsites * fl->nodesize);\r
-\r
- if(t == 0)\r
- return 0;\r
-\r
- currentMemoryBlock->next = new FreeNodeArrayList;\r
- currentMemoryBlock = currentMemoryBlock->next;\r
- currentMemoryBlock->memory = t;\r
- currentMemoryBlock->next = 0;\r
-\r
- for(i=0; i<sqrt_nsites; i+=1)\r
- makefree((struct Freenode *)((char *)t+i*fl->nodesize), fl);\r
- };\r
- t = fl -> head;\r
- fl -> head = (fl -> head) -> nextfree;\r
- return((char *)t);\r
-}\r
-\r
-\r
-\r
-void VoronoiDiagramGenerator::makefree(struct Freenode *curr,struct Freelist *fl)\r
-{\r
- curr -> nextfree = fl -> head;\r
- fl -> head = curr;\r
-}\r
-\r
-void VoronoiDiagramGenerator::cleanup()\r
-{\r
- if(sites != 0)\r
- {\r
- free(sites);\r
- sites = 0;\r
- }\r
-\r
- FreeNodeArrayList* current=0, *prev = 0;\r
-\r
- current = prev = allMemoryList;\r
-\r
- while(current->next != 0)\r
- {\r
- prev = current;\r
- current = current->next;\r
- free(prev->memory);\r
- delete prev;\r
- prev = 0;\r
- }\r
-\r
- if(current != 0 && current->memory != 0)\r
- {\r
- free(current->memory);\r
- delete current;\r
- }\r
-\r
- allMemoryList = new FreeNodeArrayList;\r
- allMemoryList->next = 0;\r
- allMemoryList->memory = 0;\r
- currentMemoryBlock = allMemoryList;\r
-}\r
-\r
-void VoronoiDiagramGenerator::cleanupEdges()\r
-{\r
- GraphEdge* geCurrent = 0, *gePrev = 0;\r
- geCurrent = gePrev = allEdges;\r
-\r
- while(geCurrent != 0 && geCurrent->next != 0)\r
- {\r
- gePrev = geCurrent;\r
- geCurrent = geCurrent->next;\r
- delete gePrev;\r
- }\r
-\r
- allEdges = 0;\r
-\r
-}\r
-\r
-void VoronoiDiagramGenerator::pushGraphEdge(float x1, float y1, float x2, float y2)\r
-{\r
- GraphEdge* newEdge = new GraphEdge;\r
- newEdge->next = allEdges;\r
- allEdges = newEdge;\r
- newEdge->x1 = x1;\r
- newEdge->y1 = y1;\r
- newEdge->x2 = x2;\r
- newEdge->y2 = y2;\r
-}\r
-\r
-\r
-char * VoronoiDiagramGenerator::myalloc(unsigned n)\r
-{\r
- char *t=0;\r
- t=(char*)malloc(n);\r
- total_alloc += n;\r
- return(t);\r
-}\r
-\r
-\r
-/* for those who don't have Cherry's plot */\r
-/* #include <plot.h> */\r
-void VoronoiDiagramGenerator::openpl(){}\r
-void VoronoiDiagramGenerator::line(float x1, float y1, float x2, float y2)\r
-{\r
- pushGraphEdge(x1,y1,x2,y2);\r
-\r
-}\r
-void VoronoiDiagramGenerator::circle(float x, float y, float radius){}\r
-void VoronoiDiagramGenerator::range(float minX, float minY, float maxX, float maxY){}\r
-\r
-\r
-\r
-void VoronoiDiagramGenerator::out_bisector(struct Edge *e)\r
-{\r
-\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::out_ep(struct Edge *e)\r
-{\r
-\r
-}\r
-\r
-void VoronoiDiagramGenerator::out_vertex(struct Site *v)\r
-{\r
-\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::out_site(struct Site *s)\r
-{\r
- if(!triangulate & plot & !debug)\r
- circle (s->coord.x, s->coord.y, cradius);\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::out_triple(struct Site *s1, struct Site *s2,struct Site * s3)\r
-{\r
-\r
-}\r
-\r
-\r
-\r
-void VoronoiDiagramGenerator::plotinit()\r
-{\r
- float dx,dy,d;\r
-\r
- dy = ymax - ymin;\r
- dx = xmax - xmin;\r
- d = (float)(( dx > dy ? dx : dy) * 1.1);\r
- pxmin = (float)(xmin - (d-dx)/2.0);\r
- pxmax = (float)(xmax + (d-dx)/2.0);\r
- pymin = (float)(ymin - (d-dy)/2.0);\r
- pymax = (float)(ymax + (d-dy)/2.0);\r
- cradius = (float)((pxmax - pxmin)/350.0);\r
- openpl();\r
- range(pxmin, pymin, pxmax, pymax);\r
-}\r
-\r
-void VoronoiDiagramGenerator::pushpoint(int sitenbr, double x, double y, int boundary)\r
-{\r
- Polygon *s;\r
-\r
- s = &polygons[sitenbr];\r
-\r
- if (s->numpoints == 0)\r
- {\r
- s->pointlist = (PolygonPoint *)malloc(sizeof(struct PolygonPoint)*(s->numpoints+10));\r
- if (!s->pointlist)\r
- {\r
- printf("Out of mem\n");\r
- }\r
- }\r
- else if (s->numpoints % 10 == 0)\r
- {\r
- s->pointlist = (PolygonPoint *)realloc(s->pointlist, sizeof(struct PolygonPoint)*(s->numpoints+10));\r
- if (!s->pointlist)\r
- {\r
- printf("Out of remem\n");\r
- }\r
- }\r
- s->pointlist[s->numpoints].coord.x = x;\r
- s->pointlist[s->numpoints].coord.y = y;\r
- s->pointlist[s->numpoints].angle = atan2f(x-s->coord.x, y-s->coord.y);\r
- s->pointlist[s->numpoints].boundary = boundary;\r
-\r
- if (boundary) s->boundary = 1;\r
-\r
- //printf("point #%d in %d (%lf, %lf) [%d] (%lf, %lf): %lf\n", s->numpoints, sitenbr, s->coord.x, s->coord.y, boundary, x, y, (s->pointlist[s->numpoints].angle/M_PI)*180);\r
-\r
- s->numpoints++;\r
-}\r
-\r
-int VoronoiDiagramGenerator::ccw( Point p0, Point p1, Point p2 )\r
-{\r
- double dx1, dx2, dy1, dy2;\r
-\r
- dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;\r
- dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;\r
-\r
- if (dx1*dy2 > dy1*dx2)\r
- return +1;\r
- if (dx1*dy2 < dy1*dx2)\r
- return -1;\r
- if ((dx1*dx2 < 0) || (dy1*dy2 < 0))\r
- return -1;\r
- if ((dx1*dx1 + dy1*dy1) < (dx2*dx2 + dy2*dy2))\r
- return +1;\r
- return 0;\r
-}\r
-\r
-void VoronoiDiagramGenerator::getSitePoints(int sitenbr, int* numpoints, PolygonPoint** pS)\r
-{\r
- int i, j, c, any, centrevalue, cornerinpolygon[4];\r
-\r
- if (polygons[sitenbr].numpoints == 0)\r
- {\r
- for(c = 0; c < 4; c++)\r
- {\r
- pushpoint(sitenbr, corners[c].x, corners[c].y, 0);\r
- }\r
- }\r
-\r
- qsort(polygons[sitenbr].pointlist, polygons[sitenbr].numpoints, sizeof(PolygonPoint), anglecomp);\r
-\r
- if (polygons[sitenbr].boundary)\r
- {\r
-// printf("\nsite %d is boundary intersection\n", sitenbr);\r
-\r
- for(c = 0; c < 4; c++) cornerinpolygon[c] = 1;\r
-\r
- for(i = 0; i < polygons[sitenbr].numpoints; i++)\r
- {\r
-// printf("Point (%lf,%lf) %d\n", polygons[sitenbr].pointlist[i].coord.x,polygons[sitenbr].pointlist[i].coord.y,polygons[sitenbr].pointlist[i].boundary);\r
- j = i > 0?i-1:polygons[sitenbr].numpoints-1;\r
- if ( (!polygons[sitenbr].pointlist[i].boundary || !polygons[sitenbr].pointlist[j].boundary) &&\r
- (polygons[sitenbr].pointlist[i].coord.x != polygons[sitenbr].pointlist[j].coord.x ||\r
- polygons[sitenbr].pointlist[i].coord.y != polygons[sitenbr].pointlist[j].coord.y))\r
- {\r
-// printf("line side test (%lf,%lf) => (%lf,%lf)\n",polygons[sitenbr].pointlist[i].coord.x,polygons[sitenbr].pointlist[i].coord.y,polygons[sitenbr].pointlist[j].coord.x,polygons[sitenbr].pointlist[j].coord.y);\r
- any = 0;\r
- centrevalue = ccw(polygons[sitenbr].pointlist[i].coord, polygons[sitenbr].pointlist[j].coord, polygons[sitenbr].coord);\r
-//printf(" test against centre (%lf,%lf) %d\n", polygons[sitenbr].coord.x, polygons[sitenbr].coord.y, centrevalue);\r
- for(c = 0; c < 4; c++)\r
- {\r
- if (cornerinpolygon[c])\r
- {\r
-\r
-//printf(" test against corner (%lf,%lf) %d\n", corners[c].x, corners[c].y, ccw(polygons[sitenbr].pointlist[i].coord, polygons[sitenbr].pointlist[j].coord, corners[c]));\r
-\r
- if (centrevalue == ccw(polygons[sitenbr].pointlist[i].coord, polygons[sitenbr].pointlist[j].coord, corners[c]))\r
- {\r
- any = 1;\r
- }\r
- else\r
- {\r
- cornerinpolygon[c] = 0;\r
- }\r
- }\r
- }\r
- if (!any) break;\r
- }\r
- }\r
- if (any)\r
- {\r
- for(c = 0; c < 4; c++)\r
- {\r
- if (cornerinpolygon[c])\r
- {\r
-// printf("adding corger (%lf,%lf) to %d\n", corners[c].x, corners[c].y, sitenbr);\r
- pushpoint(sitenbr, corners[c].x, corners[c].y, 0);\r
- }\r
- }\r
- }\r
- qsort(polygons[sitenbr].pointlist, polygons[sitenbr].numpoints, sizeof(PolygonPoint), anglecomp);\r
-\r
- polygons[sitenbr].boundary = 0;\r
- }\r
-\r
- *numpoints = polygons[sitenbr].numpoints;\r
- *pS = polygons[sitenbr].pointlist;\r
-}\r
-\r
-\r
-void VoronoiDiagramGenerator::clip_line(struct Edge *e)\r
-{\r
- struct Site *s1, *s2, *ts1, *ts2;\r
- float x1=0,x2=0,y1=0,y2=0, temp = 0;\r
- int boundary1 = 0, boundary2 = 0;\r
-\r
-\r
- x1 = e->reg[0]->coord.x;\r
- x2 = e->reg[1]->coord.x;\r
- y1 = e->reg[0]->coord.y;\r
- y2 = e->reg[1]->coord.y;\r
-\r
- if(sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1))) == 0)\r
- {\r
- return;\r
- }\r
-\r
- pxmin = borderMinX;\r
- pxmax = borderMaxX;\r
- pymin = borderMinY;\r
- pymax = borderMaxY;\r
-\r
- if(e -> a == 1.0 && e ->b >= 0.0)\r
- {\r
- s1 = e -> ep[1];\r
- s2 = e -> ep[0];\r
-\r
- ts1 = e -> reg[1];\r
- ts2 = e -> reg[0];\r
- }\r
- else\r
- {\r
- s1 = e -> ep[0];\r
- s2 = e -> ep[1];\r
-\r
- ts1 = e -> reg[0];\r
- ts2 = e -> reg[1];\r
-\r
- };\r
-\r
- if(e -> a == 1.0)\r
- {\r
- if ( s1!=(struct Site *)NULL\r
- && s1->coordout.y > pymin && s1->coordout.y < pymax\r
- && s1->coordout.x > pxmin && s1->coordout.x < pxmax)\r
- {\r
- x1 = s1->coordout.x;\r
- y1 = s1->coordout.y;\r
- }\r
- else\r
- {\r
- boundary1 = 1;\r
- y1 = pymin;\r
- if (s1!=(struct Site *)NULL && s1->coord.y > pymin)\r
- {\r
- y1 = s1->coord.y;\r
- }\r
- if(y1>pymax)\r
- {\r
- y1 = pymax;\r
- }\r
- x1 = e -> c - e -> b * y1;\r
- }\r
-\r
- if ( s2!=(struct Site *)NULL\r
- && s2->coordout.y > pymin && s2->coordout.y < pymax\r
- && s2->coordout.x > pxmin && s2->coordout.x < pxmax)\r
- {\r
- x2 = s2->coordout.x;\r
- y2 = s2->coordout.y;\r
- }\r
- else\r
- {\r
- boundary2 = 1;\r
- y2 = pymax;\r
- if (s2!=(struct Site *)NULL && s2->coord.y < pymax)\r
- y2 = s2->coord.y;\r
- if(y2<pymin)\r
- {\r
- y2 = pymin;\r
- }\r
- x2 = (e->c) - (e->b) * y2;\r
- }\r
-\r
- if (((x1> pxmax) & (x2>pxmax)) | ((x1<pxmin)&(x2<pxmin)))\r
- {\r
- // Line completely outside clipbox\r
- //printf("\nClipLine jumping out(3), x1 = %f, pxmin = %f, pxmax = %f",x1,pxmin,pxmax);\r
- return;\r
- }\r
- if(x1 > pxmax)\r
- {\r
- x1 = pxmax;\r
- y1 = (e -> c - x1)/e -> b;\r
- }\r
- if(x1 < pxmin)\r
- {\r
- x1 = pxmin;\r
- y1 = (e -> c - x1)/e -> b;\r
- }\r
- if(x2 > pxmax)\r
- {\r
- x2 = pxmax;\r
- y2 = (e -> c - x2)/e -> b;\r
- }\r
- if(x2 < pxmin)\r
- {\r
- x2 = pxmin;\r
- y2 = (e -> c - x2)/e -> b;\r
- }\r
- }\r
- else\r
- {\r
- if ( s1!=(struct Site *)NULL\r
- && s1->coordout.y > pymin && s1->coordout.y < pymax\r
- && s1->coordout.x > pxmin && s1->coordout.x < pxmax)\r
- {\r
- x1 = s1->coordout.x;\r
- y1 = s1->coordout.y;\r
- }\r
- else\r
- {\r
- boundary1 = 1;\r
- x1 = pxmin;\r
- if (s1!=(struct Site *)NULL && s1->coord.x > pxmin)\r
- x1 = s1->coord.x;\r
- if(x1>pxmax) \r
- {\r
- //printf("\nClipped (3) x1 = %f to %f",x1,pxmin);\r
- //return;\r
- x1 = pxmax;\r
- }\r
- y1 = e -> c - e -> a * x1;\r
- }\r
-\r
- if ( s2!=(struct Site *)NULL\r
- && s2->coordout.y > pymin && s2->coordout.y < pymax\r
- && s2->coordout.x > pxmin && s2->coordout.x < pxmax)\r
- {\r
- x2 = s2->coordout.x;\r
- y2 = s2->coordout.y;\r
- }\r
- else\r
- {\r
- boundary2 = 1;\r
- x2 = pxmax;\r
- if (s2!=(struct Site *)NULL && s2->coord.x < pxmax)\r
- x2 = s2->coord.x;\r
- if(x2<pxmin)\r
- {\r
- //printf("\nClipped (4) x2 = %f to %f",x2,pxmin);\r
- //return;\r
- x2 = pxmin;\r
- }\r
- y2 = e -> c - e -> a * x2;\r
- }\r
-\r
- if (((y1> pymax) & (y2>pymax)) | ((y1<pymin)&(y2<pymin)))\r
- {\r
- //printf("\nClipLine jumping out(6), y1 = %f, pymin = %f, pymax = %f",y2,pymin,pymax);\r
- return;\r
- }\r
- if(y1 > pymax)\r
- { y1 = pymax; x1 = (e -> c - y1)/e -> a;};\r
- if(y1 < pymin)\r
- { y1 = pymin; x1 = (e -> c - y1)/e -> a;};\r
- if(y2 > pymax)\r
- { y2 = pymax; x2 = (e -> c - y2)/e -> a;};\r
- if(y2 < pymin)\r
- { y2 = pymin; x2 = (e -> c - y2)/e -> a;};\r
- };\r
-\r
- if(sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1))) == 0)\r
- {\r
- return;\r
- }\r
-\r
- pushpoint(ts1->sitenbr, x1, y1, boundary1);\r
- pushpoint(ts2->sitenbr, x2, y2, boundary2);\r
- pushpoint(ts1->sitenbr, x2, y2, boundary2);\r
- pushpoint(ts2->sitenbr, x1, y1, boundary1);\r
-}\r
-\r
-\r
-/* implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,\r
-deltax, deltay (can all be estimates).\r
-Performance suffers if they are wrong; better to make nsites,\r
-deltax, and deltay too big than too small. (?) */\r
-\r
-bool VoronoiDiagramGenerator::voronoi(int triangulate)\r
-{\r
- struct Site *newsite, *bot, *top, *temp, *p;\r
- struct Site *v;\r
- struct Point newintstar;\r
- int pm;\r
- struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;\r
- struct Edge *e, *e2, *e3;\r
-\r
- PQinitialize();\r
- bottomsite = nextone();\r
- out_site(bottomsite);\r
- bool retval = ELinitialize();\r
-\r
- if(!retval)\r
- return false;\r
-\r
- newsite = nextone();\r
- while(1)\r
- {\r
-\r
- if(!PQempty())\r
- newintstar = PQ_min();\r
-\r
- //if the lowest site has a smaller y value than the lowest vector intersection, process the site\r
- //otherwise process the vector intersection \r
-\r
- if (newsite != (struct Site *)NULL && (PQempty() || newsite -> coord.y < newintstar.y\r
- || (newsite->coord.y == newintstar.y && newsite->coord.x < newintstar.x)))\r
- {/* new site is smallest - this is a site event*/\r
- out_site(newsite); //output the site\r
- lbnd = ELleftbnd(&(newsite->coord)); //get the first HalfEdge to the LEFT of the new site\r
- rbnd = ELright(lbnd); //get the first HalfEdge to the RIGHT of the new site\r
- bot = rightreg(lbnd); //if this halfedge has no edge, , bot = bottom site (whatever that is)\r
- e = bisect(bot, newsite); //create a new edge that bisects \r
- bisector = HEcreate(e, le); //create a new HalfEdge, setting its ELpm field to 0 \r
- ELinsert(lbnd, bisector); //insert this new bisector edge between the left and right vectors in a linked list \r
-\r
- if ((p = intersect(lbnd, bisector)) != (struct Site *) NULL) //if the new bisector intersects with the left edge, remove the left edge's vertex, and put in the new one\r
- { \r
- PQdelete(lbnd);\r
- PQinsert(lbnd, p, dist(p,newsite));\r
- };\r
- lbnd = bisector; \r
- bisector = HEcreate(e, re); //create a new HalfEdge, setting its ELpm field to 1\r
- ELinsert(lbnd, bisector); //insert the new HE to the right of the original bisector earlier in the IF stmt\r
-\r
- if ((p = intersect(bisector, rbnd)) != (struct Site *) NULL) //if this new bisector intersects with the\r
- {\r
- PQinsert(bisector, p, dist(p,newsite)); //push the HE into the ordered linked list of vertices\r
- };\r
- newsite = nextone();\r
- }\r
- else if (!PQempty()) /* intersection is smallest - this is a vector event */\r
- {\r
- lbnd = PQextractmin(); //pop the HalfEdge with the lowest vector off the ordered list of vectors \r
- llbnd = ELleft(lbnd); //get the HalfEdge to the left of the above HE\r
- rbnd = ELright(lbnd); //get the HalfEdge to the right of the above HE\r
- rrbnd = ELright(rbnd); //get the HalfEdge to the right of the HE to the right of the lowest HE \r
- bot = leftreg(lbnd); //get the Site to the left of the left HE which it bisects\r
- top = rightreg(rbnd); //get the Site to the right of the right HE which it bisects\r
-\r
- out_triple(bot, top, rightreg(lbnd)); //output the triple of sites, stating that a circle goes through them\r
-\r
- v = lbnd->vertex; //get the vertex that caused this event\r
- makevertex(v); //set the vertex number - couldn't do this earlier since we didn't know when it would be processed\r
- e2 = lbnd->ELedge;\r
- e3 = rbnd->ELedge;\r
- endpoint(lbnd->ELedge,lbnd->ELpm,v); //set the endpoint of the left HalfEdge to be this vector\r
- endpoint(rbnd->ELedge,rbnd->ELpm,v); //set the endpoint of the right HalfEdge to be this vector\r
- ELdelete(lbnd); //mark the lowest HE for deletion - can't delete yet because there might be pointers to it in Hash Map \r
- PQdelete(rbnd); //remove all vertex events to do with the right HE\r
- ELdelete(rbnd); //mark the right HE for deletion - can't delete yet because there might be pointers to it in Hash Map \r
- pm = le; //set the pm variable to zero\r
-\r
- if (bot->coord.y > top->coord.y) //if the site to the left of the event is higher than the Site\r
- { //to the right of it, then swap them and set the 'pm' variable to 1\r
- temp = bot;\r
- bot = top;\r
- top = temp;\r
- pm = re;\r
- }\r
- e = bisect(bot, top); //create an Edge (or line) that is between the two Sites. This creates\r
- //the formula of the line, and assigns a line number to it\r
- bisector = HEcreate(e, pm); //create a HE from the Edge 'e', and make it point to that edge with its ELedge field\r
- ELinsert(llbnd, bisector); //insert the new bisector to the right of the left HE\r
- endpoint(e, re-pm, v, e2, e3); //set one endpoint to the new edge to be the vector point 'v'.\r
- //If the site to the left of this bisector is higher than the right\r
- //Site, then this endpoint is put in position 0; otherwise in pos 1\r
- deref(v); //delete the vector 'v'\r
-\r
- //if left HE and the new bisector don't intersect, then delete the left HE, and reinsert it\r
- if((p = intersect(llbnd, bisector)) != (struct Site *) NULL)\r
- {\r
- PQdelete(llbnd);\r
- PQinsert(llbnd, p, dist(p,bot));\r
- };\r
-\r
- //if right HE and the new bisector don't intersect, then reinsert it\r
- if ((p = intersect(bisector, rrbnd)) != (struct Site *) NULL)\r
- {\r
- PQinsert(bisector, p, dist(p,bot));\r
- };\r
- }\r
- else break;\r
- };\r
-\r
- for(lbnd=ELright(ELleftend); lbnd != ELrightend; lbnd=ELright(lbnd))\r
- {\r
- e = lbnd -> ELedge;\r
-\r
- clip_line(e);\r
- };\r
-\r
- cleanup();\r
-\r
- return true;\r
-}\r
-\r
-\r
-int scomp(const void *p1,const void *p2)\r
-{\r
- struct Point *s1 = (Point*)p1, *s2=(Point*)p2;\r
- if(s1 -> y < s2 -> y) return(-1);\r
- if(s1 -> y > s2 -> y) return(1);\r
- if(s1 -> x < s2 -> x) return(-1);\r
- if(s1 -> x > s2 -> x) return(1);\r
- return(0);\r
-}\r
-\r
-int spcomp(const void *p1,const void *p2)\r
-{\r
- struct SourcePoint *s1 = (SourcePoint*)p1, *s2=(SourcePoint*)p2;\r
- if(s1 -> y < s2 -> y) return(-1);\r
- if(s1 -> y > s2 -> y) return(1);\r
- if(s1 -> x < s2 -> x) return(-1);\r
- if(s1 -> x > s2 -> x) return(1);\r
- return(0);\r
-}\r
-\r
-int anglecomp(const void * p1, const void * p2)\r
-{\r
- PolygonPoint * s1 = (PolygonPoint *)p1 ;\r
- PolygonPoint * s2 = (PolygonPoint *)p2 ;\r
-\r
- if (s1->angle < s2->angle) {\r
- return (-1) ;\r
- }\r
- if (s1->angle > s2->angle) {\r
- return (1) ;\r
- }\r
- return (0) ;\r
-}\r
-\r
-/* return a single in-storage site */\r
-struct Site * VoronoiDiagramGenerator::nextone()\r
-{\r
- struct Site *s;\r
- if(siteidx < nsites)\r
- {\r
- s = &sites[siteidx];\r
- siteidx += 1;\r
- return(s);\r
- }\r
- else\r
- return( (struct Site *)NULL);\r
-}\r
-\r