Skip to Content.
Sympa Menu

cgal-discuss - Potential bug with ch_melkman

Subject: CGAL users discussion list

List archive

Potential bug with ch_melkman


Chronological Thread 
  • From:
  • To:
  • Subject: Potential bug with ch_melkman
  • Date: Wed, 10 Oct 2007 15:05:52 +0200

I think, I have an example of a potential bug in ch_melkman.
The example should have returned 6 points instead of 5.
I try with convex_hull_2 which returns the 6 points. (just uncomment the
comment to see it)
I try with the gmpq kernel to find if there is a precision issue but the
results are the same.
Do I miss something on the condition of use of ch_melkman ?

Best regards,

Manuel.



#include <CGAL/Cartesian.h>
#include <CGAL/Gmpq.h>
#include <CGAL/ch_melkman.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
#include <iostream>
using namespace std;


template<typename CHPOINT, typename POINT_2>
void test()
{
CHPOINT in, res;

double ranges[4] = { 1.53, 1.54 };

double dtheta = 0.5*M_PI/180;
double theta=-M_PI/2.0 -dtheta/2.0;
double dr = 3.0*0.027;

for( size_t i=0; i<2; ++i )
{
double r = ranges[i];
double dir[2];
sincos( theta, &dir[1], &dir[0] );
double rmin = r-dr;
double rmax = r+dr;
in.push_back( POINT_2( rmin*dir[0], rmin*dir[1] ) );
in.push_back( POINT_2( rmax*dir[0], rmax*dir[1] ) );
theta += dtheta;
sincos( theta, &dir[1], &dir[0] );
in.push_back( POINT_2( rmax*dir[0], rmax*dir[1] ) );
in.push_back( POINT_2( rmin*dir[0], rmin*dir[1] ) );
}





CGAL::ch_melkman( in.begin(), in.end(), std::back_inserter(res) );
//CGAL::convex_hull_2( in.begin(), in.end(), std::back_inserter(res)
);

cout << "Input points:" << endl;
for( size_t i=0; i<in.size(); ++i ){
cout << in[i] << endl; }
cout << endl;

cout << "Output points:" << endl;
for( size_t i=0; i<res.size(); ++i )
{
cout << res[i] << endl;
}
cout << endl;
}

typedef CGAL::Point_2<CGAL::Cartesian<double> > Point_2;
typedef std::vector<Point_2> CHpoints_double;
typedef CGAL::Point_2<CGAL::Cartesian<CGAL::Gmpq> > Point_2_gmp;
typedef std::vector<Point_2_gmp> CHpoints_gmpq;
int main()
{
cout << "double" << endl;
test<CHpoints_double, Point_2>();

cout << "gmpq" << endl;
test<CHpoints_gmpq, Point_2_gmp>();

}



Archive powered by MHonArc 2.6.16.

Top of Page