Skip to Content.
Sympa Menu

cgal-discuss - Delaunay3D and infinite cells bug??

Subject: CGAL users discussion list

List archive

Delaunay3D and infinite cells bug??


Chronological Thread 
  • From: "Wesley Smith" <>
  • To:
  • Subject: Delaunay3D and infinite cells bug??
  • Date: Wed, 19 Sep 2007 23:16:57 -0700
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=UOwp00xC6MNKgoKntQCWT4AasjMQuKGY4fXHBbjRITqh2Hff2+ZFXqizMJDwY4LRVE+f4Ertx+rOk3oGQbO59h1m5Up4synLLSa+N6P0WNk1u+fVuIZBAQ2fX1miCIoNUXNJBDtiH2eg76r3DZrN43o2fnUzifklD24pGGk1YW8=

I've found a case in the delaunay_3d class where a vertex on the crust
of a triangulation doesn't have any incident infinite cells. Should
this ever happen or is this a bug? Here's are the points I'm
inserting:

for(int i=-1; i <= 1; i++) {
for(int j=-1; j <= 1; j++) {
for(int k=-1; k <= 1; k++) {
L.push_front(Point(i, j, k));
}
}
}

dg = new DG(L.begin(), L.end());

The test:

for(Finite_vertices_iterator fv = dg->finite_vertices_begin();
fv != dg->finite_vertices_end(); fv++) {
Delaunay_vertex_handle v(fv);


vector<Cell_handle> cells;
dg->incident_cells(v, std::back_inserter(cells));

int c = 0;
int size = cells.size();
for(c = 0; c < size; c++) {
if(dg->is_infinite(cells[c])) {
break;
}
}

if(c == size) {
Point p = v->point();
printf("NOT ON CRUST %f %f %f\n", p.x(), p.y(),
p.z());

continue;
}
...

Of the points inserted, this test determines that (0, 0, 0) and (1, 0,
0) are not on the crust (i.e. of no incident infinite cells). Clearly
(0, 0, 0) is valid, but (1, 0, 0) is not. I ran some further tests,
revering the insertion order of the points and that case, (0, 0, 0)
and (-1, 0, 0) are determined to not have any incident infinite cells.

It was my understanding that all vertices on the crust of the
triangulation would have at least one infinite cell. Is my test just
using some artifact of the triangulation algorithm or should I be able
to count on it? Essentially, I'm looking for a fast method to test
for a vertex being on the crust (not an arbitrary point but a vertex
inserted into the triangulation). I'm a bit surprised there isn't a
method for this actually, but any help in figuring this out will be
greatly appreciated.

thanks,
wes



Archive powered by MHonArc 2.6.16.

Top of Page