CGAL users discussion list

[Sebastien Loriot <>]

On 7/1/22 08:45, Johnny Bigert ( via cgal-discuss 
Mailing List) wrote:
> Hi Sebastien,
>
> Thank you for the link and the swift response, it was very helpful. I 
> was trying to read up on CDTs, but the description is a bit abstract. 
> Would you care to explain a few things about the linked example?
>
>  1. In simple words, what does a CDT do? I guess it incrementally
>     creates a triangulation as we repeatedly call
>     cdt.insert_constraint(start, end)?

Constraints endpoints are inserted and the triangulation is made 
Delaunay. Then some edge flips are done to force the constraints
to be in the triangulation (there is a theorem that proves that it
is always possible in 2D)/

>  2. I got the impression from Wikipedia
>     (https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation
>     <https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation>)
>     that a CDT tries to keep the constrained edges (they mention an
>     example with "breaklines along rivers")? But in the linked example,
>     we use insert_constraint on /all/ the edges of the mesh, and keeping
>     all edges makes no sense, so I must be missing something :)
It is indeed too much work but since we don't know the edges that are on 
the silhouette that is a brute-force way to get them. Also note that in
case of intersection of constraints, edges will be split.

>  3. In the linked example, what does the cdt.is_constrained(e) call do
>     exactly? It can't give us back the insert_constraint-inserted edges
>     (although the name seems to suggest it). So I guess it gives us the
>     outer borders?

is_constrained() returns whether an edge present in the triangulation
has been constrained by the user (or the initial edge if it has been 
split).

>  4. If cdt.is_constrained(e) gives us the outer borders, then why do we
>     iterate over faces, look at neighbors etc, why not iterate over
>     edges directly?

To get the silhouette, you need to start from the infinite vertex and 
collect all the constrained edges that can be reached without crossing
a constrained edge. It is the first iteration of this example:
https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html

If you want to get internal silhouette (like if you input mesh is a 
torus) then you'll need another method.

HTH

Sebastien


> Thank you.
>
>      Best regards, Johnny
>
> On Thu, Jun 30, 2022 at 2:18 PM Sebastien Loriot < 
> <>> wrote:
>
>     Hi,
>
>     this thread talks about this topic:
>
>     https://github.com/CGAL/cgal/discussions/6472
>     <https://github.com/CGAL/cgal/discussions/6472>
>
>     Sebastien.
>
>     On 6/30/22 12:51, Johnny Bigert (
>     <> via cgal-discuss
>     Mailing List) wrote:
>      > Hi,
>      >
>      > I would like to kindly ask for ideas regarding a problem I'm
>     trying to
>      > solve.
>      >
>      > I have a triangulated shape as a Polyhedron_3 with exact
>     constructions.
>      > The shape is closed and simple and may contain holes.
>      >
>      > What I would like to calculate is most easily described like this
>     (and
>      > takes an input parameter z): if we cut away parts of the shape
>     from Z =
>      > minus infinity to Z = z, what would the shadow (projection) of
>     the shape
>      > look like if we shine a flashlight from above, from Z = plus
>     infinity.
>      >
>      > The result will consist of multiple polygons since the shadow
>     might have
>      > disjoint areas (e.g. candelabra) and holes (e.g. drinking glass).
>      >
>      > Do you have any ideas how to implement this efficiently? Sweep line
>      > algorithms? Ray casting? Thanks!
>      >
>      >       Best regards, Johnny
>      >
>      >
>      >
>      > --
>      > 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>
>      >
>
>     -- 
>     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>
>
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss