Delaunay v/s Voronoi

classic Classic list List threaded Threaded
16 messages Options
Reply | Threaded
Open this post in threaded view
|

Delaunay v/s Voronoi

MirJafar
Hello,

I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other. From
implementation 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 Verma
Poona, India

Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Olivier Devillers

>
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Steve Chan-4
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 -----
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. From
implementation 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 Verma
Poona, India

Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Daniel Duque Campayo
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Daniel Duque Campayo
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Laurent Rineau (GeometryFactory)
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
Reply | Threaded
Open this post in threaded view
|

Delaunay Triangulation

Dennis Endt
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation

andreas.fabri
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation

M. Hazegh
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

MirJafar
In reply to this post by Olivier Devillers
Hello,

So which method is easier to implement ? Voronoi or Delaunay

csv


On Fri, Oct 3, 2008 at 6:36 PM, Olivier Devillers <[hidden email]> 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

Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Sylvain Pion
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

MirJafar
In reply to this post by Laurent Rineau (GeometryFactory)


On Fri, Oct 3, 2008 at 7:01 PM, Laurent Rineau <[hidden email]> 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 it
means that they haven't been implemented or the document need upgradation ?

Thanks.

csv
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay Triangulation

Dennis Endt
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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Daniel Duque Campayo
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_1259

Best,

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
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Monique Teillaud
In reply to this post by MirJafar
Hi ,

Using CGAL::Delaunay_triangulation_{2,3} is even easier than
re-programming Delaunay or Voronoi...

Best
        Monique Teillaud

Chaman Singh Verma wrote:

> Hello,
>
> So which method is easier to implement ? Voronoi or Delaunay
>
> csv
>
>
> On Fri, Oct 3, 2008 at 6:36 PM, Olivier Devillers
> <[hidden email]
> <mailto:[hidden email]>> 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
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Delaunay v/s Voronoi

Monique Teillaud
In reply to this post by Daniel Duque Campayo
Hi,

right.
The graphs are dual, so, when you compute a Delaunay triangulation
(provided by CGAL), you also get the graph of Voronoi.

Moreover, the Delaunay triangulation provides you with dual() functions,
that give you the geometric embedding of the Voronoi diagram.

best
        Monique Teillaud

Daniel Duque Campayo wrote:

> 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_1259
>
> Best,
>
> Daniel
>

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