CGAL users discussion list

[André Radke <>]

Hello all,

I'm trying to compute offset contours of simple polygons using the straight 
skeleton package, just like in fig. 21.3 of the CGAL user manual:

        
http://www.cgal.org/Manual/last/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html#Subsection_21.1.3

I have generally had great success using the package, but recently I 
encountered a polygon that triggers an assertion failure in the debug build. 
The assertion failure occurrs on line 944 of Straight_skeleton_builder_impl.h 
in the HandleSplitEvent method of the Straight_skeleton_builder_2 class:

        CGAL_assertion(lOppIBisector_L->prev() == lOppOBisector_R ) ;

In the release build, create_interior_straight_skeleton_2 apparently never 
returns when run on the polygon in question. This polygon is slightly unusual 
in that there are consecutive edges that are collinear or very nearly 
collinear. However, it should still be valid input for the straight skeleton 
package if I understand the documentation correctly.

I have attached a sample program below that constructs the polygon and 
demonstrates the problem. Please note that I'm using the exact predicates 
inexact constructions kernel as recommended in the documentation of the 
package.

I'm running Windows XP SP 3 and Visual Studio 2005 Express on a first 
generation Apple MacBook Pro (1.83 GHz Core Duo) via Bootcamp (i.e. not in a 
virtual machine.) I installed CGAL 3.5 via the provided Windows installer 
with GMP and MPFR binaries. I compiled my sample program with the strict 
floating-point model (/fp:strict) and with floating point exceptions 
disabled, just like the example programs from the CGAL distribution.

I'm not sure whether this is a bug in CGAL or a problem with my compiler 
settings. Therefore, if anybody would like to take a look at my Visual Studio 
demo project, I would be happy to send it to you off-list.

Thanks in advance,

André




#include <vector>

#include <boost/shared_ptr.hpp>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/create_straight_skeleton_2.h>
#include <CGAL/create_offset_polygons_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef K::Point_2 Point;

typedef CGAL::Polygon_2<K> Polygon;
typedef boost::shared_ptr<Polygon> PolygonPtr;
typedef std::vector<PolygonPtr> PolygonPtrVector;

typedef CGAL::Straight_skeleton_2<K> Ss;
typedef boost::shared_ptr<Ss> SsPtr;

typedef CGAL::Polygon_offset_builder_traits_2<K> OffsetBuilderTraits;
typedef CGAL::Polygon_offset_builder_2<Ss,OffsetBuilderTraits,Polygon> 
OffsetBuilder;


int main()
{
  Polygon poly;
  
  poly.push_back(Point(-45.454186699317802, 59.237049408412233));
  poly.push_back(Point(-42.816220506946685, 55.799184933816875));
  poly.push_back(Point(-41.395777172593, 53.94802713980399));
  poly.push_back(Point(-38.230217741747651, 49.822589770289568));
  poly.push_back(Point(-36.52568574052323, 47.601200417474111));
  poly.push_back(Point(-32.283990009183114, 50.435410893709047));
  poly.push_back(Point(-29.999999999999979, 51.96152422706632));
  poly.push_back(Point(-25.42465386223849, 54.21783524741339));
  poly.push_back(Point(-22.96100594190538, 55.432771950677207));
  poly.push_back(Point(-24.950959790203846, 60.23694551973589));
  poly.push_back(Point(-26.022473400826101, 62.823808210767496));
  poly.push_back(Point(-27.680768274408155, 66.82728618498308));
  poly.push_back(Point(-28.573696283260027, 68.983005094176079));
  poly.push_back(Point(-31.890286030424143, 76.989961042607234));
  poly.push_back(Point(-38.600793699140993, 73.680704879431531));
  poly.push_back(Point(-41.666666666666643, 72.168783648703226));
  poly.push_back(Point(-47.887820405965485, 68.011941616891974));
  poly.push_back(Point(-50.730119084060057, 66.112778357602934));

  SsPtr ss = create_interior_straight_skeleton_2(poly);

  if (!ss.get())
  {
    return -1;
  }

  OffsetBuilder ob(*ss);

  PolygonPtrVector contours;
  std::back_insert_iterator<PolygonPtrVector> iter = back_inserter(contours);
  PolygonPtrVector::size_type oldsize;

  double distance = 1.0;
  unsigned int k = 0;

  do
  {
    oldsize = contours.size();

    iter = ob.construct_offset_contours((++k) * distance, iter);

  } while (contours.size() > oldsize);

  return 0;
}






-- 
André Radke  ++  http://spicynoodles.net/