CGAL users discussion list

[Monique Teillaud <>]

Le 19/07/12 12:21, Simon Perkins a écrit :
> 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?" ;)

we sometimes get worse questions than that ;)
In fact, we put Triangulation_3 before Triangulation_data_structure_3 
because we thought that more users need Triangulation_3. I guess that 
the inverse ordering would probably cause more/different questions...

best,
        Monique



> On Thu, Jul 19, 2012 at 9:17 AM, Monique Teillaud
> <
>  
> <mailto:>>
>  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:>
>         <
>         
> <mailto:>>>
>  wrote:
>
>              Hi,
>
>              [Reminder: 
>
>         
> <mailto:>
>  
> <mailto:
>         
> <mailto:>>
>  is
>
>              the up-to-date address for this mailing list.
>              It replaced the old 
>
>         
> <mailto:>
>         <
>         
> <mailto:>>]
>
>
>              * 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/
>     <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
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>


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