CGAL users discussion list

[Simon Perkins <>]

Hi

Would this kind of error stem from the use of an inexact number type? It's the obvious culprit, yet it seems strange to my intuition that using a Delaunay Triangulation as constraints for further Delaunay Refinement would cause issues.

Simon

On Tue, Mar 9, 2010 at 1:59 PM, Simon Perkins <> wrote:

Dear All

I'm generating some random Delaunay Triangulations and I ran into a Precondition Violation in the Mesh_2 Package. I'm using the CGAL 3.5.1 and the Exact_predicates_inexact_constructions kernel.

I create a Delaunay Triangulation by creating 4 constraints corresponding to the sides of a square and then use refine_Delaunay_mesh_2 to generate a random Delaunay Triangulation within that square. I then save that Triangulation using a custom file format.

I read in the Triangulation from the file and specify the triangles as constraints on a new Triangulation. I then attempt to use refine_Delaunay_mesh_2 to further refine this new Triangulation.This is when I get the following precondition violation

terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: orientation(fh->vertex(0)->point(), fh->vertex(1)->point(), fh->vertex(2)->point()) != COLLINEAR
File: /home/simon/usr/local/include/CGAL/Mesh_2/Refine_faces.h
Line: 275
Aborted

I turned on CGAL_MESH_2_DEBUG_BAD_FACES and got the following output

bad_faces.erase(65.118 27.5913,65.118 27.5913,65.118 27.5913)
bad_faces.erase(65.118 27.5913,65.118 27.5913,65.118 27.5913)
bad_faces.erase(65.118 27.5913,65.118 27.5913,65.118 27.5913)
bad_faces.erase(65.118 27.5913,65.118 27.5913,65.118 27.5913)
bad_faces.erase(65.118 27.5913,65.118 27.5913,65.118 27.5913)
bad_faces.erase(28.3594 90.4687,28.3594 90.4688,28.3594 90.4688)
bad_faces.erase(28.3594 90.4688,28.3594 90.4687,28.3594 90.4687)
push_in_bad_faces(28.3594 90.4688,28.3594 90.4688,28.3594 90.4688)
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: orientation(fh->vertex(0)->point(), fh->vertex(1)->point(), fh->vertex(2)->point()) != COLLINEAR
File: /home/simon/usr/local/include/CGAL/Mesh_2/Refine_faces.h
Line: 275
Aborted

This happens whether I just use Delaunay_mesh_criteria_2 or Delaunay_mesh_size_criteria_2. I've checked the areas of the triangles in the Triangulation just before performing the second Delaunay refinement and they all seem to be decently sized - none of them seem obviously degenerate. Any ideas on what might be causing this issue?

The wierd thing is that it only seems to happen when my custom file describes this random Delaunay Triangulation that I've created. Other scenes that I've manually created seem to handle the subsequent Delaunay Refinement fine.

thanks for your time
  Simon