Deleting faces to create a hole in a triangulation

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Deleting faces to create a hole in a triangulation

malcolm
Hi,
I am using the Constrained Delaunay triangulation and I need to create a
hole in a triangulation using a clipping rectangle. For this, I first add
the cliprect points to the triangulation and then find all the faces that
have a vertex within the clipping polygon. I then call delete_face on each
of these faces.

Here's my code:

        std::vector<Face_handle> facesToDelete;
        for (auto& fItr = tDelaunay.all_faces_begin();
                fItr != tDelaunay.all_faces_end();
                fItr++)
        {
                for (int i = 0; i < 3; i++)
                {
                        auto& pt = fItr->vertex(i)->point();
                       
                        // holePolygon is the closed point polygon with methods to find if a
point lies on or inside the polygon
                        if (holePolygon.isPointInside(pt) && !holePolygon.isPointOn(pt)) // if
face vertex is in the interior of the hole polygon
                        {
                                facesToDelete.push_back(fItr);
                                break;
                        }
                }
        }

        for (auto& face : facesToDelete)
        {
                tDelaunay.delete_face(face);
        }


This works fine and I get the required hole. However, if I now add a vertex
to this triangulation, I get a crash.

I have tried using the make_hole() method too, and even with this, I run
into problems. Is there another way to create a hole in a CDT?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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


Reply | Threaded
Open this post in threaded view
|

Re: Deleting faces to create a hole in a triangulation

Olivier Devillers-2
The manual says:


Advanced Modifiers

The following modifiers are required for convenience of the advanced user.

They do not guarantee the combinatorial validity of the resulting triangulation data structure. 



Calling the function delete_face, you are cleaning the memory, but neighbouring faces still refer to the face you remove ==> bug

A triangulation cannot contain holes since it is a "data structure to store a two-dimensional triangulation that has the topology of a two-dimensional sphere."
(From the abstract of TDS2 manual)
So what you can do is to add a boolean in your faces to mark the faces as inside or outside.

Olivier

Reply | Threaded
Open this post in threaded view
|

Re: Deleting faces to create a hole in a triangulation

andreas.fabri
In reply to this post by malcolm
You should only mark instead of deleting.

> On 17 Sep 2019, at 12:22, malcolm <[hidden email]> wrote:
>
> Hi,
> I am using the Constrained Delaunay triangulation and I need to create a
> hole in a triangulation using a clipping rectangle. For this, I first add
> the cliprect points to the triangulation and then find all the faces that
> have a vertex within the clipping polygon. I then call delete_face on each
> of these faces.
>
> Here's my code:
>
>    std::vector<Face_handle> facesToDelete;
>    for (auto& fItr = tDelaunay.all_faces_begin();
>        fItr != tDelaunay.all_faces_end();
>        fItr++)
>    {
>        for (int i = 0; i < 3; i++)
>        {
>            auto& pt = fItr->vertex(i)->point();
>            
>            // holePolygon is the closed point polygon with methods to find if a
> point lies on or inside the polygon
>            if (holePolygon.isPointInside(pt) && !holePolygon.isPointOn(pt)) // if
> face vertex is in the interior of the hole polygon
>            {
>                facesToDelete.push_back(fItr);
>                break;
>            }
>        }
>    }
>
>    for (auto& face : facesToDelete)
>    {
>        tDelaunay.delete_face(face);
>    }
>
>
> This works fine and I get the required hole. However, if I now add a vertex
> to this triangulation, I get a crash.
>
> I have tried using the make_hole() method too, and even with this, I run
> into problems. Is there another way to create a hole in a CDT?
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.nabble.com/
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> 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


Reply | Threaded
Open this post in threaded view
|

Re: Deleting faces to create a hole in a triangulation

malcolm
In reply to this post by Olivier Devillers-2
Thanks, Olivier.
Do you mean I should add some custom info to the face with a boolean flag?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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


Reply | Threaded
Open this post in threaded view
|

Re: Deleting faces to create a hole in a triangulation

malcolm
Also, I see there's a Triangulation_face_base_with_info_2 class for adding
face info. Is there a class for adding custom info to a constrained
triangulation face?



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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