CGAL users discussion list

["Vu, Khuong" <>]

Hi Shusen,



Please see me answer below. Generally speaking, the dual of a Voronoi diagram 
is the Delaunay, and vice versa. Please email me if you want the specific 
code to convert.
________________________________________
From: shusen liu 
[]
Sent: Wednesday, April 21, 2010 3:17 PM
To: 

Subject: [cgal-discuss] Question about method of dealing with the unbounded 
half-edge in  Voronoi_diagram_2

Hi everyone,

I've been search on the solution for this problem for a while. Seems
it has been asked several times on this mailing list. But I still
didn't find a working solution.

The problem we have is, when using the Voronoi_diagram_2 adapter to
calculate voronoi diagram within a certain region(a quad for example),
in order to get the correct face we need to clip the unbounded face
with the boundary of this region.

it has been discussed in several thread:
One solution is in here :
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2007-06/msg00229.html
but it require you to use dual of Delaunay_triangulation_2 in stead of
voronoi_diagram_2

Since you can't(or I don't know how) convert unbounded half-edge into
Ray_2, the reasonable solution would be calculate the direction by
yourself using the sites position. But this also turn out to be
difficult to do.



-> please see 
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2010-04/msg00127.html for 
the solution.


There are two possible way to access the two sites related to the
edge. One is using left() and right() method for half-edge
structure.But when I test this method, right and left didn't return
the defining site along the edge (the vertex returned seems like the
geometrical on the "left" or "right" of the edge, not the sites define
the edge)

-> please see the third example for the details. 
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html#Section_26.5

I'm sure it works.

The other one is call the half-edge's dual method, this is what
confuse me alot. I have no idea what the returned "Delaunay_edge" is.
There is no document tell you what the structure is.

typedef Delaunay_graph::Edge    Delaunay_edge;  // I don't know where
Delaunay_graph is come from....

When you goto the its
documets:http://www.cgal.org/Manual/last/doc_html/cgal_manual/Voronoi_diagram_2_ref/Concept_DelaunayGraph_2.html#Cross_link_anchor_1403

It seems to have a structure like this, but the Face_handle to
Triangulation_ds_face_base_2 and a int index CAN ONLY decide ONE
vertex, HOW COULD I GET THE OTHER ONE?

typedef std::pair<Face_handle,int>  Edge;

I use /// c_halfedge->dual().first->vertex(c_halfedge->dual().second)->point()
 to get the point

Could anyone give me some hint on how to get the points data from the
Delaunay_graph::Edge ?

-> there is no way to compute the vertex coordinate from the Delaunay graph. 
You have to either convert the Delaunay into Voronoi then retrive the data. 
This works perfectly for Voronoi/Delaunay graph of points. However, there is 
a bug in diagram of segments. Please email me if you need anything else.



Best Regards,
Shusen

PhD student at University of Utah

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