Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Slivers seem to fool the location algorithm in CGAL Delaunay_triangulation

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Slivers seem to fool the location algorithm in CGAL Delaunay_triangulation


Chronological Thread 
  • From: Renaud GILLON <>
  • To:
  • Subject: Re: [cgal-discuss] Slivers seem to fool the location algorithm in CGAL Delaunay_triangulation
  • Date: Sun, 25 Jul 2021 17:43:22 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Neutral ; spf=None
  • Ironport-hdrordr: A9a23:gApNMKARZ/jVqX3lHelK55DYdb4zR+YMi2TDtnoBMSC9F/byqynApoV/6faZskdyZJhko6HiBEDiexLhHPxOkO4s1N6ZNWGN1VdAbrsD0WKI+UyHJ8SRzJ8l6U9EG5IOcqyMfCQK8reF3OGae+xQsOVuFs2T9JPjJ0wEd3AaV0ii1WtEIzfePEl/RAwDI4E4Gpqa7s8Cgza7Y3wYYoCaKxA+Loz+ThHw+64PYXM9dmUaAcC14w9B2tbBYmulNiF3aUI8/V8UmVK15jDE2g==
  • Ironport-phdr: A9a23:RdRCgRD9Kq7GxeHwe0J2UyQUv0QY04WdBeb1wqQuh78GSKm/5ZOqZBWZua81ygOTFtWKo9t/yMPu+5j6XmIB5ZvT+FsjS7drEyE/tMMNggY7C9SEA0CoZNTjbig9AdgQHAQ9pyLzPkdaAtvxaEPPqXOu8zESBg//NQ1oLejpB4Lelcu62/6u95HJbAhEmjWxbLB2IR6rsQjfq84ajJd4JK0s0BXJuHxIe+pXxWNsO12emgv369mz8pB+7Sleouot+MFcX6r0eaQ4VqFYAy89M28p/s3rtALMQhWJ63ABT2gZiBtIAwzC7BHnQpf8tzbxu+Rh1CWGO8D9ULY5Uimg4ah2Uh/lkCgINzA7/2/XhMJ+j79Vrgy9qBFk2YHYfJuYOeBicq/Bf94XQ3dKUMZLVyxGB4Oxd5cBAPQHPelCsonyukYFoxq9CweqAu3h0ydGjWLx0K0gzeshFxvJ3BE9EN4Uv3TUrdH1NKMVUeCz16TI1jXCYO5I1jf56YjIbhAgreuQUrJ3dMrc0E8iHB7KgVuMs4LqJS+V1vgTvGiB6eptTfyjhm4opQ9xvjSi29sghpXJi4wbxV3J+iV0zZorKNC5R0B1btGpHpROuiyYOYV4Qt4uT39otig6xbMKpZy2cicMxZ86yRDfbPmHfJKJ4hLlTOuRIDF4hGhkeL2lnRqy/1KgxvXnVsi0zVlFsC5FktjQtnENzRDf8NSISvx4/ku5wjaO1x3c5f9AIUA1iaraK4QtzaI3lpoWt0nIAyz4mF3ugaKXdUgo4Oml5uT9brn7uJOROZV4hw//P6g2hMCzHeA1PhINUmWb4+iwyqPv8VDjTLhFjvA7lLTSvorAKsQBvKG5BhdY0oY95Ba7CDeryM8YkmcdLFJbZh2HlZblNlPQLPzhEPuzmVqtnylwyPzfPr3hBY7NLmTCkLfncrZx8VJTyA02zdxH5pJUDK8OIO7rV0Lwt9HUFB40Pgyuz+r6Ftlw2JkSVGyOD6OBNaPdq16I5uYhI+mWY48VvS7wK+I76P7ol3A5hEIScbOm3ZsWbHC4GvNmI0OCbHr3gtYODHkFvg4/TOz2iFyOSyJcZ3G3X64k/DE0FJqmDZvfRoCqmLGOwCi7EYdSZmxfF1+MEGzoeJmZW/cXcyKfOdRhkzwBVbi5UYAtzxCutAngy7pmNOXY4CMYtYiwnOVz/PDZwBEu6SRvXYPayHCIV2gyn2USRjZw0ro4ul140l7E0K52hLtTGtVXov9ISQwnLoWP8uphFtrSRgfFK9eVVE69EJLhGiA0Vtt3wtkUYk87Fc/llQHGxyPtArkbkPuAC5Uwt67dxHPsPN0u9nDdyaMdgkk6F8tTKXW91Ok47BnWH4ePkkODlq/se75bxz/I7G7EzGyAuwZTXwd0FKnERnsCfVCFkdOs7UzLS/qiCK8sLxBa4c+EMKpDLNPz3ntcQ/K2AtnYan+900iRITKv4PvYdofscngRmircDEwDlSgI7HqLMQkiF2GqpGeIX28mLk7mf065qbo2k3i8VEJhl2lijmV62qCr9wRP2qbZErUM07hBuCA6tzRyExC22NeEU7JoQiJ6balRZdIh8RFM0meL72SV0bS7Pqxvgl8CYkJ8uEa8jX1K

Hello,

After checking my data thoroughly, it appeared that the filtering implemented in the generation of random test points had been relaxed and that I was effectively getting outside points and in my processing these were mapped to the nearest "finite" cell which happened to be slivers (by coïncidence because there were slivers on the faces closest to where outside test points were allowed by the relaxed filtering).

In conclusion, I did not find any evidence that slivers are fooling the location algorithm or that there is any bug in the location algorithm for D-dimensional Delaunay triangulations in version 5.1.

Regards,


Renaud


Le dim. 18 juil. 2021 à 09:57, Marc Glisse <> a écrit :
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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




--
Renaud GILLON

SYDELITY
"Scaleable Virtual Prototyping"

Mobile : +32 (0)495 27 65 65
E-mail : 
Web:     www.sydelity.com 



Archive powered by MHonArc 2.6.19+.

Top of Page