Iteration over Voronoi faces

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

Iteration over Voronoi faces

Stefan Witzel
Hello,

I do not have any previous experience with cgal and my question is a
rather conceptual one without much technical insight: I would like to
iterate over the faces of a Voronoi diagram and then over the edges of
each face (to obtain a closed polygon); in other words this means to
iterate over the vertices of a Delaunay triangulation and then over
the edges incident with this vertex. Am I right to assume that this is
fundamentally problematic with the default parameters for
Delaunay_triangulation_2 (Triangulation_vertex_base_2,
Triangulation_face_base_2) as a vertex does not ``know'' the edges it
is incident with? Is there a kind of dual assignment that I could use
(like ``(Tessellation_face_base, Tessellation_vertex_base)'')?

Since tessellations into non-triangles may be more complicated, would
it be a possibility to first produce the (common) barycentric
subdivision?

Best,
Stefan

--
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: Iteration over Voronoi faces

Stefan Witzel
Hi,

Sorry about my last question! In case someone is actually wondering:
the answer are face circulators [1]. The documentation would be much
more accessible if one could see all the inherited methods somewhere.
I was looking at the documentation for
Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
down to Triangulation_2, especially when you are wondering about the
traits and data structures along the way.

Best,
Stefan

[1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96

Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:

>
> Hello,
>
> I do not have any previous experience with cgal and my question is a
> rather conceptual one without much technical insight: I would like to
> iterate over the faces of a Voronoi diagram and then over the edges of
> each face (to obtain a closed polygon); in other words this means to
> iterate over the vertices of a Delaunay triangulation and then over
> the edges incident with this vertex. Am I right to assume that this is
> fundamentally problematic with the default parameters for
> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
> is incident with? Is there a kind of dual assignment that I could use
> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
>
> Since tessellations into non-triangles may be more complicated, would
> it be a possibility to first produce the (common) barycentric
> subdivision?
>
> Best,
> Stefan

--
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: Iteration over Voronoi faces

MaelRL
Hello,

This is usually the case, if you look at the documentation page of e.g.
Regular_triangulation_2, you'll see a section "Additional Inherited
Members", which contains exactly what you have in mind (typedefs and
functions from Triangulation_2).

Hyperbolic_Delaunay_triangulation_2 (HDT2) is a little bit different
because it inherits Delaunay_triangulation_2 (DT2), but in a private
way. This is done exactly so that not everything from DT2 is shown in
the documentation. This is because the simplicies in a HDT2 form only a
subset of the simplices of a DT2. Thus, we are internally building a DT2
and the class HDT2 is just a filter on top of the DT2.

You can use the functions from DT2 (or even T2, which DT2 inherits), but
be careful that you will then be working with the full DT2 structure and
not the HDT2. You can apply hyperbolic filtering manually via the
"is_hyperbolic()" family of functions to bring things back to HDT2.

Best,
Mael

On 13/06/2019 22:15, Stefan Witzel wrote:

> Hi,
>
> Sorry about my last question! In case someone is actually wondering:
> the answer are face circulators [1]. The documentation would be much
> more accessible if one could see all the inherited methods somewhere.
> I was looking at the documentation for
> Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
> down to Triangulation_2, especially when you are wondering about the
> traits and data structures along the way.
>
> Best,
> Stefan
>
> [1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96
>
> Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:
>> Hello,
>>
>> I do not have any previous experience with cgal and my question is a
>> rather conceptual one without much technical insight: I would like to
>> iterate over the faces of a Voronoi diagram and then over the edges of
>> each face (to obtain a closed polygon); in other words this means to
>> iterate over the vertices of a Delaunay triangulation and then over
>> the edges incident with this vertex. Am I right to assume that this is
>> fundamentally problematic with the default parameters for
>> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
>> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
>> is incident with? Is there a kind of dual assignment that I could use
>> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
>>
>> Since tessellations into non-triangles may be more complicated, would
>> it be a possibility to first produce the (common) barycentric
>> subdivision?
>>
>> Best,
>> Stefan

--
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: Iteration over Voronoi faces

Stefan Witzel
Dear Mael,

Thank you for this nice explanation! I have in fact run into issues
with non-hyperbolic faces which I had understood mathematically and
thanks to you now understand also on the software level.

Best,
Stefan

Am Fr., 14. Juni 2019 um 08:12 Uhr schrieb Mael
<[hidden email]>:

>
> Hello,
>
> This is usually the case, if you look at the documentation page of e.g.
> Regular_triangulation_2, you'll see a section "Additional Inherited
> Members", which contains exactly what you have in mind (typedefs and
> functions from Triangulation_2).
>
> Hyperbolic_Delaunay_triangulation_2 (HDT2) is a little bit different
> because it inherits Delaunay_triangulation_2 (DT2), but in a private
> way. This is done exactly so that not everything from DT2 is shown in
> the documentation. This is because the simplicies in a HDT2 form only a
> subset of the simplices of a DT2. Thus, we are internally building a DT2
> and the class HDT2 is just a filter on top of the DT2.
>
> You can use the functions from DT2 (or even T2, which DT2 inherits), but
> be careful that you will then be working with the full DT2 structure and
> not the HDT2. You can apply hyperbolic filtering manually via the
> "is_hyperbolic()" family of functions to bring things back to HDT2.
>
> Best,
> Mael
>
> On 13/06/2019 22:15, Stefan Witzel wrote:
> > Hi,
> >
> > Sorry about my last question! In case someone is actually wondering:
> > the answer are face circulators [1]. The documentation would be much
> > more accessible if one could see all the inherited methods somewhere.
> > I was looking at the documentation for
> > Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
> > down to Triangulation_2, especially when you are wondering about the
> > traits and data structures along the way.
> >
> > Best,
> > Stefan
> >
> > [1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96
> >
> > Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:
> >> Hello,
> >>
> >> I do not have any previous experience with cgal and my question is a
> >> rather conceptual one without much technical insight: I would like to
> >> iterate over the faces of a Voronoi diagram and then over the edges of
> >> each face (to obtain a closed polygon); in other words this means to
> >> iterate over the vertices of a Delaunay triangulation and then over
> >> the edges incident with this vertex. Am I right to assume that this is
> >> fundamentally problematic with the default parameters for
> >> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
> >> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
> >> is incident with? Is there a kind of dual assignment that I could use
> >> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
> >>
> >> Since tessellations into non-triangles may be more complicated, would
> >> it be a possibility to first produce the (common) barycentric
> >> subdivision?
> >>
> >> Best,
> >> Stefan
>
> --
> 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: Iteration over Voronoi faces

Stefan Witzel
Hello again,

I have the following piece of code where dt is a hyperbolic Delaunay
triangulation, and vt is a vertex handle.

  ecr = vt->incident_edges();
 do
  {
    if (!dt.is_Delaunay_hyperbolic(*ecr)) {
      break;
    }
    process(dt.dual(*ecr));
  } while (++ecr != vt->incident_edges());

Now I would like that the ecr->target() in one iteration is
ecr->source() of the next iteration (I'm sweeping casting of ecr to a
Euclidean_segment_2 respectively Circular_arc_2 under the rug). Now my
problem is that not only is this not the case but neither does there
seem to be any kind of pattern. So my question is: is there any way to
predict the orientation of the dual segment of a (hyperbolic) Delaunay
triangulation? Thanks in advance!

Best,
Stefan

Am Fr., 14. Juni 2019 um 11:20 Uhr schrieb Stefan Witzel <[hidden email]>:

>
> Dear Mael,
>
> Thank you for this nice explanation! I have in fact run into issues
> with non-hyperbolic faces which I had understood mathematically and
> thanks to you now understand also on the software level.
>
> Best,
> Stefan
>
> Am Fr., 14. Juni 2019 um 08:12 Uhr schrieb Mael
> <[hidden email]>:
> >
> > Hello,
> >
> > This is usually the case, if you look at the documentation page of e.g.
> > Regular_triangulation_2, you'll see a section "Additional Inherited
> > Members", which contains exactly what you have in mind (typedefs and
> > functions from Triangulation_2).
> >
> > Hyperbolic_Delaunay_triangulation_2 (HDT2) is a little bit different
> > because it inherits Delaunay_triangulation_2 (DT2), but in a private
> > way. This is done exactly so that not everything from DT2 is shown in
> > the documentation. This is because the simplicies in a HDT2 form only a
> > subset of the simplices of a DT2. Thus, we are internally building a DT2
> > and the class HDT2 is just a filter on top of the DT2.
> >
> > You can use the functions from DT2 (or even T2, which DT2 inherits), but
> > be careful that you will then be working with the full DT2 structure and
> > not the HDT2. You can apply hyperbolic filtering manually via the
> > "is_hyperbolic()" family of functions to bring things back to HDT2.
> >
> > Best,
> > Mael
> >
> > On 13/06/2019 22:15, Stefan Witzel wrote:
> > > Hi,
> > >
> > > Sorry about my last question! In case someone is actually wondering:
> > > the answer are face circulators [1]. The documentation would be much
> > > more accessible if one could see all the inherited methods somewhere.
> > > I was looking at the documentation for
> > > Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
> > > down to Triangulation_2, especially when you are wondering about the
> > > traits and data structures along the way.
> > >
> > > Best,
> > > Stefan
> > >
> > > [1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96
> > >
> > > Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:
> > >> Hello,
> > >>
> > >> I do not have any previous experience with cgal and my question is a
> > >> rather conceptual one without much technical insight: I would like to
> > >> iterate over the faces of a Voronoi diagram and then over the edges of
> > >> each face (to obtain a closed polygon); in other words this means to
> > >> iterate over the vertices of a Delaunay triangulation and then over
> > >> the edges incident with this vertex. Am I right to assume that this is
> > >> fundamentally problematic with the default parameters for
> > >> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
> > >> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
> > >> is incident with? Is there a kind of dual assignment that I could use
> > >> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
> > >>
> > >> Since tessellations into non-triangles may be more complicated, would
> > >> it be a possibility to first produce the (common) barycentric
> > >> subdivision?
> > >>
> > >> Best,
> > >> Stefan
> >
> > --
> > 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: Iteration over Voronoi faces

Stefan Witzel
Hi again,

If I understand correctly in lines 135-136 of

Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h

the orientation of hyperbolic segments is chosen so that circular arcs
are always (counter-?)clockwise, discarding potential combinatorial
information. That is, a hyperbolic segment from p to q may end up
going from q to p. Is this correct and is there a good reason for it?

Best,
Stefan

Am Fr., 14. Juni 2019 um 14:13 Uhr schrieb Stefan Witzel <[hidden email]>:

>
> Hello again,
>
> I have the following piece of code where dt is a hyperbolic Delaunay
> triangulation, and vt is a vertex handle.
>
>   ecr = vt->incident_edges();
>  do
>   {
>     if (!dt.is_Delaunay_hyperbolic(*ecr)) {
>       break;
>     }
>     process(dt.dual(*ecr));
>   } while (++ecr != vt->incident_edges());
>
> Now I would like that the ecr->target() in one iteration is
> ecr->source() of the next iteration (I'm sweeping casting of ecr to a
> Euclidean_segment_2 respectively Circular_arc_2 under the rug). Now my
> problem is that not only is this not the case but neither does there
> seem to be any kind of pattern. So my question is: is there any way to
> predict the orientation of the dual segment of a (hyperbolic) Delaunay
> triangulation? Thanks in advance!
>
> Best,
> Stefan
>
> Am Fr., 14. Juni 2019 um 11:20 Uhr schrieb Stefan Witzel <[hidden email]>:
> >
> > Dear Mael,
> >
> > Thank you for this nice explanation! I have in fact run into issues
> > with non-hyperbolic faces which I had understood mathematically and
> > thanks to you now understand also on the software level.
> >
> > Best,
> > Stefan
> >
> > Am Fr., 14. Juni 2019 um 08:12 Uhr schrieb Mael
> > <[hidden email]>:
> > >
> > > Hello,
> > >
> > > This is usually the case, if you look at the documentation page of e.g.
> > > Regular_triangulation_2, you'll see a section "Additional Inherited
> > > Members", which contains exactly what you have in mind (typedefs and
> > > functions from Triangulation_2).
> > >
> > > Hyperbolic_Delaunay_triangulation_2 (HDT2) is a little bit different
> > > because it inherits Delaunay_triangulation_2 (DT2), but in a private
> > > way. This is done exactly so that not everything from DT2 is shown in
> > > the documentation. This is because the simplicies in a HDT2 form only a
> > > subset of the simplices of a DT2. Thus, we are internally building a DT2
> > > and the class HDT2 is just a filter on top of the DT2.
> > >
> > > You can use the functions from DT2 (or even T2, which DT2 inherits), but
> > > be careful that you will then be working with the full DT2 structure and
> > > not the HDT2. You can apply hyperbolic filtering manually via the
> > > "is_hyperbolic()" family of functions to bring things back to HDT2.
> > >
> > > Best,
> > > Mael
> > >
> > > On 13/06/2019 22:15, Stefan Witzel wrote:
> > > > Hi,
> > > >
> > > > Sorry about my last question! In case someone is actually wondering:
> > > > the answer are face circulators [1]. The documentation would be much
> > > > more accessible if one could see all the inherited methods somewhere.
> > > > I was looking at the documentation for
> > > > Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
> > > > down to Triangulation_2, especially when you are wondering about the
> > > > traits and data structures along the way.
> > > >
> > > > Best,
> > > > Stefan
> > > >
> > > > [1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96
> > > >
> > > > Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:
> > > >> Hello,
> > > >>
> > > >> I do not have any previous experience with cgal and my question is a
> > > >> rather conceptual one without much technical insight: I would like to
> > > >> iterate over the faces of a Voronoi diagram and then over the edges of
> > > >> each face (to obtain a closed polygon); in other words this means to
> > > >> iterate over the vertices of a Delaunay triangulation and then over
> > > >> the edges incident with this vertex. Am I right to assume that this is
> > > >> fundamentally problematic with the default parameters for
> > > >> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
> > > >> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
> > > >> is incident with? Is there a kind of dual assignment that I could use
> > > >> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
> > > >>
> > > >> Since tessellations into non-triangles may be more complicated, would
> > > >> it be a possibility to first produce the (common) barycentric
> > > >> subdivision?
> > > >>
> > > >> Best,
> > > >> Stefan
> > >
> > > --
> > > 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: Iteration over Voronoi faces

MaelRL
Hello,

The edge iterator/circulator around a vertex gives edges around the
target, in a counter clockwise manner.

Although there is not really any notion of halfedges in a triangulation,
the fact that an edge is described by a face and the index of the vertex
opposite to the edge in that face is indeed pretty much the definition
of a halfedge (since the edge can be described in two different
manners). Using this 'halfedge' point of view, the way you circulate
around the vertex will be counter clockwise and such that target(edge,
tr) == v. You only get the edge once.

If you really want to get the opposite halfedge, you can use the
function 'mirror_edge'.

Concerning the forced orientation that you have noticed, I do not know
the reason, I'll ping the authors and come back to you.

Best,
Mael

On 14/06/2019 15:10, Stefan Witzel wrote:

> Hi again,
>
> If I understand correctly in lines 135-136 of
>
> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>
> the orientation of hyperbolic segments is chosen so that circular arcs
> are always (counter-?)clockwise, discarding potential combinatorial
> information. That is, a hyperbolic segment from p to q may end up
> going from q to p. Is this correct and is there a good reason for it?
>
> Best,
> Stefan
>
> Am Fr., 14. Juni 2019 um 14:13 Uhr schrieb Stefan Witzel <[hidden email]>:
>> Hello again,
>>
>> I have the following piece of code where dt is a hyperbolic Delaunay
>> triangulation, and vt is a vertex handle.
>>
>>    ecr = vt->incident_edges();
>>   do
>>    {
>>      if (!dt.is_Delaunay_hyperbolic(*ecr)) {
>>        break;
>>      }
>>      process(dt.dual(*ecr));
>>    } while (++ecr != vt->incident_edges());
>>
>> Now I would like that the ecr->target() in one iteration is
>> ecr->source() of the next iteration (I'm sweeping casting of ecr to a
>> Euclidean_segment_2 respectively Circular_arc_2 under the rug). Now my
>> problem is that not only is this not the case but neither does there
>> seem to be any kind of pattern. So my question is: is there any way to
>> predict the orientation of the dual segment of a (hyperbolic) Delaunay
>> triangulation? Thanks in advance!
>>
>> Best,
>> Stefan
>>
>> Am Fr., 14. Juni 2019 um 11:20 Uhr schrieb Stefan Witzel <[hidden email]>:
>>> Dear Mael,
>>>
>>> Thank you for this nice explanation! I have in fact run into issues
>>> with non-hyperbolic faces which I had understood mathematically and
>>> thanks to you now understand also on the software level.
>>>
>>> Best,
>>> Stefan
>>>
>>> Am Fr., 14. Juni 2019 um 08:12 Uhr schrieb Mael
>>> <[hidden email]>:
>>>> Hello,
>>>>
>>>> This is usually the case, if you look at the documentation page of e.g.
>>>> Regular_triangulation_2, you'll see a section "Additional Inherited
>>>> Members", which contains exactly what you have in mind (typedefs and
>>>> functions from Triangulation_2).
>>>>
>>>> Hyperbolic_Delaunay_triangulation_2 (HDT2) is a little bit different
>>>> because it inherits Delaunay_triangulation_2 (DT2), but in a private
>>>> way. This is done exactly so that not everything from DT2 is shown in
>>>> the documentation. This is because the simplicies in a HDT2 form only a
>>>> subset of the simplices of a DT2. Thus, we are internally building a DT2
>>>> and the class HDT2 is just a filter on top of the DT2.
>>>>
>>>> You can use the functions from DT2 (or even T2, which DT2 inherits), but
>>>> be careful that you will then be working with the full DT2 structure and
>>>> not the HDT2. You can apply hyperbolic filtering manually via the
>>>> "is_hyperbolic()" family of functions to bring things back to HDT2.
>>>>
>>>> Best,
>>>> Mael
>>>>
>>>> On 13/06/2019 22:15, Stefan Witzel wrote:
>>>>> Hi,
>>>>>
>>>>> Sorry about my last question! In case someone is actually wondering:
>>>>> the answer are face circulators [1]. The documentation would be much
>>>>> more accessible if one could see all the inherited methods somewhere.
>>>>> I was looking at the documentation for
>>>>> Hyperbolic_Delaunay_triangulation_2 and from there it's a bit of a way
>>>>> down to Triangulation_2, especially when you are wondering about the
>>>>> traits and data structures along the way.
>>>>>
>>>>> Best,
>>>>> Stefan
>>>>>
>>>>> [1] https://doc.cgal.org/latest/Triangulation_2/classCGAL_1_1Triangulation__2.html#a1bda2ab92ccf638bb22fc223ae281b96
>>>>>
>>>>> Am Do., 13. Juni 2019 um 16:32 Uhr schrieb Stefan Witzel <[hidden email]>:
>>>>>> Hello,
>>>>>>
>>>>>> I do not have any previous experience with cgal and my question is a
>>>>>> rather conceptual one without much technical insight: I would like to
>>>>>> iterate over the faces of a Voronoi diagram and then over the edges of
>>>>>> each face (to obtain a closed polygon); in other words this means to
>>>>>> iterate over the vertices of a Delaunay triangulation and then over
>>>>>> the edges incident with this vertex. Am I right to assume that this is
>>>>>> fundamentally problematic with the default parameters for
>>>>>> Delaunay_triangulation_2 (Triangulation_vertex_base_2,
>>>>>> Triangulation_face_base_2) as a vertex does not ``know'' the edges it
>>>>>> is incident with? Is there a kind of dual assignment that I could use
>>>>>> (like ``(Tessellation_face_base, Tessellation_vertex_base)'')?
>>>>>>
>>>>>> Since tessellations into non-triangles may be more complicated, would
>>>>>> it be a possibility to first produce the (common) barycentric
>>>>>> subdivision?
>>>>>>
>>>>>> Best,
>>>>>> Stefan
>>>> --
>>>> 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: Iteration over Voronoi faces

teillaud
Administrator
In reply to this post by Stefan Witzel
Hi,

I don't remember details but I guess that we have followed the same conventions as the CGAL circular kernel, see
https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2 
The orientation is chosen to be globally consistent.

I have checked the documentation quickly. As far as I can see, neither the traits concept
(https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
nor the two models (note that one of them is based on the abovementioned circular kernel) is explicitly saying anything on the orientation of circular arcs. There is no guarantee that undocumented properties stay the same forever, so, it might be risky to rely on them.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :

> Hi again,
>
> If I understand correctly in lines 135-136 of
>
> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>
> the orientation of hyperbolic segments is chosen so that circular arcs
> are always (counter-?)clockwise, discarding potential combinatorial
> information. That is, a hyperbolic segment from p to q may end up
> going from q to p. Is this correct and is there a good reason for it?
>
> Best,
> Stefan
>

--
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: Iteration over Voronoi faces

Stefan Witzel
Hi,

I realize that the documentation does not guarantee any kind of behavior
but I would like say that it would be very useful if the result of
Construct_hyperbolic_segment_2 *was* guaranteed to be oriented (which
actually amounts to a simplification of code, see below). I have code
that needs this property and without it I would essentially start
reimplementing them just to lift that restriction.

I would also like to point out that, unlike for circular arcs, the
property of running clockwise or counterclockwise is not an intrinsic
property of a hyperbolic segment. So one could apply a Moebius
transformation and the orientation would change.

Generally I agree that the term "segment" doesn't suggest any kind of
orientation, so one might want to call it differently. However, I found
that throwing away the order of the endpoints (even of circular arcs) is
a loss of information that is hard to recover, whereas the property of
running clockwise or counterclockwise can be checked in a single line
(which might be a method).

I don't mean to question your design decisions just humbly report on my
user experience. I'll just work with my patched header for now.

Best,
Stefan

---
a/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
+++
b/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
@@ -132,10 +132,7 @@ public:
      // uncomment!!!
      //assert(circle.has_on_boundary(p) && circle.has_on_boundary(q));

-    if(_gt.orientation_2_object()(p, q, center) == LEFT_TURN)
-      return Circular_arc_2(circle, p, q);
-
-    return Circular_arc_2(circle, q, p);
+    return Circular_arc_2(circle, p, q);
    }


On 17.06.19 15:32, Monique Teillaud wrote:

> Hi,
>
> I don't remember details but I guess that we have followed the same conventions as the CGAL circular kernel, see
> https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
> The orientation is chosen to be globally consistent.
>
> I have checked the documentation quickly. As far as I can see, neither the traits concept
> (https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
> nor the two models (note that one of them is based on the abovementioned circular kernel) is explicitly saying anything on the orientation of circular arcs. There is no guarantee that undocumented properties stay the same forever, so, it might be risky to rely on them.
>
> Best,
> --
> Monique Teillaud
> https://members.loria.fr/Monique.Teillaud/
> INRIA Nancy - Grand Est, LORIA
> Institut National de Recherche en Informatique et Automatique
>
> ----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :
>
>> Hi again,
>>
>> If I understand correctly in lines 135-136 of
>>
>> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>>
>> the orientation of hyperbolic segments is chosen so that circular arcs
>> are always (counter-?)clockwise, discarding potential combinatorial
>> information. That is, a hyperbolic segment from p to q may end up
>> going from q to p. Is this correct and is there a good reason for it?
>>
>> Best,
>> Stefan
>>
>

--
Stefan Witzel
Faculty of Mathematics
Bielefeld University
Universitätsstraße 25
33501 Bielefeld
http://www.math.uni-bielefeld.de/~switzel/

--
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: Iteration over Voronoi faces

MaelRL
Hello,

Just a side-note, the forced orientation is also because it makes it
easier when you want to draw the diagram: as Monique said, we have a
cgal-wide convention on the orientation of these circle arcs and thus if
you have oriented your Voronoi edges in the correct way, you can just
draw it immediately without having to check the orientation (and if the
orientation hadn't been enforced, you would sometimes use the
complementary circle arc).

Best,
Mael

On 17/06/2019 16:54, Stefan Witzel wrote:

> Hi,
>
> I realize that the documentation does not guarantee any kind of
> behavior but I would like say that it would be very useful if the
> result of Construct_hyperbolic_segment_2 *was* guaranteed to be
> oriented (which actually amounts to a simplification of code, see
> below). I have code that needs this property and without it I would
> essentially start reimplementing them just to lift that restriction.
>
> I would also like to point out that, unlike for circular arcs, the
> property of running clockwise or counterclockwise is not an intrinsic
> property of a hyperbolic segment. So one could apply a Moebius
> transformation and the orientation would change.
>
> Generally I agree that the term "segment" doesn't suggest any kind of
> orientation, so one might want to call it differently. However, I
> found that throwing away the order of the endpoints (even of circular
> arcs) is a loss of information that is hard to recover, whereas the
> property of running clockwise or counterclockwise can be checked in a
> single line (which might be a method).
>
> I don't mean to question your design decisions just humbly report on
> my user experience. I'll just work with my patched header for now.
>
> Best,
> Stefan
>
> ---
> a/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> +++
> b/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> @@ -132,10 +132,7 @@ public:
>      // uncomment!!!
>      //assert(circle.has_on_boundary(p) && circle.has_on_boundary(q));
>
> -    if(_gt.orientation_2_object()(p, q, center) == LEFT_TURN)
> -      return Circular_arc_2(circle, p, q);
> -
> -    return Circular_arc_2(circle, q, p);
> +    return Circular_arc_2(circle, p, q);
>    }
>
>
> On 17.06.19 15:32, Monique Teillaud wrote:
>> Hi,
>>
>> I don't remember details but I guess that we have followed the same
>> conventions as the CGAL circular kernel, see
>> https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
>> The orientation is chosen to be globally consistent.
>>
>> I have checked the documentation quickly. As far as I can see,
>> neither the traits concept
>> (https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
>>
>> nor the two models (note that one of them is based on the
>> abovementioned circular kernel) is explicitly saying anything on the
>> orientation of circular arcs. There is no guarantee that undocumented
>> properties stay the same forever, so, it might be risky to rely on them.
>>
>> Best,
>> --
>> Monique Teillaud
>> https://members.loria.fr/Monique.Teillaud/
>> INRIA Nancy - Grand Est, LORIA
>> Institut National de Recherche en Informatique et Automatique
>>
>> ----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :
>>
>>> Hi again,
>>>
>>> If I understand correctly in lines 135-136 of
>>>
>>> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>>>
>>>
>>> the orientation of hyperbolic segments is chosen so that circular arcs
>>> are always (counter-?)clockwise, discarding potential combinatorial
>>> information. That is, a hyperbolic segment from p to q may end up
>>> going from q to p. Is this correct and is there a good reason for it?
>>>
>>> Best,
>>> Stefan
>>>
>>
>

--
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: Iteration over Voronoi faces

Stefan Witzel
Hello,

I understand and I am actually drawing them (or rather exporting them to svg). But as I said whether they are clockwise or counterclockwise is a single flag that I can recover in a single line of code (which of course is just the line I took out of the header).

On the other hand having a sequence of segments [a_i, b_i] and knowing that one of a_i and b_i equals one of a_{i+1} and b_{i+1} up to numerical error and trying to figure out the correct ordering is a bit messy. (Of course I could always carry around the end points as well as the segment but that seems a bit silly.)

I don't know whether I mentioned it but the point of the exercise is to make the Voronoi cells be closed polygons rather than just a bunch of paths, so they can be filled. So at some point they absolutely need to get oriented in a circular fashion around the polygon and since they start off being constructed that way I'd rather not throw away that information only to later recover it in a costly and complicated way.

So if a suggestion is allowed, you could have some notion of an oriented segment (arc, etc) that carries combinatorial orientation besides your established notion of a segment (arc etc). There could then be a method that turns the oriented thing into the unoriented one by flipping arcs counterclockwise and tossing a coin for segments. (And that method would be very fundamental and never need to be overloaded.)

Best,
Stefan

Mael <[hidden email]> schrieb am Di., 18. Juni 2019, 08:04:
Hello,

Just a side-note, the forced orientation is also because it makes it
easier when you want to draw the diagram: as Monique said, we have a
cgal-wide convention on the orientation of these circle arcs and thus if
you have oriented your Voronoi edges in the correct way, you can just
draw it immediately without having to check the orientation (and if the
orientation hadn't been enforced, you would sometimes use the
complementary circle arc).

Best,
Mael

On 17/06/2019 16:54, Stefan Witzel wrote:
> Hi,
>
> I realize that the documentation does not guarantee any kind of
> behavior but I would like say that it would be very useful if the
> result of Construct_hyperbolic_segment_2 *was* guaranteed to be
> oriented (which actually amounts to a simplification of code, see
> below). I have code that needs this property and without it I would
> essentially start reimplementing them just to lift that restriction.
>
> I would also like to point out that, unlike for circular arcs, the
> property of running clockwise or counterclockwise is not an intrinsic
> property of a hyperbolic segment. So one could apply a Moebius
> transformation and the orientation would change.
>
> Generally I agree that the term "segment" doesn't suggest any kind of
> orientation, so one might want to call it differently. However, I
> found that throwing away the order of the endpoints (even of circular
> arcs) is a loss of information that is hard to recover, whereas the
> property of running clockwise or counterclockwise can be checked in a
> single line (which might be a method).
>
> I don't mean to question your design decisions just humbly report on
> my user experience. I'll just work with my patched header for now.
>
> Best,
> Stefan
>
> ---
> a/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> +++
> b/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> @@ -132,10 +132,7 @@ public:
>      // uncomment!!!
>      //assert(circle.has_on_boundary(p) && circle.has_on_boundary(q));
>
> -    if(_gt.orientation_2_object()(p, q, center) == LEFT_TURN)
> -      return Circular_arc_2(circle, p, q);
> -
> -    return Circular_arc_2(circle, q, p);
> +    return Circular_arc_2(circle, p, q);
>    }
>
>
> On 17.06.19 15:32, Monique Teillaud wrote:
>> Hi,
>>
>> I don't remember details but I guess that we have followed the same
>> conventions as the CGAL circular kernel, see
>> https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
>> The orientation is chosen to be globally consistent.
>>
>> I have checked the documentation quickly. As far as I can see,
>> neither the traits concept
>> (https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
>>
>> nor the two models (note that one of them is based on the
>> abovementioned circular kernel) is explicitly saying anything on the
>> orientation of circular arcs. There is no guarantee that undocumented
>> properties stay the same forever, so, it might be risky to rely on them.
>>
>> Best,
>> --
>> Monique Teillaud
>> https://members.loria.fr/Monique.Teillaud/
>> INRIA Nancy - Grand Est, LORIA
>> Institut National de Recherche en Informatique et Automatique
>>
>> ----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :
>>
>>> Hi again,
>>>
>>> If I understand correctly in lines 135-136 of
>>>
>>> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>>>
>>>
>>> the orientation of hyperbolic segments is chosen so that circular arcs
>>> are always (counter-?)clockwise, discarding potential combinatorial
>>> information. That is, a hyperbolic segment from p to q may end up
>>> going from q to p. Is this correct and is there a good reason for it?
>>>
>>> Best,
>>> Stefan
>>>
>>
>

--
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: Iteration over Voronoi faces

teillaud
Administrator
Hi

We are not mixing combinatorics and geometry.
You can iterate over the edges of a 2d Voronoi cell by using the circulator over the Delaunay edges incident to the Delaunay vertex and taking their dual. This combinatorial infirmation gives you the edges in order.
And you can draw them using the geometry of the dual segments.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

----- Le 18 Juin 19, à 3:31, Stefan Witzel <[hidden email]> a écrit :
Hello,

I understand and I am actually drawing them (or rather exporting them to svg). But as I said whether they are clockwise or counterclockwise is a single flag that I can recover in a single line of code (which of course is just the line I took out of the header).

On the other hand having a sequence of segments [a_i, b_i] and knowing that one of a_i and b_i equals one of a_{i+1} and b_{i+1} up to numerical error and trying to figure out the correct ordering is a bit messy. (Of course I could always carry around the end points as well as the segment but that seems a bit silly.)

I don't know whether I mentioned it but the point of the exercise is to make the Voronoi cells be closed polygons rather than just a bunch of paths, so they can be filled. So at some point they absolutely need to get oriented in a circular fashion around the polygon and since they start off being constructed that way I'd rather not throw away that information only to later recover it in a costly and complicated way.

So if a suggestion is allowed, you could have some notion of an oriented segment (arc, etc) that carries combinatorial orientation besides your established notion of a segment (arc etc). There could then be a method that turns the oriented thing into the unoriented one by flipping arcs counterclockwise and tossing a coin for segments. (And that method would be very fundamental and never need to be overloaded.)

Best,
Stefan

Mael <[hidden email]> schrieb am Di., 18. Juni 2019, 08:04:
Hello,

Just a side-note, the forced orientation is also because it makes it
easier when you want to draw the diagram: as Monique said, we have a
cgal-wide convention on the orientation of these circle arcs and thus if
you have oriented your Voronoi edges in the correct way, you can just
draw it immediately without having to check the orientation (and if the
orientation hadn't been enforced, you would sometimes use the
complementary circle arc).

Best,
Mael

On 17/06/2019 16:54, Stefan Witzel wrote:
> Hi,
>
> I realize that the documentation does not guarantee any kind of
> behavior but I would like say that it would be very useful if the
> result of Construct_hyperbolic_segment_2 *was* guaranteed to be
> oriented (which actually amounts to a simplification of code, see
> below). I have code that needs this property and without it I would
> essentially start reimplementing them just to lift that restriction.
>
> I would also like to point out that, unlike for circular arcs, the
> property of running clockwise or counterclockwise is not an intrinsic
> property of a hyperbolic segment. So one could apply a Moebius
> transformation and the orientation would change.
>
> Generally I agree that the term "segment" doesn't suggest any kind of
> orientation, so one might want to call it differently. However, I
> found that throwing away the order of the endpoints (even of circular
> arcs) is a loss of information that is hard to recover, whereas the
> property of running clockwise or counterclockwise can be checked in a
> single line (which might be a method).
>
> I don't mean to question your design decisions just humbly report on
> my user experience. I'll just work with my patched header for now.
>
> Best,
> Stefan
>
> ---
> a/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> +++
> b/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> @@ -132,10 +132,7 @@ public:
>      // uncomment!!!
>      //assert(circle.has_on_boundary(p) && circle.has_on_boundary(q));
>
> -    if(_gt.orientation_2_object()(p, q, center) == LEFT_TURN)
> -      return Circular_arc_2(circle, p, q);
> -
> -    return Circular_arc_2(circle, q, p);
> +    return Circular_arc_2(circle, p, q);
>    }
>
>
> On 17.06.19 15:32, Monique Teillaud wrote:
>> Hi,
>>
>> I don't remember details but I guess that we have followed the same
>> conventions as the CGAL circular kernel, see
>> https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
>> The orientation is chosen to be globally consistent.
>>
>> I have checked the documentation quickly. As far as I can see,
>> neither the traits concept
>> (https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
>>
>> nor the two models (note that one of them is based on the
>> abovementioned circular kernel) is explicitly saying anything on the
>> orientation of circular arcs. There is no guarantee that undocumented
>> properties stay the same forever, so, it might be risky to rely on them.
>>
>> Best,
>> --
>> Monique Teillaud
>> https://members.loria.fr/Monique.Teillaud/
>> INRIA Nancy - Grand Est, LORIA
>> Institut National de Recherche en Informatique et Automatique
>>
>> ----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :
>>
>>> Hi again,
>>>
>>> If I understand correctly in lines 135-136 of
>>>
>>> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>>>
>>>
>>> the orientation of hyperbolic segments is chosen so that circular arcs
>>> are always (counter-?)clockwise, discarding potential combinatorial
>>> information. That is, a hyperbolic segment from p to q may end up
>>> going from q to p. Is this correct and is there a good reason for it?
>>>
>>> Best,
>>> Stefan
>>>
>>
>

--
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: Iteration over Voronoi faces

Stefan Witzel
Hi,

Yes of course, that was the starting point of the discussion. But I cannot (easily) turn them into a closed path because the endpoints of the dual segments don't match up.

Anyway, you have a consistent system that you are happy with and I have a solution that works for me. So never mind.

Best,
Stefan


Monique Teillaud <[hidden email]> schrieb am Di., 18. Juni 2019, 17:48:
Hi

We are not mixing combinatorics and geometry.
You can iterate over the edges of a 2d Voronoi cell by using the circulator over the Delaunay edges incident to the Delaunay vertex and taking their dual. This combinatorial infirmation gives you the edges in order.
And you can draw them using the geometry of the dual segments.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

----- Le 18 Juin 19, à 3:31, Stefan Witzel <[hidden email]> a écrit :
Hello,

I understand and I am actually drawing them (or rather exporting them to svg). But as I said whether they are clockwise or counterclockwise is a single flag that I can recover in a single line of code (which of course is just the line I took out of the header).

On the other hand having a sequence of segments [a_i, b_i] and knowing that one of a_i and b_i equals one of a_{i+1} and b_{i+1} up to numerical error and trying to figure out the correct ordering is a bit messy. (Of course I could always carry around the end points as well as the segment but that seems a bit silly.)

I don't know whether I mentioned it but the point of the exercise is to make the Voronoi cells be closed polygons rather than just a bunch of paths, so they can be filled. So at some point they absolutely need to get oriented in a circular fashion around the polygon and since they start off being constructed that way I'd rather not throw away that information only to later recover it in a costly and complicated way.

So if a suggestion is allowed, you could have some notion of an oriented segment (arc, etc) that carries combinatorial orientation besides your established notion of a segment (arc etc). There could then be a method that turns the oriented thing into the unoriented one by flipping arcs counterclockwise and tossing a coin for segments. (And that method would be very fundamental and never need to be overloaded.)

Best,
Stefan

Mael <[hidden email]> schrieb am Di., 18. Juni 2019, 08:04:
Hello,

Just a side-note, the forced orientation is also because it makes it
easier when you want to draw the diagram: as Monique said, we have a
cgal-wide convention on the orientation of these circle arcs and thus if
you have oriented your Voronoi edges in the correct way, you can just
draw it immediately without having to check the orientation (and if the
orientation hadn't been enforced, you would sometimes use the
complementary circle arc).

Best,
Mael

On 17/06/2019 16:54, Stefan Witzel wrote:
> Hi,
>
> I realize that the documentation does not guarantee any kind of
> behavior but I would like say that it would be very useful if the
> result of Construct_hyperbolic_segment_2 *was* guaranteed to be
> oriented (which actually amounts to a simplification of code, see
> below). I have code that needs this property and without it I would
> essentially start reimplementing them just to lift that restriction.
>
> I would also like to point out that, unlike for circular arcs, the
> property of running clockwise or counterclockwise is not an intrinsic
> property of a hyperbolic segment. So one could apply a Moebius
> transformation and the orientation would change.
>
> Generally I agree that the term "segment" doesn't suggest any kind of
> orientation, so one might want to call it differently. However, I
> found that throwing away the order of the endpoints (even of circular
> arcs) is a loss of information that is hard to recover, whereas the
> property of running clockwise or counterclockwise can be checked in a
> single line (which might be a method).
>
> I don't mean to question your design decisions just humbly report on
> my user experience. I'll just work with my patched header for now.
>
> Best,
> Stefan
>
> ---
> a/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> +++
> b/Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
> @@ -132,10 +132,7 @@ public:
>      // uncomment!!!
>      //assert(circle.has_on_boundary(p) && circle.has_on_boundary(q));
>
> -    if(_gt.orientation_2_object()(p, q, center) == LEFT_TURN)
> -      return Circular_arc_2(circle, p, q);
> -
> -    return Circular_arc_2(circle, q, p);
> +    return Circular_arc_2(circle, p, q);
>    }
>
>
> On 17.06.19 15:32, Monique Teillaud wrote:
>> Hi,
>>
>> I don't remember details but I guess that we have followed the same
>> conventions as the CGAL circular kernel, see
>> https://doc.cgal.org/latest/Manual/packages.html#PkgCircularKernel2
>> The orientation is chosen to be globally consistent.
>>
>> I have checked the documentation quickly. As far as I can see,
>> neither the traits concept
>> (https://doc.cgal.org/latest/Hyperbolic_triangulation_2/classHyperbolicDelaunayTriangulationTraits__2.html)
>>
>> nor the two models (note that one of them is based on the
>> abovementioned circular kernel) is explicitly saying anything on the
>> orientation of circular arcs. There is no guarantee that undocumented
>> properties stay the same forever, so, it might be risky to rely on them.
>>
>> Best,
>> --
>> Monique Teillaud
>> https://members.loria.fr/Monique.Teillaud/
>> INRIA Nancy - Grand Est, LORIA
>> Institut National de Recherche en Informatique et Automatique
>>
>> ----- Le 14 Juin 19, à 9:10, Stefan Witzel [hidden email] a écrit :
>>
>>> Hi again,
>>>
>>> If I understand correctly in lines 135-136 of
>>>
>>> Hyperbolic_triangulation_2/include/CGAL/internal/Hyperbolic_Delaunay_triangulation_traits_2_functions.h
>>>
>>>
>>> the orientation of hyperbolic segments is chosen so that circular arcs
>>> are always (counter-?)clockwise, discarding potential combinatorial
>>> information. That is, a hyperbolic segment from p to q may end up
>>> going from q to p. Is this correct and is there a good reason for it?
>>>
>>> Best,
>>> Stefan
>>>
>>
>

--
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: Iteration over Voronoi faces

teillaud
Administrator
----- Le 18 Juin 19, à 12:06, Stefan Witzel <[hidden email]> a écrit :
Hi,

Yes of course, that was the starting point of the discussion. But I cannot (easily) turn them into a closed path because the endpoints of the dual segments don't match up.
Aren't you using the recommended kernels? they make sure that you don't encounter arithmetic issues.
Even if you are using your own rounded arithmetics, then you _know_ by definition that the two Voronoi vertices are the same. For this, it is better to rely on the combinatorics rather than arithmetic constructions.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique
Reply | Threaded
Open this post in threaded view
|

Re: Iteration over Voronoi faces

Stefan Witzel
Am Di., 18. Juni 2019 um 19:54 Uhr schrieb Monique Teillaud
<[hidden email]>:
> ----- Le 18 Juin 19, à 12:06, Stefan Witzel <[hidden email]> a écrit :
> Yes of course, that was the starting point of the discussion. But I cannot (easily) turn them into a closed path because the endpoints of the dual segments don't match up.
>
> Aren't you using the recommended kernels? they make sure that you don't encounter arithmetic issues.
> Even if you are using your own rounded arithmetics, then you _know_ by definition that the two Voronoi vertices are the same. For this, it is better to rely on the combinatorics rather than arithmetic constructions.

When I say "don't match up" I mean target() of one is not source() of
the next (not because of imprecision but because they happen to lie in
a region of the Poincaré disk where the cgal convention stipulates
that the source() of one should be the source() of the next).
What I take from this discussion is that hyperbolic segments are not
useful and are not meant to represent edges of combinatorial polygons.
So to do things in the cgal spirit one should probably represent
polygons by their vertices and only create the hyperbolic segments
when drawing the polygon. In that situation one would then have the
vertices as well as the segments available and could sort out the
right orientation.

Just to make sure: this cgal convention on counterclockwise
orientation of circular arcs is just an internal convention, not
guaranteed behavior, correct? So if I have a hyperbolic segment I
really know nothing about the role of source() and target()?

Perhaps I should say this at least once (and it should probably have
been earlier): it's great that cgal provides the power of computing
hyperbolic Voronoi diagrams in such a robust way! I wouldn't have
started the discussion if your software wasn't so useful.

Best,
Stefan

--
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: Iteration over Voronoi faces

teillaud
Administrator
----- Le 19 Juin 19, à 3:16, Stefan Witzel [hidden email] a écrit :

> Am Di., 18. Juni 2019 um 19:54 Uhr schrieb Monique Teillaud
> <[hidden email]>:
>> ----- Le 18 Juin 19, à 12:06, Stefan Witzel <[hidden email]> a écrit :
>> Yes of course, that was the starting point of the discussion. But I cannot
>> (easily) turn them into a closed path because the endpoints of the dual
>> segments don't match up.
>>
>> Aren't you using the recommended kernels? they make sure that you don't
>> encounter arithmetic issues.
>> Even if you are using your own rounded arithmetics, then you _know_ by
>> definition that the two Voronoi vertices are the same. For this, it is better
>> to rely on the combinatorics rather than arithmetic constructions.
>
> When I say "don't match up" I mean target() of one is not source() of
> the next (not because of imprecision but because they happen to lie in
> a region of the Poincaré disk where the cgal convention stipulates
> that the source() of one should be the source() of the next).
> What I take from this discussion is that hyperbolic segments are not
> useful and are not meant to represent edges of combinatorial polygons.

Hyperbolic segments are only useful to what the manual says. They are standard geometric hyperbolic (non-oriented) segments, not combinatorial objects.

> So to do things in the cgal spirit one should probably represent
> polygons by their vertices and only create the hyperbolic segments
> when drawing the polygon. In that situation one would then have the
> vertices as well as the segments available and could sort out the
> right orientation.

If I understand correctly, this goes along the same lines as what I proposed in my previous email:
* use circulators to get the combinatorial structure (the polygon is left implicit)
* use segments as (non-oriented) geometric objects.

> Just to make sure: this cgal convention on counterclockwise
> orientation of circular arcs is just an internal convention, not
> guaranteed behavior, correct? So if I have a hyperbolic segment I
> really know nothing about the role of source() and target()?

If I am not mistaken, source() and target() are not even mentioned in the manual.

> Perhaps I should say this at least once (and it should probably have
> been earlier): it's great that cgal provides the power of computing
> hyperbolic Voronoi diagrams in such a robust way! I wouldn't have
> started the discussion if your software wasn't so useful.

We are glad that this new package can already be useful to some users!
Thank you for your comments.

Best,
--
Monique Teillaud
https://members.loria.fr/Monique.Teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

--
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: Iteration over Voronoi faces

Stefan Witzel
Am Mi., 19. Juni 2019 um 20:31 Uhr schrieb Monique Teillaud
<[hidden email]>:

> ----- Le 19 Juin 19, à 3:16, Stefan Witzel [hidden email] a écrit :
> > Am Di., 18. Juni 2019 um 19:54 Uhr schrieb Monique Teillaud
> > <[hidden email]>:
> > So to do things in the cgal spirit one should probably represent
> > polygons by their vertices and only create the hyperbolic segments
> > when drawing the polygon. In that situation one would then have the
> > vertices as well as the segments available and could sort out the
> > right orientation.
>
> If I understand correctly, this goes along the same lines as what I proposed in my previous email:
> * use circulators to get the combinatorial structure (the polygon is left implicit)
> * use segments as (non-oriented) geometric objects.

Except that you suggested to iterate over edges and take their duals
which are hyperbolic segments and therefore not combinatorial objects
as you would say. With that approach one does not get the circular
order of the vertices. This was the very first thing I tried and it
took almost a day to figure out why it's not working.

> > Just to make sure: this cgal convention on counterclockwise
> > orientation of circular arcs is just an internal convention, not
> > guaranteed behavior, correct? So if I have a hyperbolic segment I
> > really know nothing about the role of source() and target()?
>
> If I am not mistaken, source() and target() are not even mentioned in the manual.

Yes, well, I still haven't gotten to grips with the manual.

Best,
Stefan

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