CGAL users discussion list

[Laure Guicherd <>]

Thank you so much, I did not think of this nice solution, it helps a lot :)

Vu, Khuong wrote:
> Laure,
>
> I don't know if CGAL can convert a Voronoi edge into a Ray or not, since an 
> edge may be a quadratic curve, not only a straight line. Anyway, we can solve 
> your problem, based on some following simple observations:
>
> Let P is the set of all points from your input set S.  If S contains 
> segments, P includes the end-points of those.
>
> 1. a ray R (equivalently a infinite edge) MUST be a bisector of 2 points. Let 
> those points be p1 and p2, and L be the line passing p1 and p2. L divides the 
> plane into 2 halves: h1 and h2.
> 2. In case of the order-1 Voronoi diagram (as CGAL provides): all points of P 
> MUST stay in ONE SINGLE half plane divided by L., say h1, not both. It's easy 
> to prove that R must direct h2. From the observation, we can have a simple 
> algorithm:
>
> let p be the intersection of R and L, and s be the source of R. The direction 
> of R is either from s to p, or from p to s.  If s is in h1, then the 
> direction is from s to p. Otherwise, it is from p to s.
>
> Hope it solves your problem.
>
> Best,
> Khuong
> ________________________________________
> From: Laure Guicherd 
> []
> Sent: Monday, April 12, 2010 10:44 AM
> To: 
>
> Subject: Re: [cgal-discuss] Voronoi 2D : convert Halfedge to Segment_2 or 
> Ray_2
>
> Hi Khuong,
>
> You are absolutely right. I have a diagram like this one :
> http://www.olivierlanglois.net/images/voro2.jpg
> which i want to bound with a Rectangle (say, the borders of the image)
>
> I hear your solution, but the problem remains, that even if the source
> or target does not exist (infinite edge), I need the direction of the
> edge to calculate its intersection with a the rectangle. This is why i
> want to convert this edge to Ray_2.
>
> Moreover, if an edge is finite (i.e. if it has a source AND a target),
> sometimes it will intersect this rectange as well. That is why I need to
> convert it to Segment_2.
>
> In the second case, I could create this segment from the source and
> target point and test the intersection, but in the first case (infinite
> edge), I cannot figure how to get this intersection if only have one
> point and no direction, and cannot convert the edge to Ray_2.
>
> I hope i have made myself clear :) Thank you for your help Khuong.
>
> Vu, Khuong wrote:
>   
> > Hi Laure,
> >
> > Let me see if I understand your problem correctly. You have a set of segments 
> > (sites), which possibly intersect with each other. You then construct the 
> > Voronoi diagram, and test if the face of each (possible divided due to 
> > intersections) site is close of open.
> >
> > If so, you can use the function has_target or has_source to check if a 
> > segment if infinite. Hope this helps.
> >
> > Best,
> >
> > Khuong
> > ________________________________________
> > From: Laure Guicherd 
> > []
> > Sent: Monday, April 12, 2010 10:05 AM
> > To: 
> >
> > Subject: [cgal-discuss] Voronoi 2D : convert Halfedge to Segment_2 or Ray_2
> >
> > Hi all,
> > I'm kind of stuck with this issue with Voronoi 2D. I know this topic has
> > been discussed a lot in this mailing, but I could not find a solution in
> > the archives.
> >
> > I am getting a Voronoi diagram from successive sites insertions, then i
> > want to get its faces and vertices. Since i want to bound this diagram
> > with a convex hull, i need to get the intersection of the diagram edges
> > with this hull, and in this purpose i want to convert each halfedge to
> > Segment_2 or Ray_2 in order to test this intersection.
> >
> > Here is my (simplified) code :
> >
> >
> >
> > typedef typename CGAL::Delaunay_triangulation_2<K> DT;
> > typedef typename CGAL::Delaunay_triangulation_adaptation_traits_2<DT> AT;
> > typedef typename
> > CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT> AP;
> > typedef typename CGAL::Voronoi_diagram_2<DT,AT,AP> Voronoi;
> > typedef typename Voronoi::Face_iterator Face_iterator;
> > typedef typename Voronoi::Ccb_halfedge_circulator Ccb_halfedge_circulator;
> > typedef typename AT::Site_2 Site_2;
> >
> >
> > Voronoi VD;
> >
> > // for each point [x,y] :
> > VD.insert( Site_2(x,y) );
> >
> > for ( Face_iterator bf = VD.faces_begin() ; bf != VD.faces_end() ; ++bf )
> > {
> >     Ccb_halfedge_circulator firstEdge = (*bf).outer_ccb();
> >     Ccb_halfedge_circulator he = firstEdge;
> >     do
> >     {
> >         CGAL::Object obj = make_object(he);
> >
> >         Segment_2 segment;
> >         Ray_2 ray;
> >         bool isSegment = ( CGAL::assign( segment, obj ) );
> >         bool isRay = ( CGAL::assign( ray, obj ) );
> >
> >         // test intersection, get points, etc.
> >     }
> >     while ( ++he != firstEdge );
> > }
> >
> >
> > My problem is that isRay and isSegment always return false, even when
> > he->is_ray() or he->is_segment() are true.
> >
> > What did i do wrong ? How can i make this conversion ?
> > Any hint will be greatly appreciated, thank you !
> >
> > Laure
> >
> > --
> > 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
>
>
>