CGAL users discussion list

[Simon Perkins <>]

Hi Monique

> I would say that it is not the CGAL design that precludes your approach,
>  but just the usual definition of a triangulation of a set of points in 
> R^3 in computational geometry: a triangulation is a simplicial complex 
> that partitions the convex hull of the points.
> CGAL triangulations implement this definition.
>
> The answer to your initial question also depends on what you want to do 
> with your triangulation when it is stored as a CGAL object.
> If you only want to store it and traverse the data structure, you can always use a Triangulation_data_structure_3, after completing your triangulation in order to ensure that it becomes a combinatorial ball (see Chapter 40). This can be done by adding one special vertex, and cells (which you can 
> mark) connecting it to the facets of your polyhedron P, exactly as I 
> said in my previous email (you must still be careful with orientation of
>  the combinatorial cells). The Triangulation_data_structure_3 does not 
> care about the geometric embedding (you can still store points in the 
> vertices), so, it would work. But then you cannot use any geometric algorithm taken from Triangulation_3.

Thanks for the clear explanation. I made a conceptual mistake regarding the purposes of Triangulation_3 vs Triangulation_data_structure_3. In some sense, I've always viewed Triangulation_data_structure_3 as an "internal" class of Triangulation_3 rather than something that can be used in its own right. Indeed, the fact that it has its own manual chapter makes a lot more sense now...

I wonder if there is some stronger way to highlight this, perhaps by moving the TDS chapter forward in front of the Triangulation chapter? I say this not as a criticism of the manuals (which I think are very good), but perhaps to save yourself from users with questions like "Why can't I force my square peg into this round hole?" ;)

kind regards
   Simon

On Thu, Jul 19, 2012 at 9:17 AM, Monique Teillaud <> wrote:

Hi Simon,

I'm realising the naivety of my approach. I think I went through the
same thought process some years ago with 2D Triangulations before
deciding to use Constrained Triangulations to read in the points and
edges of the faces.

If I understand correctly, your input triangulation is the triangulation of the interior of a polyhedron P.
Unlike in R^2, a constrained triangulation of a polyhedron does not always exist in R^3 (see the Schönhardt polyhedron). That's why we don't have a CGAL::Constrained_triangulation_3.

I understand that inserting vertices of the external triangulation via
the T.insert* methods is the preferred way of constructing a
Triangulation_3. However, if I understand correctly, this will not
necessarily preserve the tetrahedrons that I'm trying to represent,

right

because once points are added outside the convex hull for example, CGAL
will connect that point to all other points visible from it.

Not only because of this. Also in the interior of your polyhedron P, there is no reason why you would find the same tetrahedra.

Is there some generally accepted way of preserving this connectivity
information during the vertex insertion process? I tried calling
T.insert(const Point & p, Face_handle fh) with fh set to the infinite
cells that I was trying to "extend" the triangulation into, but  this
also seems to exhibit the point connection behaviour for points external
to the convex hull.

Am I trying to do something that CGAL's design precludes?

I would say that it is not the CGAL design that precludes your approach, but just the usual definition of a triangulation of a set of points in R^3 in computational geometry: a triangulation is a simplicial complex that partitions the convex hull of the points.
CGAL triangulations implement this definition.

The answer to your initial question also depends on what you want to do with your triangulation when it is stored as a CGAL object.
If you only want to store it and traverse the data structure, you can always use a Triangulation_data_structure_3, after completing your triangulation in order to ensure that it becomes a combinatorial ball (see Chapter 40).
This can be done by adding one special vertex, and cells (which you can mark) connecting it to the facets of your polyhedron P, exactly as I said in my previous email (you must still be careful with orientation of the combinatorial cells). The Triangulation_data_structure_3 does not care about the geometric embedding (you can still store points in the vertices), so, it would work.
But then you cannot use any geometric algorithm taken from Triangulation_3.

Best,
        Monique Teillaud

On Wed, Jul 18, 2012 at 6:49 PM, Monique Teillaud

< <mailto:Monique.Teillaud@inria.fr>> wrote:

    Hi,

    [Reminder: <mailto:> is

    the up-to-date address for this mailing list.
    It replaced the old

    <mailto:cgal-discuss@sophia.inria.fr>]

    * Each facet p,q,r of the convex hull is
    - the finite facet of an infinite cell p,q,r,inf
    - one of the facets of a finite cell p,q,r,s
    These two cells must be neighbors in the data structure.
    You must be very careful with orientation (see Sec 39.1)

    * When two facets p,q,r and p,q,s of the convex hull share a common
    edge p,q, then their respective infinite cells p,q,r,inf and
    p,q,s,inf are neighbors through a common facet p,q,inf.
    Here again, be careful with orientation.


    In fact, it is easier (and safer) to just read the vertices of your
    external triangulation, and construct a CGAL triangulation from
    scratch by inserting the corresponding points...

    Best,
             Monique Teillaud

    Le 18/07/12 17:56, Simon Perkins a écrit :

        Hello

        I'm writing a loader that will read information from an external
        file
        format into the CGAL Triangulation_3 data structure. One thing
        that may
        be problematic is that the file format doesn't explicitly define the
        infinite cells intrinsic to CGAL's representation and so I will
        have to
        create them myself. I don't find this too daunting but I'm not
        sure how
        the neighbours of an infinite cell should be configured. It
        seems clear
        to me that the one can set the neighbour of the infinite vertex
        to be
        the finite cell sharing a facet with the infinite cell, but I'm
        not sure
        how to handle the neighbours of the other three vertices on the
        facet
        itself.

        Would it be valid to set them to a random finite cell for example?

        kind regards
            Simon

--
Monique Teillaud
INRIA Sophia Antipolis - Méditerranée
http://www.inria.fr/sophia/members/Monique.Teillaud/

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