CGAL users discussion list

[Monique Teillaud <>]

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 <> 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 <> 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 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