Triangulation_3: creating all triangulations reachable by a flip

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

Triangulation_3: creating all triangulations reachable by a flip

Marc Alexa
Dear all,

I am trying to achieve the following: given a Triangulation_3 T, enumerate all triangulations that can be reached from T by a flip. The problem is that T.flip(C) (where C is either an Edge or a Facet) changes T, so that creating other flips starting from T is cumbersome.

Concretely, I am iterating over Edges or Facets. Flipping will invalidate the iterator. But I also cannot use the iterator (which is a Face or Edge of T) on a copy of T.

One way out would be a method for generating a copy of T that also provides a handle to a given Cell in T. But I cannot see any method doing this.

Any help would be appreciated.

Thanks,
Marc

 

--
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: Triangulation_3: creating all triangulations reachable by a flip

Adam Getchell
Hi Marc,

I’m doing something related, which requires large numbers of flips (and other moves) on Delaunay Triangulations.

What I’ve done is written a class which contains a Triangulation_3 as well as other containers of cells, facets, edges, and vertices.

I use the container (i.e. a vector) of edges to determine the edge -> facet flip locations, and the container of facets to determine the facet -> edge flip locations.

I make copies of this class to perform proposed moves; the copy constructors take care of the various containers.

That gives you the triangulation and iterator (but look at Ranges, which are coming in C++20).


I’d been using Boost::optional to provide the semantics that Expected<T,E> is supposed to provide, that is, return a T or an exception E (except that option types return a T if the move succeeds or null if it fails). However, this seems to be not recommended, so I’m probably going to use simple error codes and wait for Zero overhead deterministic failures.



On Dec 10, 2018, at 12:27 AM, Marc Alexa <[hidden email]> wrote:

Dear all,

I am trying to achieve the following: given a Triangulation_3 T, enumerate all triangulations that can be reached from T by a flip. The problem is that T.flip(C) (where C is either an Edge or a Facet) changes T, so that creating other flips starting from T is cumbersome.

Concretely, I am iterating over Edges or Facets. Flipping will invalidate the iterator. But I also cannot use the iterator (which is a Face or Edge of T) on a copy of T.

One way out would be a method for generating a copy of T that also provides a handle to a given Cell in T. But I cannot see any method doing this.

Any help would be appreciated.

Thanks,
Marc



--
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: Triangulation_3: creating all triangulations reachable by a flip

Marc Alexa
Hi Adam,

Thanks a lot for the information and the references. I realized that you probably need to iterate through the lists of elements during the copy. I thought I might as well use CGAL’s Triangulation_3, copy it, and then iterate through the elements to identify the element I want to flip. It seems the copy preserves the order of elements in the iterators, making the identification of an element in the copy trivial. Not elegant, but it works fine. 

Thanks!
-Marc



On 10. Dec 2018, at 20:54, Adam Getchell <[hidden email]> wrote:

Hi Marc,

I’m doing something related, which requires large numbers of flips (and other moves) on Delaunay Triangulations.

What I’ve done is written a class which contains a Triangulation_3 as well as other containers of cells, facets, edges, and vertices.

I use the container (i.e. a vector) of edges to determine the edge -> facet flip locations, and the container of facets to determine the facet -> edge flip locations.

I make copies of this class to perform proposed moves; the copy constructors take care of the various containers.

That gives you the triangulation and iterator (but look at Ranges, which are coming in C++20).


I’d been using Boost::optional to provide the semantics that Expected<T,E> is supposed to provide, that is, return a T or an exception E (except that option types return a T if the move succeeds or null if it fails). However, this seems to be not recommended, so I’m probably going to use simple error codes and wait for Zero overhead deterministic failures.



On Dec 10, 2018, at 12:27 AM, Marc Alexa <[hidden email]> wrote:

Dear all,

I am trying to achieve the following: given a Triangulation_3 T, enumerate all triangulations that can be reached from T by a flip. The problem is that T.flip(C) (where C is either an Edge or a Facet) changes T, so that creating other flips starting from T is cumbersome.

Concretely, I am iterating over Edges or Facets. Flipping will invalidate the iterator. But I also cannot use the iterator (which is a Face or Edge of T) on a copy of T.

One way out would be a method for generating a copy of T that also provides a handle to a given Cell in T. But I cannot see any method doing this.

Any help would be appreciated.

Thanks,
Marc



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