# Delaunay v/s Voronoi

16 messages
Open this post in threaded view
|

## Delaunay v/s Voronoi

 Hello,I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other. Fromimplementation point of view, which one has less complexity ?  Almost all the books in Computational Geometry describe both the algorithms but I couldn't find the comparison between two approaches.Can someone clarify ?Chaman Singh VermaPoona, India
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 > > I have one fundamental doubt. Delaunay triangulation and Voronoi > Diagrams are dual to each other. Delaunay and Voronoi are two point of view for the same object > implementation point of view, which one has less complexity ? thus the complexity is exactly the same (since it is the same stuff) -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by MirJafar It all depends on what problem you are solving. For motion planning or obstacle avoidance, I use Delaunay. Regards   Steve ----- Original Message ----- From: [hidden email] Sent: Friday, October 03, 2008 5:49 AM Subject: [cgal-discuss] Delaunay v/s Voronoi Hello,I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other. Fromimplementation point of view, which one has less complexity ?  Almost all the books in ComputationalGeometry describe both the algorithms but I couldn't find the comparison between two approaches.Can someone clarify ?Chaman Singh VermaPoona, India
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by MirJafar > thus the complexity is exactly the same (since it is the same stuff) I think he means "difficulty" in implementing, not actual complexity. In this case, Delaunay seems to be the choice in CGAL, and I see it easier to implement myself. Thanks to the empty circle condition, I would had some idea about how to introduce new points, and re-triangulate; for the Voronoi, the thing seems much more delicate. It is true that many textbooks talk about just everything but often fail to mention ease of implementation and applicability. Best, Daniel -------------------------------------------------------------------------- Mensaje enviado mediante una herramienta Webmail integrada en *El Rincon*: ------------->>>>>>>>     https://rincon.uam.es     <<<<<<<<-------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by MirJafar > thus the complexity is exactly the same (since it is the same stuff) I think he means "difficulty" in implementing, not actual complexity. In this case, Delaunay seems to be the choice in CGAL, and I see it easier to implement myself. Thanks to the empty circle condition, I would had some idea about how to introduce new points, and re-triangulate; for the Voronoi, the thing seems much more delicate. It is true that many textbooks talk about just everything but often fail to mention ease of implementation and applicability. Best, Daniel -------------------------------------------------------------------------- Mensaje enviado mediante una herramienta Webmail integrada en *El Rincon*: ------------->>>>>>>>     https://rincon.uam.es     <<<<<<<<-------------- -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by Daniel Duque Campayo On Friday 03 October 2008 17:21:42 [hidden email] wrote: > > thus the complexity is exactly the same (since it is the same stuff) > > I think he means "difficulty" in implementing, not actual complexity. In > this case, Delaunay seems to be the choice in CGAL, and I see it easier to > implement myself. Thanks to the empty circle condition, I would had some > idea about how to introduce new points, and re-triangulate; for the > Voronoi, the thing seems much more delicate. It is true that many textbooks > talk about just everything but often fail to mention ease of implementation > and applicability. For the euclidean distance, and with points in general position, computing a Voronoi diagram and computing a Delaunay triangulation is exactly the same: same result and same algorithm. The only difference is that for Voronoi you need to compute Voronoi vertices (which are circumcenters). -- Laurent Rineau, PhD Engineer at GeometryFactory http://www.geometryfactory.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Delaunay Triangulation

 In reply to this post by Daniel Duque Campayo Hi, I installed CGAL a few days ago about to use the 3d delaunay function. So I followed the example and create an Delaunay Trinagulation Object: Triangulation T; So I inserted my Points and all works fine. But how can I acces the points and the faces in my Object for manually inserting them to another object? Can someone give me an short example plz? Greets, Dennis -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay Triangulation

 Dennis Endt wrote: > Hi, > > I installed CGAL a few days ago about to use the 3d delaunay function. > > So I followed the example and create an Delaunay Trinagulation Object: > > Triangulation T; > > So I inserted my Points and all works fine. > > But how can I acces the points and the faces in my Object for manually > inserting them to another object? > > Can someone give me an short example plz? > > Greets, > Dennis > > It might help to read the manual. -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay Triangulation

 You need to use iterators. Here is an example from the manual that iterates through vertices. http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Subsection_25.4.2-Ramin On Fri, Oct 3, 2008 at 12:05 PM, Andreas Fabri <[hidden email]> wrote: > Dennis Endt wrote: >> >> Hi, >> >> I installed CGAL a few days ago about to use the 3d delaunay function. >> >> So I followed the example and create an Delaunay Trinagulation Object: >> >> Triangulation T; >> >> So I inserted my Points and all works fine. >> >> But how can I acces the points and the faces in my Object for manually >> inserting them to another object? >> >> Can someone give me an short example plz? >> >> Greets, >> Dennis >> >> > > > It might help to read the manual. > -- > 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
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by Olivier Devillers Hello,So which method is easier to implement ? Voronoi or Delaunay csvOn Fri, Oct 3, 2008 at 6:36 PM, Olivier Devillers wrote: I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other. Delaunay and Voronoi are two point of view for the same object implementation point of view, which one has less complexity ? thus the complexity is exactly the same (since it is the same stuff) -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 Administrator Chaman Singh Verma a écrit : > Hello, > > So which method is easier to implement ? Voronoi or Delaunay Go for Delaunay. -- Sylvain Pion INRIA Sophia-Antipolis Geometrica Project-Team CGAL, http://cgal.org/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by Laurent Rineau (GeometryFactory) On Fri, Oct 3, 2008 at 7:01 PM, Laurent Rineau wrote: On Friday 03 October 2008 17:21:42 [hidden email] wrote: > > thus the complexity is exactly the same (since it is the same stuff) > > I think he means "difficulty" in implementing, not actual complexity. In > this case, Delaunay seems to be the choice in CGAL, and I see it easier to > implement myself. Thanks to the empty circle condition, I would had some > idea about how to introduce new points, and re-triangulate; for the > Voronoi, the thing seems much more delicate. It is true that many textbooks > talk about just everything but often fail to mention ease of implementation > and applicability. For the euclidean distance, and with points in general position, computing a Voronoi diagram and computing a Delaunay triangulation is exactly the same: same result and same algorithm. The only difference is that for Voronoi you need to compute Voronoi vertices (which are circumcenters). -- Laurent Rineau, PhD Engineer at GeometryFactory http://www.geometryfactory.com/ -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss Hello,CGAL documents don't talk about Voronoi Diagrams in 3D.  Does itmeans that they haven't been implemented or the document need upgradation ?Thanks. csv
Open this post in threaded view
|

## Re: Delaunay Triangulation

 In reply to this post by M. Hazegh Hi, I didn`t find any exact information regarding to the needed iterators. I searched the online documentation as well as the demos and examples. So I tried this: for(Triangulation::Point_iterator it = T.points_begin(); it != T.points_end(); it++) { } But what next? How could I access the Points with the coordinates and the facets with the points? Furthermore the Delaunay Triangulation seems to be wrong: The number of vertices are 8. My Object are an Rectangle. After the Delaunay Triangulation I receive 27 edges and 36 facets??? A very high number I think....17 edges seems to be right! Greets Dennis -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss
Open this post in threaded view
|

## Re: Delaunay v/s Voronoi

 In reply to this post by MirJafar Hi, > CGAL documents don't talk about Voronoi Diagrams in 3D.  Does it > means that they haven't been implemented or the document need upgradation ? Discussion on Voronoi diagrams is under triangulation in many cases. See e.g.: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Triangulation_3_ref/Class_Delaunay_triangulation_3.html#Index_anchor_1259Best, Daniel -- Daniel Duque http://rincon.uam.es/dir?cw=950067138671875-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://lists-sop.inria.fr/wws/info/cgal-discuss