CGAL users discussion list

[Monique Teillaud <>]

Le 19/03/13 13:45, Philipp Blanke a écrit :
> Hello Monique & Sebastien ,
>
> as I understand the incremental algorithm, if a tetrahedron T is marked
> degenerated and a point would be inserted into its circumsphere, T would
> be destroyed and the hole re-triangulated. The newly constructed tets
> would not automatically inherit the "degenerate" flag from T.
>
> You suggest that a marked tetrahedron could lose its degenerate status,
> since there could be an insertion of a point, so that there are not >4
> points cospherical anymore. But such a point would have to be inserted
> inside T's circumsphere.

I am not sure what Sébastien was referring to.
But at least if you remove all points that were cospherical with T's 
vertices, then T becomes non-degenerate.

Actually my point is not related with this. I just don't see how to easily
- 'catch' cospherical cases, since this is hidden in the (perturbed) 
predicate, which never returns 0
- and pass the information to the TDS, which is actually creating 
tetrahedra.
At first sight, I would say that, assuming it is possible, it would 
require a non-trivial patching of the CGAL code.

> Was there an email from Laurent regarding this topic on the list?!

Laurent answered the email that you sent last week, with subject: Fwd: 
Delaunay_triangulation_3 degenerate case

best,
        Monique

> I did
> not find one. But Monique's email has pointed me into the right
> direction. Thank you!
>
> Best regards!
> Philipp
>
>
>
>
> On Tue, Mar 19, 2013 at 9:34 AM, Sebastien Loriot (GeometryFactory)
> <
>  
> <mailto:>>
>  wrote:
>
>     I think if you proceed like this, since the algorithm is
>     incremental, you can end up with tetrahedra marked that are no
>     longer degenerated.
>
>     I think the method Laurent proposed you is the best.
>
>     Sebastien.
>
>
>     On 03/19/2013 09:07 AM, Philipp Blanke wrote:
>
>         Hello!
>
>         I'd like to construct a Delaunay complex for a point set that
>         contains
>         several degenerate cases, i. e., >4 cospherical points. The doc says
>         that the  Delaunay_triangulation_3 code solves the local
>         disambiguity by
>         using a perturbation scheme.
>
>         If the tetrahedra that were constructed using this scheme would be
>         marked, I could merge them in a preprocessing step to get a Delaunay
>         complex consisting of convex polyhedra.
>
>         Where in the code is the perturbation scheme used to select a
>         possible
>         tetrahedrization? I did not find this.
>
>         Best regards,
>         Philipp
>
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://sympa.inria.fr/sympa/__info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>


--
Monique Teillaud
http://www.inria.fr/sophia/members/Monique.Teillaud/
INRIA Sophia Antipolis - Méditerranée
Institut National de Recherche en Informatique et Automatique