CGAL users discussion list

[Cornelia Auer <>]

Hello Menelaos Karavelas,

thanks for getting involved. I attached a file how I build the 
Segment_Delaunay_Graph_2 (SDG), it also contains a vector with the 
points I am inserting. I hope it's easy to read and maybe to copy and 
paste into some running system.

Also I attached a screenshot of the polygon - it is simple. Above that I 
don't even demand the polygon to be without strong intersections. I use 
the standard Segment_Delaunay_graph_traits_2.

Maybe it is something really simple that I'm just not seeing.
Thanks anyway for your effort.

Best,
Cornelia

PS: Just in case - is there a way to catch CGAL conditions and 
preconditions? Maybe to build a work around. I don't see yet, how I can 
check the possible non- validity of the SDG before actually inserting 
the segments.



Am 06.07.2012 06:57, schrieb Menelaos Karavelas:
> In order to determine if this is really a bug in the code or not, you need to 
> provide an input instance that creates the problem. It would also make sense 
> to send the program that you have written that creates this kind of problems.
>
> Regarding the choice of the kernel: Filtered_kernel<Simple_cartesian<double>  >  is 
> a bad choice. You should use the filtered traits instead. CGAL::Cartesian<CGAL::Gmpq>  
> and CGAL::Exact_predicates_exact_constructions_kernel should work.
>
> One final issue: how do you know that your non-convex polygon does not have 
> self-intersections? Could it be that your polygon is not really simple (i.e., 
> its edges strongly intersect), while you consider it to be simple?
> Have you tried building the segment Delaunay graph with a traits class that 
> supports segment intersections?
>
> - m.
>
> On 5 Jul 2012, at 20:56, Cornelia Auer wrote:
>
> > Thank you very much for your response!
> >
> > However using the CGAL::Exact_predicates_exact_constructions_kernel the 
> > insertion of segments breaks even earlier. I end up in:
> >
> > CGAL error: assertion violation!
> > Expression : !(i>s)
> > File       : 
> > c:\Users\bzfauerc\MyAmiraVC9\product\include\arch-Win64VC9\CGAL/In Line       
> > : 89
> > Explanation:  Variable used before being initialized (or CGAL bug)
> >
> > All I do is:
> >
> > p1=Point_2(to_exact(myDoublePoint1.x), to_exact(myDoublePoint1.y) );
> > p2=Point_2(to_exact(myDoublePoint2.x), to_exact(myDoublePoint2.y) );
> > v_h=sdg.insert(p1,p2, v_h);
> >
> > I haven't tried the CGAL::Simple_cartesian<CGAL::Gmpq>  Kernel yet, as I have 
> > trouble in my working enviroment to get it properly included.
> >
> > However if you see something obviously wrong the way I'm proceeding above I 
> > would be very happy if you let me know. Or could it really be a CGAL bug?
> >
> > Thanks in advance for your answer!
> > Best,
> > Cornelia Auer
> >
> >
> >
> > Am 05.07.2012 07:56, schrieb Sebastien Loriot (GeometryFactory):
> > > On 07/04/2012 07:46 PM, Cornelia Auer wrote:
> > > > Dear CGAL users&  developers,
> > > >
> > > > with the help of the segment_delaunay_graph_2 I try to compute the
> > > > medial axis for a given *non*-convex polygon.
> > > > To build the segment delaunay graph (SDG) I am adding edge by edge of
> > > > the initial polygon. This should give me only weakly intersecting
> > > > segments.
> > > >
> > > > Now, this works perfectly for most of my polygons, however sometimes the
> > > > construction of the SDG crashes:
> > > >
> > > > I try to insert a new segment by
> > > > v_h=sdg.insert(p1,p2, v_h);
> > > > however within the insert routine the check SDG.is_valid() fails and the
> > > > procedure crashes. But for no obvious reason (looking at the polygon).
> > > > Due to the high grade of templatization the code is really hard to
> > > > debug/step through for me. I also tried to find the answer by reading
> > > > the paper of Karavelas, but without success.
> > > >
> > > > I would be extremly thankful for any information how degenerate cases
> > > > (!SDG.is_valid()) arise for weakly intersecting input segments.
> > > >
> > > > Or if this could be a numerical issue, as I use the
> > > > Filtered_kernel<Simple_cartesian<double>  >.
> > > Indeed, you should try with a kernel with exact constructions
> > > (CGAL::Simple_cartesian<CGAL::Gmpq>  or
> > > CGAL::Exact_predicates_exact_constructions_kernel).
> > >
> > > Sebastien.
> > >
> > > > Thanks in advance for your help
> > > > Best,
> > > > Cornelia Auer
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://sympa.inria.fr/sympa/info/cgal-discuss

Attachment: PolygonCrashing.png
Description: PNG image

#ifndef SegmentDelaunayGraphExactKernel_H_
#define SegmentDelaunayGraphExactKernel_H_

#include <list>

// define the kernels
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Filtered_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Cartesian_converter.h>

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_2.h>

class SegmentDelaunayGraphExactKernel {

public: 

  typedef CGAL::Simple_cartesian<double>                                      
  CK;
  typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
  typedef CGAL::Cartesian_converter<Kernel,CK>              To_Inexact;
  typedef CGAL::Cartesian_converter<CK, Kernel>             To_Exact;
  

  typedef       Kernel::FT                                                    
                          FT;
  typedef CGAL::Segment_Delaunay_graph_traits_2<Kernel>         Gt;
  typedef CGAL::Segment_Delaunay_graph_2<Gt>                            SDG2;
  typedef Kernel::Point_2                                                     
                  Point_2;        
  typedef SDG2::Vertex_handle                                                 
          Vertex_handle;
  
 protected: 
        
        To_Inexact to_inexact;
        To_Exact to_exact;
 public:

        // Con(De)structor methods //
         SegmentDelaunayGraphExactKernel(){};
        ~SegmentDelaunayGraphExactKernel() {};

        SDG2                    sdg;
        void init();

        
} ;


void SegmentDelaunayGraphExactKernel :: init() 
{
        
        std::vector<std::pair<float, float> > inputPoints;
        inputPoints.push_back(std::pair<float, float> (30.5,0.334848));
        inputPoints.push_back(std::pair<float, float> (30.75 , 0.0478354));
        inputPoints.push_back(std::pair<float, float> (31 , -0.287013));
        inputPoints.push_back(std::pair<float, float> (31 , -0.669696));
        inputPoints.push_back(std::pair<float, float> (31.25 , -1.00454));
        inputPoints.push_back(std::pair<float, float> (31.5 , -1.31026));
        inputPoints.push_back(std::pair<float, float> (31.75 , -1.63469));
        inputPoints.push_back(std::pair<float, float> (32 , -1.95911));
        inputPoints.push_back(std::pair<float, float> (32.75 , -2.28293));
        inputPoints.push_back(std::pair<float, float> (32.75 , -2.08077));
        inputPoints.push_back(std::pair<float, float> (32.75 , -2.04021));
        inputPoints.push_back(std::pair<float, float> (32.5 , -1.83745));
        inputPoints.push_back(std::pair<float, float> (32.5 , -0.861038));
        inputPoints.push_back(std::pair<float, float> (32.75 , -0.430519));
        inputPoints.push_back(std::pair<float, float> (33 , 0));
        inputPoints.push_back(std::pair<float, float> (33.25 , 0.430519));
        inputPoints.push_back(std::pair<float, float> (33.5 , 0.813202));
        inputPoints.push_back(std::pair<float, float> (33.75 , 1.1886));
        inputPoints.push_back(std::pair<float, float> (34 , 1.55358));
        inputPoints.push_back(std::pair<float, float> (34 , 2.12132));
        inputPoints.push_back(std::pair<float, float> (31.75 , 2.60615));
        inputPoints.push_back(std::pair<float, float> (30.5 , 1.878));
        inputPoints.push_back(std::pair<float, float> (30.25 , 1.59413));
        inputPoints.push_back(std::pair<float, float> (30.25 , 0.813202));
        
        Vertex_handle v_h;
        Point_2 p1,p2;
        

        for (int i=0;i< inputPoints.size() -1; i++) {
                std::cout << i << std::endl;
                p1=Point_2(to_exact(inputPoints[i].first), 
to_exact(inputPoints[i].second));
                p2=Point_2(to_exact(inputPoints[i+1].first), 
to_exact(inputPoints[i+1].second));
                v_h=sdg.insert(p1,p2, v_h);
        }

        p1=Point_2(to_exact(inputPoints[inputPoints.size()-1].first), 
                           
to_exact(inputPoints[inputPoints.size()-1].second));
        p2=Point_2(to_exact(inputPoints[0].first), 
to_exact(inputPoints[0].second));
        v_h=sdg.insert(p1,p2,v_h);

        assert( sdg.is_valid(true, 1) );

        
        return ;

};


#endif