CGAL users discussion list

[Renaud GILLON <>]

Hello,

Using the CGAL d-dimensional Delaunay_triangulation class with the Epick kernel, I want to generate triangulations in order to perform barycentric interpolation of a multi-dimensional function sampled along with its derivatives at the location of the vertices of the triangulation.

Because of the nature of the sampled function, the sampling grid is rather anisotropic (the spacing in one direction is 1.0E4 times larger than in the others) in some region. Despite this difficulty, the Delaynay mesh is nice (uniform volumes) on the inside. It just has slivers (quasi-zero volume cells) on the outside.

Initially, I was hoping to push the slivers out by adding "padding" (dummy points) on the periphery where the slivers are occurring, so that test points would always reside in a well formed cell.

However, I noticed that slivers seem to behave as "strange attractors" for the point location algorithm. A large number of test points located close to the boundary gets located in slivers, despite the fact that normally none of these points should fall in there. The number of points that the locate() method assigns to slivers is also totally out of proportion to the fraction of the outer shell occupied by the slivers.

So the impression is that the slivers are somehow fooling the location algorithm. Could it be that the "inside / outside" detection depends on the sign of some computed quantity (something related to a matrix determinant) and that in the case of slivers, the result should be "zero" but is not due to numerical errors and that the location algorithm then "concludes" that the point is inside the sliver -- which is not the case, just a results of bad conditionning ?

Is there a way to specify a threshold value for the quantity used to make the "inside / outside" test so that the problem related to slivers can be avoided ?

Regards,

Renaud

--

Renaud GILLON SYDELITY "Scaleable Virtual Prototyping" Mobile : +32 (0)495 27 65 65 E-mail : Web: www.sydelity.com