CGAL users discussion list

[Bernhard Kornberger <>]

I encountered a bug in the regular triangulation class of CGAL 3.3,
let's start with some testcode:

### CopyPaste begin ###

#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <sstream>

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_euclidean_traits_2.h>
#include <CGAL/Regular_triangulation_filtered_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>
#include <fstream>

using namespace std;

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Regular_triangulation_filtered_traits_2<K> 
TriangulationTraits;
typedef CGAL::Regular_triangulation_2<TriangulationTraits> 
Regular_triangulation;
typedef Regular_triangulation::Weighted_point Weighted_point;
typedef Regular_triangulation::Bare_point Point;

int main(int argc,char** argv)
{
        vector<Weighted_point> vWP;

        // Read the circles from a file
        cout<<"Reading: "<<argv[1]<<endl<<endl;
        ifstream in(argv[1]);
        const int BUFSIZE=1024;
        char oneLine[BUFSIZE];
        while(in.getline(oneLine,BUFSIZE))
        {
                // Erase leading spaces and discard empty lines and comment 
lines
                string buf=string(oneLine);
                buf.erase(0, buf.find_first_not_of(" "));
                if (buf.length()==0 || buf[0]=='#' || buf[0]==';' ) continue;
                double x(-99),y(-99),dist(-99),sqDist(-99);
                istringstream another_buffer(buf.c_str());
                another_buffer>>x;
                another_buffer>>y;
                another_buffer>>dist;
                Point center(x,y);
                sqDist=dist * dist;
                Weighted_point wp(center,sqDist);
                vWP.push_back(wp);
        }
        in.close();
        cout << "Number of circles: "<<vWP.size()<<endl;
        

        // Now insert them into the triangulation
        Regular_triangulation regTr;
        for(unsigned i=0;i<vWP.size();++i)
        {
                Weighted_point wp=vWP[i];
                cout << " inserting "<<wp<<endl;
                regTr.insert(wp);
                if(regTr.is_valid()) cout << "Still valid"<<endl;
                        else cout << "not valid anymore"<<endl;
                
        }
}
### CopyPaste end ###



The output of the program is:



### CopyPaste begin ###
./rtest badSpheres.cir
Reading: badSpheres.cir

Number of circles: 17
 inserting 50.6932 25.6932 716.537
Still valid
 inserting 50.1811 25.1811 689.383
Still valid
 inserting 47.3853 55 965.656
Still valid
 inserting 49.1239 55 965.656
Still valid
 inserting 45.6468 55 965.656
Still valid
 inserting 43.9083 55 965.656
Still valid
 inserting 50 55 965.656
Still valid
 inserting 50 55 965.656
face : 0x806abc0 =>
point :50.6932 25.6932 716.537   / voisin 0x806aac0[50 55 965.656 
/inf    /49.1239 55 965.656     ]
point :50 55 965.656     / voisin 0x806ab20[50.6932 25.6932 716.537 
/49.1239 55 965.656     /47.3853 55 965.656     ]
point :49.1239 55 965.656        / voisin 0x806abe0[50.6932 25.6932 
716.537     /inf    /50 55 965.656  ]
  +++++>>>    [ 50 55 965.656 ] ,
CGAL error: assertion violation!
Expr: result
File: /opt/CGAL330/include/CGAL/Regular_triangulation_2.h
Line: 710
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct NULL not valid
Aborted (core dumped)
### CopyPaste end ###


Okay, it leads to an error if one inserts the same circle a second
time. But not at the time of insertion but only if one calls:
.is_valid(). The whole thing runs if there is no redundant circle in
the input:


### CopyPaste begin ###

./rtest badSpheres_better.cir
Reading: badSpheres_better.cir

Number of circles: 16
 inserting 50.6932 25.6932 716.537
Still valid
 inserting 50.1811 25.1811 689.383
Still valid
 inserting 47.3853 55 965.656
Still valid
 inserting 49.1239 55 965.656
Still valid
 inserting 45.6468 55 965.656
Still valid
 inserting 43.9083 55 965.656
Still valid
 inserting 50 55 965.656
Still valid
 inserting 60.066 89.934 1306.17
Still valid
 inserting 57.7539 92.2461 1144.39
Still valid
 inserting 55.7417 94.2583 1012.3
Still valid
 inserting 54.0296 95.9704 906.287
Still valid
 inserting 52.6175 97.3825 823.26
Still valid
 inserting 51.5053 98.4947 760.673
Still valid
 inserting 50.6932 99.3068 716.537
Still valid
 inserting 50.1811 99.8189 689.383
Still valid
 inserting 67.2461 32.7539 1144.39
Still valid
### CopyPaste end ###


...but running the same command again in valgrind leads to:


### CopyPaste begin ###

valgrind ./rtest badSpheres_better.cir

==28900== Memcheck, a memory error detector.
==28900== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==28900== Using LibVEX rev 1658, a library for dynamic binary translation.
==28900== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==28900== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation 
framework.
==28900== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==28900== For more details, rerun with: -v
==28900==
Reading: badSpheres_better.cir

Number of circles: 16
 inserting 50.6932 25.6932 716.537
Still valid
 inserting 50.1811 25.1811 689.383
Still valid
 inserting 47.3853 55 965.656
Still valid
 inserting 49.1239 55 965.656
Still valid
 inserting 45.6468 55 965.656
Still valid
 inserting 43.9083 55 965.656
Still valid
 inserting 50 55 965.656
Still valid
 inserting 60.066 89.934 1306.17
Still valid
 inserting 57.7539 92.2461 1144.39
Still valid
 inserting 55.7417 94.2583 1012.3
Still valid
 inserting 54.0296 95.9704 906.287
Still valid
 inserting 52.6175 97.3825 823.26
Still valid
 inserting 51.5053 98.4947 760.673
CGAL error: assertion violation!
Expr: result
File: /opt/CGAL330/include/CGAL/Regular_triangulation_2.h
Line: 823
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct NULL not valid
==28900==
==28900== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 61 from 1)
==28900== malloc/free: in use at exit: 554,939 bytes in 73 blocks.
==28900== malloc/free: 309 allocs, 236 frees, 571,212 bytes allocated.
==28900== For counts of detected errors, rerun with: -v
==28900== searching for pointers to 73 not-freed blocks.
==28900== checked 1,146,740 bytes.
==28900==
==28900== LEAK SUMMARY:
==28900==    definitely lost: 0 bytes in 0 blocks.
==28900==      possibly lost: 1,140 bytes in 5 blocks.
==28900==    still reachable: 553,799 bytes in 68 blocks.
==28900==         suppressed: 0 bytes in 0 blocks.
==28900== Reachable blocks (those to which a pointer was found) are not 
shown.
==28900== To see them, rerun with: --show-reachable=yes
Aborted (core dumped)

### CopyPaste end ###


I'm using:

CGAL3.3.0
g++ (GCC) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)
valgrind-3.2.1-Debian


Any hints?


Btw: You can find the test code at: 
http://www.ist.tugraz.at/staff/kornberger/rtest.tar.gz

Best
Bernhard