CGAL users discussion list

["J.L.M." <>]

Attached are two simple programs that demonstrate my difficulties with 
2D Minkowski sums. The first one, mks_point.cpp enters into an infinite 
loop when attempting to calculate the Minkowski sum of one polygon with 
another polygon that contains only one single point. It is my 
expectation that the result of such a computation is merely the 
translation of the polygon by the point.

Secondly, and more important to me, I need to calculate the Minkowski 
sum of a polygon and an edge of another polygon. I am doing that by 
making a polygon with only two verticies. The second program shows my 
problem. The output is:

{ Outer boundary = [ 14 vertices: (-7 -3) (-7 -13) (-13 -13) (-13 -3) 
(-17 -3) (-27 -3) (-27 -17) (-3 -17) (7 -17) (7 -3) (3 -3) (7 -3) (7 
-17) (-3 -17) ]
  0 holes:
 }

Which is incorrect. The last three verticies should not exist, and if 
you look closely, they backtrack along the path around the polygon. When 
I use the verticies in an OpenGL program to display the polygon, I get a 
nonsensical shape. If those last three verticies were not there, then 
the shape would be correct. It is a U shape with square corners, 
translated horizontally. So the vertical parts of the U shape should be 
thick due to the translation.

When I remove the negative signs from the Q polygon, then the output is 
correct.

I would appreciate some help with this. I did not see anything in the 
CGAL manual stating that there were restrictions on the Minkowski sum 
operation.

Thanks.
#include <CGAL/Cartesian.h>
#include <CGAL/minkowski_sum_2.h>

#include <print_utils.h>

typedef CGAL::Cartesian<float>                Kernel;
typedef Kernel::Point_2                             Point_2;
typedef CGAL::Polygon_2<Kernel>                     Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>          Polygon_with_holes_2;

int main(int argc, char* argv[])
{
  Polygon_2   P;
  P.push_back (Point_2 (0, 0));
  P.push_back (Point_2 (10, 0));

  Polygon_2   Q;
  Q.push_back (Point_2 (-3, -3));
  Q.push_back (Point_2 (-7, -3));
  Q.push_back (Point_2 (-7, -13));
  Q.push_back (Point_2 (-23, -13));
  Q.push_back (Point_2 (-23, -3));
  Q.push_back (Point_2 (-27, -3));
  Q.push_back (Point_2 (-27, -17));
  Q.push_back (Point_2 (-3, -17));
  Polygon_with_holes_2 sum=minkowski_sum_2(P, Q);
  print_polygon_with_holes(sum);
  return (0);
}

#include <CGAL/Cartesian.h>
#include <CGAL/minkowski_sum_2.h>

typedef CGAL::Cartesian<float>                Kernel;
typedef Kernel::Point_2                             Point_2;
typedef CGAL::Polygon_2<Kernel>                     Polygon_2;
typedef CGAL::Polygon_with_holes_2<Kernel>          Polygon_with_holes_2;

int main(int argc, char* argv[])
{
  Polygon_2   P;
  P.push_back (Point_2 (0, 0));

  Polygon_2   Q;
  Q.push_back (Point_2 (3, 3));
  Q.push_back (Point_2 (7, 3));
  Q.push_back (Point_2 (7, 13));
  Q.push_back (Point_2 (23, 13));
  Q.push_back (Point_2 (23, 3));
  Q.push_back (Point_2 (27, 3));
  Q.push_back (Point_2 (27, 17));
  Q.push_back (Point_2 (3, 17));
  Polygon_with_holes_2 sum=minkowski_sum_2(P, Q);
  return (0);
}