CGAL users discussion list

[Marc Glisse <>]

On Sat, 17 Jul 2021, Renaud GILLON wrote:

> 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 ?

Hello,

the computations are performed exactly, as if in infinite precision, so 
that's unlikely to be the problem. It is possible that there is a bug in 
the logic of the walk that affects degenerate cases, but I don't have 
enough information to say if that is the case, you could also be 
misinterpreting the result. Do you think you could prepare a testcase that 
demonstrates a point badly located? Please try to minimize it (low 
dimension, few points, short code).

--
Marc Glisse