Wrong offset from straight skeleton 2 algorithm

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Wrong offset from straight skeleton 2 algorithm

Martin Stumpf-2
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
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

#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;
}

wrong_offset.bmp (18K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Wrong offset from straight skeleton 2 algorithm

Fernando Cacciola-3
Hello Martin,

>> Hello,
>>
>> I guess, I found a bug in CGAL straight skeleton 2 algorithm.
>>
Indeed... this has been fixed shortly after 3.3.1 went out.

I just tested it and the corrected algorithm (to be included in the next
release) works fine in your case.

If you wish to evaluate the patched algorithm I can email you an executable that
reads in a file listing the vertices of a polygon and outputs an .eps drawing
with the specified offset (see the .eps attached corresponding to your report)

HTH

Fernando Cacciola
www.geometryfactory.com

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

report.dat.offset.eps (1K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Wrong offset from straight skeleton 2 algorithm

Martin Stumpf-2
Hello Fernando,


thanks for your answer. It would be nice, if you send me the executable.
Is there also a patch for the source code or do I have to wait for the
next release? What does your roadmap say about the next release?

Thanks + Best regards,
  Martin

> Hello Martin,
>
>>> Hello,
>>>
>>> I guess, I found a bug in CGAL straight skeleton 2 algorithm.
>>>
> Indeed... this has been fixed shortly after 3.3.1 went out.
>
> I just tested it and the corrected algorithm (to be included in the next
> release) works fine in your case.
>
> If you wish to evaluate the patched algorithm I can email you an
> executable that
> reads in a file listing the vertices of a polygon and outputs an .eps
> drawing
> with the specified offset (see the .eps attached corresponding to your
> report)
>
> HTH
>
> Fernando Cacciola
> www.geometryfactory.com
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
> +----------------------------------------------------------------------+
> | Z1 SecureMail Gateway Info - http://www.zertificon.com               |
> +----------------------------------------------------------------------+
> | - Die Nachricht war weder verschluesselt noch digital unterschrieben |
> +----------------------------------------------------------------------+
>



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss