CGAL users discussion list

[Bernd Gaertner <>]

MiTcX wrote:
> hi all,
>
>  i've a little problem when i try to compute the Polytope_distance_d
> between two polygons.
> here is my code  :
>
>     struct Kernel : public CGAL::Cartesian<float> {};

This is the main problem. You are using an inexact kernel, but
CGAL algorithms are only guaranteed to work correctly under
exact kernels. Please try using an exat number type, like
CGAL::Cartesian<CGAL::MP_Float> or CGAL::Cartesian<CGAL::Gmpzf>
(the latter number type is faster but available only in release 3.3).

>     std::cout<< "dist : "<<dist2.squared_distance()<<std::endl;

This function has a problem on our side (wrong return type), and
I will fix this for CGAL 3.3.1; In your case, I recommend to use
CGAL::to_double(squared_distance_numerator())/ 
CGAL::to_double(squared_distance_denominator()), this will
work (see the example programs for the Polytope_distance_d package).

> Explanation:nu <= et0 violated -- is your D matrix positive semidefinite?

This looks like you are using CGAL 3.2; but even with this release, the
problem should go away by replacing float with Gmpzf or MP_Float as
described above. In CGAL 3.3, the attached code is the fastest option;
it uses an inexact kernel, but the Polytope_distance_d package takes
care of exactness itself through the additional CGAL::Gmpzf provided
in the traits class (see also the example program
polytope_distance_d_fast_and_exact.cpp)

> i check my polygons, but they are convex.

This is irrelevant, the code does not assume this. In fact, you don't
need to have polygons to start with, but just point sets.

Best regards,
        Bernd.
#include <iostream>
#include <CGAL/Cartesian.h>
#include <CGAL/Gmpzf.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polytope_distance_d.h>
#include <CGAL/Polytope_distance_d_traits_2.h>

typedef CGAL::Cartesian<double> Kernel;
typedef CGAL::Polytope_distance_d_traits_2<Kernel, CGAL::Gmpzf, double> 
TraitsPolytope;
typedef CGAL::Polytope_distance_d<TraitsPolytope> Polytope_distance;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;

int main() {
    Polygon_2 p;
    p.push_back(Point_2(444,607));
    p.push_back(Point_2(445,97));
    p.push_back(Point_2(448,92));
    p.push_back(Point_2(449,610));
    Polygon_2 p1;
    p1.push_back(Point_2(212,91));
    p1.push_back(Point_2(448,92));
    p1.push_back(Point_2(445,97));
    p1.push_back(Point_2(213,96));
   
    Polytope_distance dist2
      (p.vertices_begin(),
       p.vertices_end(),
       p1.vertices_begin(),
       p1.vertices_end());

    std::cout<< "dist : "
	     << CGAL::to_double(dist2.squared_distance_numerator())/
                CGAL::to_double(dist2.squared_distance_denominator())
	     <<std::endl;

  return 0;

}