CGAL users discussion list

[Nicklas SB Karlsson <>]

Attached as a .zip file.

Or if your prefer also as separate files. CMakeLists.txt in top directory, src_CmakeLists.txt renamed to CMakeLists.txt put into src subdirectory, main.cpp put in src subdirectory, ConstantToolEngagementAngle.cbp Codeblocks project file put into subdirectory maybe with name ConstantToolEngagementAngle.

Make subdirectory build if needed and change to this directory. Run cmake .. and then run make and then there should be a executable built into the build directory.

Regards Nicklas  Karlsson

lör 2023-11-25 klockan 10:53 +0200 skrev Efi Fogel:

Please provide a complete stand-alone example that compiles.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Fri, 24 Nov 2023 at 23:44, Nicklas SB Karlsson <> wrote:

Have been able to make polygons with connected lines, circles and
boolean operations in between them. While possible to make polygons with
circular arcs using boolean operations of these it is not a desirable
solution. Preferred solution is of course to add lines and then needed
circular arcs.

Have code below that for some angles cases succeed making a polygon with
half circle and a line connecting the two endpoints example in attached
picture. It seems to work perfect for different angles then circle is to
the right the first if condition if(p2.y() < p3.y()) in code snippet
below. But for the second if condition if(p2.y() > p3.y()) it only seems
to work then pointing to the left the angle=PI but otherwise fail with
the error message at bottom. Suspect this is because something does not
fit perfectly together for example the points on the circle. Guess I am
not the first person try to do this. Anybody have any suggestions how to
make it work?

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 K_Point_2;
typedef CGAL::Arr_circle_segment_traits_2<Kernel>::Point_2 Apoint_2;
typedef Kernel::Circle_2 K_Circle_2;
typedef CGAL::Gps_circle_segment_traits_2<Kernel> Traits_2; /* The
traits class Gps_circle_segment_traits_2 models the
GeneralPolygonSetTraits_2 concept.
                                                                      *
It enables Boolean set-operations on general polygons bounded by linear
segments or circular arcs. It should be parameterized with a kernel. */
typedef CGAL::General_polygon_set_2<Traits_2> Polygon_set_2;
typedef Traits_2::General_polygon_2 Polygon_2;
typedef Traits_2::General_polygon_with_holes_2 Polygon_with_holes_2;
typedef Traits_2::Curve_2                                 Curve_2;
typedef Traits_2::X_monotone_curve_2 X_monotone_curve_2;
typedef Traits_2::CoordNT                                 coordnt;

tool_type::tool_type(point_type pOld, point_type pNew)
{
   const double xOld = pOld.x;
   const double yOld = pOld.y;
   const double xNew = pNew.x;
   const double yNew = pNew.y;
   const double radius = 6;
   const double angle = atan2(yNew-yOld, xNew-xOld);
   const FT radiusFT = radius;

   {
     const K_Point_2 p0(xOld+radius*std::cos(angle + M_PI/2),
yOld+radius*std::sin(angle + M_PI/2)); // angle zero and pNew to the right
     const K_Point_2 p1(xOld+radius*std::cos(angle - M_PI/2),
yOld+radius*std::sin(angle - M_PI/2)); // of pOld arrangement below:
     const K_Point_2 p2(xNew+radius*std::cos(angle - M_PI/2),
yNew+radius*std::sin(angle - M_PI/2)); //   p0 p3
     const K_Point_2 p3(xNew+radius*std::cos(angle + M_PI/2),
yNew+radius*std::sin(angle + M_PI/2)); //   p1 p2

     {
       Polygon_2 pgn;
       const K_Circle_2 tool_circle(K_Point_2(xOld,yOld),
radiusFT*radiusFT);
       const K_Circle_2 tool_circle2(p2, p3, CGAL::COUNTERCLOCKWISE);
       toolFront = construct_polygon(tool_circle);
       monotone_curves_type cc;// = construct_circular_arc(tool_circle2,
radiusFT, p2, p3, CGAL::COUNTERCLOCKWISE); // Test function remove!!
then done
       if(p2.y() < p3.y())
       {
         const Apoint_2 p(p2.x(), p2.y());
         const K_Point_2 pRight(xNew + radius, yNew);
         const Apoint_2 r(p3.x(), p3.y());
         const K_Circle_2 c(p2, pRight, p3);
         const K_Point_2 center = c.center();
         const Apoint_2 q(pRight.x(), pRight.y());

         cc.x1 = X_monotone_curve_2(c, p, q, CGAL::COUNTERCLOCKWISE);
         cc.x2 = X_monotone_curve_2(c, q, r, CGAL::COUNTERCLOCKWISE);
         cc.valid = 2;
       }
       if(p2.y() > p3.y())
       {
         const Apoint_2 p(p2.x(), p2.y());
         const K_Point_2 pLeft(xNew - radius, yNew);
         const Apoint_2 r(p3.x(), p3.y());
         const K_Circle_2 c(p2, pLeft, p3);
         const K_Point_2 center = c.center();
         const Apoint_2 q(pLeft.x(), pLeft.y());

         cc.x1 = X_monotone_curve_2(c, p, q, CGAL::COUNTERCLOCKWISE);
         cc.x2 = X_monotone_curve_2(c, q, r, CGAL::COUNTERCLOCKWISE);
         cc.valid = 2;
       }
       pgn.push_back(cc.x1);
       pgn.push_back(cc.x2);
       pgn.push_back(X_monotone_curve_2(p3, p2));

       closed.insert(pgn);
     }
   }
}

terminate called after throwing an instance of
'CGAL::Precondition_exception'

   what(): CGAL ERROR: precondition violation!

Expr: cv1.point_position (p) == EQUAL && cv2.point_position (p) == EQUAL

File: /usr/include/CGAL/Arr_circle_segments_traits2.h

Line: 255

Aborted

For the curios persons it should be used to iteratively calculate tool
path for a CNC machine. If Successful I will try to add it to the CAM
module called path workbench in Freecad. At first tried to use the
builtin representation of material and tool shape but seems I got some
accuracy problem. Then I tried Open Cascade which Freecad use internally
or are built upon so to say but calculations where slow. So then I
decided to switch to CGAL as I had seen before it have an impressive
list of developers so guess it is the best possible to get.

Nicklas SB Karlsson

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Gps_circle_segment_traits_2.h>
#include <CGAL/General_polygon_set_2.h>

#include <boost/iterator/function_output_iterator.hpp>

#include <QtGui/QPainterPath>
#include <CGAL/Qt/GraphicsViewNavigation.h>

#include <QApplication>
#include <QGraphicsScene>
#include <QGraphicsView>
#include <QtMath>
#include <QDebug>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2                                   K_Point_2;
typedef CGAL::Arr_circle_segment_traits_2<Kernel>::Point_2 Apoint_2;
typedef Kernel::Circle_2                                  K_Circle_2;
typedef CGAL::Gps_circle_segment_traits_2<Kernel>         Traits_2; /* The traits class Gps_circle_segment_traits_2 models the GeneralPolygonSetTraits_2 concept.
                                                                     * It enables Boolean set-operations on general polygons bounded by linear segments or circular arcs. It should be parameterized with a kernel. */
typedef CGAL::General_polygon_set_2<Traits_2>             Polygon_set_2;
typedef Traits_2::General_polygon_2                       Polygon_2;
typedef Traits_2::General_polygon_with_holes_2            Polygon_with_holes_2;
typedef Traits_2::Curve_2                                 Curve_2;
typedef Traits_2::X_monotone_curve_2                      X_monotone_curve_2;
typedef Kernel::FT                                        FT;
typedef Kernel::RT                                        RT;
typedef Traits_2::CoordNT                                 coordnt;

typedef struct
{
  X_monotone_curve_2 x1;
  X_monotone_curve_2 x2;
  int valid = 0;          // Number of valid monotone curves
} monotone_curves_type;

class tool_type
{
public :
  typedef struct
  {
    double x;
    double y;
  } point_type;

  Polygon_set_2 closed;		  // All four edges connected to a wire, used to face to subtract machined material from stock
  tool_type(point_type pOld, point_type pNew);
private :
};

int draw_General_Polygon_2(int argc, char **argv, Polygon_set_2 polygon);

int main(int argc, char **argv)
{
  Polygon_set_2 S;
  /* Boolean operations: do_instersect, intersection, join, difference, symmetric difference. */
  {
    tool_type::point_type oldPos = {.x=30.0, .y=0.0};
    tool_type::point_type newPos = {.x=25, .y=0};
    tool_type tool(oldPos, newPos);

    S.join(tool.closed);
  }

  return draw_General_Polygon_2(argc, argv, S);
}

tool_type::tool_type(point_type pOld, point_type pNew)
{
  const double xOld = pOld.x;
  const double yOld = pOld.y;
  const double xNew = pNew.x;
  const double yNew = pNew.y;
  const double radius = 6;
  const double angle = atan2(yNew-yOld, xNew-xOld);
  const FT radiusFT = radius;

  {
    const K_Point_2 p0(xOld+radius*std::cos(angle + M_PI/2), yOld+radius*std::sin(angle + M_PI/2)); // angle zero and pNew to the right
    const K_Point_2 p1(xOld+radius*std::cos(angle - M_PI/2), yOld+radius*std::sin(angle - M_PI/2)); // of pOld arrangement below:
    const K_Point_2 p2(xNew+radius*std::cos(angle - M_PI/2), yNew+radius*std::sin(angle - M_PI/2)); //   p0 p3
    const K_Point_2 p3(xNew+radius*std::cos(angle + M_PI/2), yNew+radius*std::sin(angle + M_PI/2)); //   p1 p2

    {
      Polygon_2 pgn;
      const K_Circle_2 tool_circle(K_Point_2(xOld,yOld), radiusFT*radiusFT);
      const K_Circle_2 tool_circle2(p2, p3, CGAL::COUNTERCLOCKWISE);
      monotone_curves_type cc;// = construct_circular_arc(tool_circle2, radiusFT, p2, p3, CGAL::COUNTERCLOCKWISE); // Test function remove!! then done
      if(p2.y() < p3.y())
      {
        const Apoint_2 p(p2.x(), p2.y());
        const K_Point_2 pRight(xNew + radius, yNew);
        const Apoint_2 r(p3.x(), p3.y());
        const K_Circle_2 c(p2, pRight, p3);
        const K_Point_2 center = c.center();
        const Apoint_2 q(pRight.x(), pRight.y());

        cc.x1 = X_monotone_curve_2(c, p, q, CGAL::COUNTERCLOCKWISE);
        cc.x2 = X_monotone_curve_2(c, q, r, CGAL::COUNTERCLOCKWISE);
        cc.valid = 2;
      }
      if(p2.y() > p3.y())
      {
        const Apoint_2 p(p2.x(), p2.y());
        const K_Point_2 pLeft(xNew - radius, yNew);
        const Apoint_2 r(p3.x(), p3.y());
        const K_Circle_2 c(p2, pLeft, p3);
        const K_Point_2 center = c.center();
        const Apoint_2 q(pLeft.x(), pLeft.y());

        cc.x1 = X_monotone_curve_2(c, p, q, CGAL::COUNTERCLOCKWISE);
        cc.x2 = X_monotone_curve_2(c, q, r, CGAL::COUNTERCLOCKWISE);
        cc.valid = 2;
      }
      pgn.push_back(cc.x1);
      pgn.push_back(cc.x2);
      pgn.push_back(X_monotone_curve_2(p3, p2));

      closed.insert(pgn);
    }
  }
}

static QPainterPath construct_path(const Polygon_2 &pgn)
{
  QPainterPath result;

  Q_ASSERT(pgn.orientation() == CGAL::CLOCKWISE ||
           pgn.orientation() == CGAL::COUNTERCLOCKWISE);

  // Degenerate polygon, ring.size() < 3
  if (pgn.orientation() == CGAL::ZERO)
    {
      qWarning() << "construct_path: Ignoring degenerated polygon";
      return  result;
    }

  const bool isClockwise = pgn.orientation() == CGAL::CLOCKWISE;

  Polygon_2::Curve_const_iterator current = pgn.curves_begin();
  Polygon_2::Curve_const_iterator end = pgn.curves_end();

  result.moveTo(CGAL::to_double(current->source().x()),
                CGAL::to_double(current->source().y()));

  do
    {
      const Polygon_2::X_monotone_curve_2 &curve = *current;
      const auto &source = curve.source();
      const auto &target = curve.target();

      if (curve.is_linear())
        {
          std::cout << "curve.linear() = (" << CGAL::to_double(source.x()) << ", " << CGAL::to_double(source.y()) << ")<->(";
          std::cout << CGAL::to_double(target.x()) << ", " << CGAL::to_double(target.y()) << ")\n";
          result.lineTo(QPointF(CGAL::to_double(target.x()),
                                CGAL::to_double(target.y())));
        }
      else if (curve.is_circular())
        {
          const auto bbox = curve.supporting_circle().bbox();
          const QRectF rect(QPointF(bbox.xmin(), bbox.ymin()),
                            QPointF(bbox.xmax(), bbox.ymax()));
          const auto center = curve.supporting_circle().center();
          const double asource = qAtan2(CGAL::to_double(source.y() - center.y()),
                                        CGAL::to_double(source.x() - center.x()));
          const double atarget = qAtan2(CGAL::to_double(target.y() - center.y()),
                                        CGAL::to_double(target.x() - center.x()));
          double aspan = atarget - asource;
          if (aspan < -CGAL_PI || (qFuzzyCompare(aspan, -CGAL_PI) && !isClockwise))
            aspan += 2.0*CGAL_PI;
          else if (aspan > CGAL_PI || (qFuzzyCompare(aspan, CGAL_PI) && isClockwise))
            aspan -= 2.0*CGAL_PI;
          result.arcTo(rect, qRadiansToDegrees(-asource), qRadiansToDegrees(-aspan));
          std::cout << "curve.is_circular() center=" << center << " (" <<
                    CGAL::to_double(source.x()) << ", " << CGAL::to_double(source.y()) << ")<->(" <<
                    CGAL::to_double(target.x()) << ", " << CGAL::to_double(target.y()) << ")\n";
        }
      else   // ?!?
        {
          Q_UNREACHABLE();
        }
    }
  while (++current != end);

  return result;
}

int draw_General_Polygon_2(int argc, char **argv, Polygon_set_2 S)
{
  QApplication app(argc, argv);
  QGraphicsScene scene;

  // Insert the resulting polygons into the graphics scene
  S.polygons_with_holes(boost::make_function_output_iterator([&scene](const Polygon_with_holes_2 &pgn)
  {
    if (!pgn.is_unbounded())
      scene.addPath(construct_path(pgn.outer_boundary()), QPen(Qt::green, 0.0), Qt::darkGreen);

    Polygon_with_holes_2::Hole_const_iterator current = pgn.holes_begin();
    Polygon_with_holes_2::Hole_const_iterator end = pgn.holes_end();
    while (current != end)
      {
        scene.addPath(construct_path(*current), QPen(Qt::red, 0.0), Qt::darkRed);
        current++;
      }
  }));

  // And show the result
  QGraphicsView view;
  view.setBackgroundBrush(QColor("#073642"));
  view.setInteractive(true);
  view.setDragMode(QGraphicsView::ScrollHandDrag);
  scene.setSceneRect(scene.itemsBoundingRect());
  view.setScene(&scene);
  view.fitInView(scene.sceneRect(), Qt::KeepAspectRatio);
  view.scale(1, -1); // Revert Y-axis

  CGAL::Qt::GraphicsViewNavigation navigation;
  view.installEventFilter(&navigation);
  view.viewport()->installEventFilter(&navigation);
  view.setRenderHint(QPainter::Antialiasing);

  view.show();
  return app.exec();
}
file(GLOB ConstantToolAngle_SRC
"*.cxx"
"*.cpp"
"Samples.qrc")

target_sources(ConstantToolEngagementAngle PUBLIC ${ConstantToolAngle_SRC})
# Created by the script cgal_create_cmake_script
# This is the CMake script for compiling a CGAL application.

cmake_minimum_required(VERSION 3.1...3.15)
project(ConstantToolEngagementAngle CXX)


find_package(CGAL REQUIRED OPTIONAL_COMPONENTS Qt5)

if(CGAL_Qt5_FOUND)
  add_definitions(-DCGAL_USE_BASIC_VIEWER -DQT_NO_KEYWORDS)
endif()

add_executable(ConstantToolEngagementAngle)
add_subdirectory(src)

# create a target per cppfile
#file(
#  GLOB cppfiles
#  RELATIVE ${CMAKE_CURRENT_SOURCE_DIR}
#  ${CMAKE_CURRENT_SOURCE_DIR}/*.cpp)
#foreach(cppfile ${cppfiles})
#  create_single_source_cgal_program("${cppfile}")
#endforeach()

if(CGAL_Qt5_FOUND)
  #target_link_libraries(draw_polygon PUBLIC CGAL::CGAL_Qt5)
  target_link_libraries(ConstantToolEngagementAngle PUBLIC CGAL::CGAL_Qt5)
endif()

Attachment: ConstantToolEngagementAngle.cbp
Description: application/codeblocks

Attachment: ConstantToolAngleCGAL.zip
Description: Zip archive