CGAL users discussion list

[Michael Balzer <>]

Hi Andreas,

thank you for your comment. It is good to know that I'm not missing
something essential.

I'm working on so-called "capacity-constrained Voronoi tessellation",
which are weighted Voronoi tessellations with pre-defined region
areas, e.g. 10 sites in a polygon of area 1, where each Voronoi region
has an area of 0.1. The weights of the sites allow to control the
region areas throughout an iterative optimization. I use the resulting
tessellations in different areas of computer graphics and
visualization.

Michael


On Mon, Mar 16, 2009 at 12:10, Andreas Fabri
<>
 wrote:
>
> Hi Michael, Hi Zhan,
>
> It would be best if you explain what you expect. The edges are
> hyperbola arcs, so you are on the right track by looking at
> the hyperbola class.  It is not documented as it is not in
> the CGAL kernel concept.  The endpoints of the hyperbola arcs
> are only given implicitely, that is you can get the sites
> (circles) which are equidistant to the Voronoi vertex.
> For the unbounded Voronoi cells they have linear rays at the
> two "ends" (unless your input consists of only two disks.
>
> Hope this helps,
>
> andreas
>
> ps.: Just out of curiosity: What problem do you want to solve
>     with the Voronoi diagram of disks ?
>
>
>
>
> Michael Balzer wrote:
>>
>> Hi,
>>
>> I'm currently working on the same problem (for the third time):
>> extracting the regions of the Apollonius diagram from the underlying
>> Apollonius graph. I'm either too stupid for it, or it's really tricky
>> with CGAL (probably it's the first of the two alternatives).
>>
>> My first approach some years ago was to use the method
>> draw_dual_edge(Edge e, Stream& str) of Apollonius_graph_2 for which I
>> implemented my own special stream class. It worked, but I had major
>> problem to create the complete polygons for a regions du to the fact
>> that this method just draw the edges with no particular scheme that
>> allows me too know their orientation and order in the resulting
>> polygon.
>>
>> My second approach was to utilize the CGAL classes Hyperbola_2 and its
>> derivatives. They are not in the manual, but used by the Apollonius
>> classes and not hard to understand. With the edge traversal around an
>> Apollonius site and my own hyperbola classes based on Hyperbola_2 I
>> built my polygonal regions. This approach worked much better, but I
>> still had some problems, especially with the infinite regions.
>>
>> I would really appreciate to get a comment from one of the CGAL
>> auhtors on this topic of extracting the polygonal regions of an
>> Apollonius diagram from the underlying Apollonius graph. Is there
>> something I overlook, or another CGAL package that provides a solution
>> to this problem. I as well tried the Voronoi_diagram_2 adaptor class
>> but could not get a sufficient result for others than the normal
>> Delauney graph.
>>
>>
>> Kind regards,
>> Michael
>>
>>
>>
>>
>> On Fri, Mar 13, 2009 at 15:30, Gao Zhan, Jimmy 
>> <>
>>  wrote:
>>>
>>> Hello CGAL friends
>>>
>>>
>>> I want to use the 2D Apollonius Graphs module to obtain the voronoi
>>> diagram
>>> of some disks on a plane. My question is how to get the edge information?
>>> What’s the geometric representation of the edges? I can get the edge
>>> iterator, but after that how do I get the information?
>>>
>>>
>>> Any suggestion or hints are appreciated.
>>>
>>> Best,
>>>
>>> Zhan
>>>
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>