CGAL users discussion list

[Raghu Kisore N <>]

 

 

From: [mailto:] On Behalf Of Efi Fogel
Sent: Monday, August 12, 2013 5:18 PM
To:
Subject: Re: [cgal-discuss] question reg class Envelope_divide_and_conquer_3

 

On Mon, Aug 12, 2013 at 7:24 AM, Raghu Kisore N <> wrote:

 

What exactly are you trying to do?

In my case I have set of 500 data points which have been broken into 2 groups of 250 points each. A voronoi diagram is created for the first 250 points and the same is done with the other 250 points. Now I am using the function merge_envelope to combine the two.

ok, but first you need to compute the 2 envelopes of the 2 structures, respectively.

How do you do that?

  Using the logic provided in the example code “print_cropped_voronoi.cpp” I first obtained cropped version of the voronoi diagrams.

By traversing over these diagrams I converted them into objects of type

Typedef Arrangement_2<Env_plane_traits_3<Traits>, Envelope_pm_dcel<Traits, Traits::Xy_monotone_surface_3> > Arrag_2

Traits in the above  are of type Env_plane_Traits_3<Cartesian<Gmpq>>

Using the above an object of the class Envelope_divide_and_conquer is created

typedef CGAL::Envelope_diagram_on_surface_2<Traits>::Arrangement min_diagram;
typedef CGAL::Envelope_divide_and_conquer_3<Traits, min_diagram> DivConq;

 

The program crashes when I call DivConq.merge_envelopes();//the three required arguments are of type Arrag_2 defined above

 

After debugging I found the following cause for the crash.

The function merge-envelopes makes use of objectàget_data() [this happens during the àresolve function call line 532 of the function merge_envelopes ] without ever calling set_data()[of course it is eventually called at the end of merge_envelopes when calling update_envelope_surfaces_decision()..line 674 ].

 

[Alternatively is there any other way of converting object of type VD into Arrangement_2?]

What version are you using?

CGAL-4.2

What kernel are you using?

I am using FC-15 and kernel version is 2.6.38

 

I meant what CGAL kernel are you using?

You must use a kernel that supports exact constructions as well as exact predicates, e.g., Exact_predicates_exact_constructions_kernel

The example “print_cropped_voronoi” uses Exact_predicates_inexact_constructions_kernel.

As per your suggestion I used Exact_predicates_exact_constructions_kernel, but it still doesn’t work.

 

I am happy if you could post an example that makes use of this class.

 

I don't have one, and as I've said, it is internal and as such it is not documented.

However, you are absolutely free to try and use it any way you want.

 

Several papers have been published claiming that the class can be used to merge two arrangement’s.

 

Can you please point them to me.

“Exact and Efficient Construction of General Voronoi Diagrams in the Plane via Divide and Conquer of Envelopes in Space” Workshop on Robust Shape Operations, INRIA Sophia-Antipolis, September 2007.  Dan Halperin Ophir Setter Micha Sharir.

“Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space” by Ophir Setter. Tel-Aviv University, May 2009

 

 

Regards

Raghu.

 

From: [mailto:] On Behalf Of Efi Fogel
Sent: Friday, August 09, 2013 7:57 PM
To:
Subject: Re: [cgal-discuss] question reg class Envelope_divide_and_conquer_3

 

This file is internal.
The class is not documented, and thus might be hard to use.

What exactly are you trying to do?

What version are you using?
What kernel are you using?

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

 

On Thu, Aug 8, 2013 at 1:09 PM, Raghu Kisore N <> wrote:

Dear All,

   The file Envelope_divide_conquer_3.h has implementation of class Envelope_divide_conquer_3

This class has some public functions one of whic is meger_envelopes(mindiagram, mindiagram, mindiagram)

The document claims the purpose of this function is to merge the 1^st 2 diagrams and provided the combined diagram in the 3^rd parameter.

 

I was wondering if anyone has been able to successfully able to create the object of this class and use the above function to combine two diagrams like say voronoi diagrams or objects of type Arrangement_2 or Arrangement_on_surface_2?

 

When it try to do it, it crashes giving the following error:

 

terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: m_data.size() > 0
File: /home/raghukisore/CGAL-4.2/examples/Triangulation_2/../../include/CGAL/Envelope_3/Envelope_pm_dcel.h
Line: 132
Aborted (core dumped)

 

Regards

Raghu.

 

N. Raghu Kisore, Ph.D.

Assistant Professor

Institute for Development & Research in Banking Technology [IDRBT]

(established by the Reserve Bank of India)

Castle Hills, Road No.1, Masab Tank,

Hyderabad, India - 500057.

Telephone: 009104023294041