PDA

View Full Version : voronoi.h: missing edges?


jonas
03-24-2009, 02:47 PM
When printing the edges of a voronoi diagram, it seems to me the last edge of each cell is lacking (see attached program output produced by the code below). Can you confirm this?
In order to get for each cell a last edge with an ending point equal to the starting point of the first edge, I use in Voronoi::Voronoi() ifirst instead of jfirst:

voronoi.h (changed):

jfirst = j;
ifirst = i; // <- save first i
vfirst = ccp = circumcircle(pts[p],pts[i],pts[j]).center;
while (1) {
key = hashfn.int64(i) - hashfn.int64(p);
if ( ! linehash->get(key,k) ) throw("Delaunay is incomplete");
cc = circumcircle(pts[p],pts[k],pts[i]).center;
segs[nseg++] = Voredge(ccp,cc,p);
if(k == ifirst) break; // <- use ifirst instead of jfirst to close the loop
ccp = cc;
j=i;
i=k;
}



Attached output is produced by:



srand((unsigned)time(0));

// Generate random points
int numPoints = 120;
vector<Point<2> > pvec;
double minPos = 0.01;
double maxPos = 0.99;
for (int j = 0; j < numPoints; j++) {
Point<2> p;
p.x[0] = minPos + ((float)((maxPos-minPos)*rand()))/((float)RAND_MAX);
pvec.push_back(p);
}

// compute voronoi
voronoi = new Voronoi(pvec);

// Write voronoi vertices
for(int i = 0; i < voronoi->nseg; i++){
::Voredge edge = voronoi->segs[i];
cout << "Site: " << edge.nearpt <<
"\t\tedge: p0: " << edge.p[0].x[0] << " " << edge.p[0].x[1] <<
"\tp1: " << edge.p[1].x[0] << " " << edge.p[1].x[1] << endl;
}

delete voronoi;
voronoi = NULL;


Thanks in advance for any clarification.
Best regards,
Jonas