Subject: CGAL users discussion list
List archive
- From: Martin Stumpf <>
- To:
- Subject: [cgal-discuss] Wrong offset from straight skeleton 2 algorithm
- Date: Thu, 10 Jul 2008 19:27:24 +0200
- Organization: Pixel GmbH
Hello,
I guess, I found a bug in CGAL straight skeleton 2 algorithm. I just used the example project coming with CGAL 3.3.1 (CGAL-3.3.1\examples\Straight_skeleton_2) using default project settings (Visual Studio 2005).
I changed the offset to 0.35 and replaced the polygon by the following one:
Point_2(22.5,0),
Point_2(22.5,12),
Point_2(22.5,12.41421),
Point_2(21.914221,13),
Point_2(21.5,13),
Point_2(19,13),
Point_2(19,25),
Point_2(0,25),
Point_2(0,0)
The result offset curve contains one wrong extra point (as you can also see in the attachment wrong_offset.bmp).
(-0.35,-0.35)
(22.85,-0.35)
(22.85,12.4142)
(22.85,12.5592)
(22.0592,13.35)
(19,13.35) <------ This point is wrong
(19.35,13.35)
(19.35,25.35)
(-0.35,25.35)
(-0.35,-0.35)
Using the precompiled demo (CGAL-3.3.1\demo\Straight_skeleton_2) instead of the example does not produce this error. The bad thing is, I can not compile the Qt demo, so comparing both examples is very hard for me and I didn't find a difference.
I hope, you can help me.
Best regards,
Martin Stumpf
#include<vector>
#include<iterator>
#include<iostream>
#include<iomanip>
#include<string>
#include<boost/shared_ptr.hpp>
#include<CGAL/basic.h>
#include<CGAL/Cartesian.h>
#include<CGAL/Polygon_2.h>
#include<CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include<CGAL/Straight_skeleton_builder_2.h>
#include<CGAL/Polygon_offset_builder_2.h>
#include<CGAL/compute_outer_frame_margin.h>
//
// This example illustrates how to use the CGAL Straight Skeleton package
// to construct an offset contour on the outside of a polygon
//
// This is the recommended kernel
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Polygon_2<Kernel> Contour;
typedef boost::shared_ptr<Contour> ContourPtr;
typedef std::vector<ContourPtr> ContourSequence ;
typedef CGAL::Straight_skeleton_2<Kernel> Ss;
typedef Ss::Halfedge_iterator Halfedge_iterator;
typedef Ss::Halfedge_handle Halfedge_handle;
typedef Ss::Vertex_handle Vertex_handle;
typedef CGAL::Straight_skeleton_builder_traits_2<Kernel> SsBuilderTraits;
typedef CGAL::Straight_skeleton_builder_2<SsBuilderTraits,Ss> SsBuilder;
typedef CGAL::Polygon_offset_builder_traits_2<Kernel>
OffsetBuilderTraits;
typedef CGAL::Polygon_offset_builder_2<Ss,OffsetBuilderTraits,Contour>
OffsetBuilder;
int main()
{
// A start-shaped polygon, oriented counter-clockwise as required for outer
contours.
Point_2 pts[] = /*{ Point_2(0,0)
, Point_2(0,2.5)
, Point_2(1.9,2.5)
, Point_2(1.9,1.3)
, Point_2(2.15,1.3)
, Point_2(2.191422,1.3)
, Point_2(2.25,1.241421)
, Point_2(2.25,1.2)
, Point_2(2.25,0)
} ;*/
{
Point_2(22.5,0),
Point_2(22.5,12),
Point_2(22.5,12.41421),
Point_2(21.914221,13),
Point_2(21.5,13),
Point_2(19,13),
Point_2(19,25),
Point_2(0,25),
Point_2(0,0)
} ;
std::vector<Point_2> star(pts,pts+9);
// We want an offset contour in the outside.
// Since the package doesn't support that operation directly, we use the
following trick:
// (1) Place the polygon as a hole of a big outer frame.
// (2) Construct the skeleton on the interior of that frame (with the
polygon as a hole)
// (3) Construc the offset contours
// (4) Identify the offset contour that corresponds to the frame and remove
it from the result
double offset = 0.35 ; // The offset distance
// First we need to determine the proper separation between the polygon and
the frame.
// We use this helper function provided in the package.
boost::optional<double> margin =
CGAL::compute_outer_frame_margin(star.begin(),star.end(),offset);
// Proceed only if the margin was computed (an extremely sharp corner might
cause overflow)
if ( margin )
{
// Get the bbox of the polygon
CGAL::Bbox_2 bbox = CGAL::bbox_2(star.begin(),star.end());
// Compute the boundaries of the frame
double fxmin = bbox.xmin() - *margin ;
double fxmax = bbox.xmax() + *margin ;
double fymin = bbox.ymin() - *margin ;
double fymax = bbox.ymax() + *margin ;
// Create the rectangular frame
Point_2 frame[4]= { Point_2(fxmin,fymin)
, Point_2(fxmax,fymin)
, Point_2(fxmax,fymax)
, Point_2(fxmin,fymax)
} ;
// Instantiate the skeleton builder
SsBuilder ssb ;
// Enter the frame
ssb.enter_contour(frame,frame+4);
// Enter the polygon as a hole of the frame (NOTE: as it is a hole we
insert it in the opposite orientation)
ssb.enter_contour(star.rbegin(),star.rend());
// Construct the skeleton
boost::shared_ptr<Ss> ss = ssb.construct_skeleton();
// Proceed only if the skeleton was correctly constructed.
if ( ss )
{
// Instantiate the container of offset contours
ContourSequence offset_contours ;
// Instantiate the offset builder with the skeleton
OffsetBuilder ob(*ss);
// Obtain the offset contours
ob.construct_offset_contours(offset,
std::back_inserter(offset_contours));
// Locate the offset contour that corresponds to the frame
// That must be the outmost offset contour, which in turn must be the
one
// with the largetst unsigned area.
ContourSequence::iterator f = offset_contours.end();
double lLargestArea = 0.0 ;
for (ContourSequence::iterator i = offset_contours.begin(); i !=
offset_contours.end(); ++ i )
{
double lArea = CGAL_NTS abs( (*i)->area() ) ; //Take abs() as
Polygon_2::area() is signed.
if ( lArea > lLargestArea )
{
f = i ;
lLargestArea = lArea ;
}
}
// Remove the offset contour that corresponds to the frame.
offset_contours.erase(f);
// Print out the skeleton
Halfedge_handle null_halfedge ;
Vertex_handle null_vertex ;
// Dump the edges of the skeleton
for ( Halfedge_iterator i = ss->halfedges_begin(); i !=
ss->halfedges_end(); ++i )
{
std::string edge_type = (i->is_bisector())? "bisector" : "contour";
Vertex_handle s = i->opposite()->vertex();
Vertex_handle t = i->vertex();
std::cout << "(" << s->point() << ")->(" << t->point() << ") " <<
edge_type << std::endl;
}
// Dump the generated offset polygons
std::cout << offset_contours.size() << " offset contours obtained\n" ;
for (ContourSequence::const_iterator i = offset_contours.begin(); i !=
offset_contours.end(); ++ i )
{
// Each element in the offset_contours sequence is a shared pointer
to a Polygon_2 instance.
std::cout << (*i)->size() << " vertices in offset contour\n" ;
for (Contour::Vertex_const_iterator j = (*i)->vertices_begin(); j !=
(*i)->vertices_end(); ++ j )
std::cout << "(" << j->x() << "," << j->y() << ")" << std::endl ;
}
}
}
return 0;
}
- [cgal-discuss] Wrong offset from straight skeleton 2 algorithm, Martin Stumpf, 07/10/2008
- Re: [cgal-discuss] Wrong offset from straight skeleton 2 algorithm, Fernando Cacciola, 07/15/2008
- Re: [cgal-discuss] Wrong offset from straight skeleton 2 algorithm, Martin Stumpf, 07/16/2008
- Re: [cgal-discuss] Wrong offset from straight skeleton 2 algorithm, Fernando Cacciola, 07/15/2008
Archive powered by MHonArc 2.6.16.