src/polygons.cpp (6471f40) - dxfngc · BlinkenArea

polygons.cpp

/* drawing (DXF) to G-code (NGC) converter
 * Copyright 2013 Stefan Schuermans <stefan@schuermans.info>
 * Copyleft: GNU public license - http://www.gnu.org/copyleft/gpl.html
 */

#include <boost/shared_ptr.hpp>
#include <iostream>
#include <vector>

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Gmpq.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/create_offset_polygons_from_polygon_with_holes_2.h>
#include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>

#include "layer.h"
#include "path.h"
#include "point.h"
#include "polygons.h"

/**
 * @brief clear all polygons
 */
void Polygons::clear()
{
  mPolys.clear();
}

/**
 * @brief add polygons from layer
 * @param[in] layer layer to obtain the polygons from
 * @param[in] eqDist maximum distance of two points to be considered equal
 * @return if the layer could be converted to polygons and imported
 */
bool Polygons::addLayer(const Layer &layer, double eqDist)
{
  // convert all paths to simple polygons
  // once using exact construction kernel (needed by intersection, difference)
  // once using inexact construction kernel (faster offsetting)
  CgExPolyVec simplesEx;
  CgPolyVec simples;
  Layer::Paths::const_iterator path;
  for (path = layer.mPaths.begin(); path != layer.mPaths.end(); ++path) {
    // skip empty paths and paths with just one point
    if (path->mPoints.size() <= 1)
      continue;
    // check that path is closed
    if (!path->mPoints.front().equals(path->mPoints.back(), eqDist)) {
      std::cerr << "path not closed" << std::endl;
      Path::Points::const_iterator pt;
      for (pt = path->mPoints.begin(); pt != path->mPoints.end(); ++pt)
        std::cerr << "  " << pt->mX << "," << pt->mY << std::endl;
      return false;
    }
    // create simple polygon from path
    //   - do not add last point to polygon, as it is the same as the first one
    CgExPoly simpleEx;
    CgPoly simple;
    Path::Points::const_iterator pt;
    for (pt = path->mPoints.begin(); pt + 1 != path->mPoints.end(); ++pt) {
      simpleEx.push_back(CgExPoint(pt->mX, pt->mY));
      simple.push_back(CgPoint(pt->mX, pt->mY));
    }
    // check that polygon is simple
    if (!simpleEx.is_simple()) {
      std::cerr << "path is not simple (maybe self-itersecting?)" << std::endl;
      Path::Points::const_iterator pt;
      for (pt = path->mPoints.begin(); pt != path->mPoints.end(); ++pt)
        std::cerr << "  " << pt->mX << "," << pt->mY << std::endl;
      return false;
    }
    // ensure orientation is clockwise (must be the same for all polygons)
    if (simpleEx.is_clockwise_oriented()) {
      simpleEx.reverse_orientation();
      simple.reverse_orientation();
    }
    // collect polygons
    simplesEx.push_back(simpleEx);
    simples.push_back(simple);
  } // for path

// check that no partly overlaps are present
  // deterine which polygon is contained in which one
  std::vector<ssize_t> contained_in; // idx: contained poly, val: containing poly
  ssize_t ia, ib;
  CgExPolyVec::const_iterator a, b;
  for (a = simplesEx.begin(); a != simplesEx.end(); ++a)
    contained_in.push_back(-1); // not contained in any polygon
  for (a = simplesEx.begin(), ia = 0; a != simplesEx.end(); ++a, ++ia) {
    b = a;
    ib = ia;
    for (++b, ++ib; b != simplesEx.end(); ++b, ++ib) {
      // A and B intersect each other
      if (CGAL::do_intersect(*a, *b)) {
        // compute differences A - B and B - A
        CgExPolyHolesVec a_b, b_a;
        CGAL::difference(*a, *b, std::back_inserter(a_b));
        CGAL::difference(*b, *a, std::back_inserter(b_a));
        if (a_b.empty()) {
          // A and B are identical
          if (b_a.empty()) {
            std::cerr << "duplicate polygons found - meaning is undefined"
                      << std::endl;
            return false;
          }
          // B contains A (A is hole in B)
          else {
            if (contained_in.at(ia) >= 0) {
              std::cerr << "polygon contained in multiple polygons"
                           " - meaning is undefined" << std::endl;
              return false;
            }
            contained_in.at(ia) = ib;
          }
        } else {
          // A contains B (B is hole in A)
          if (b_a.empty()) {
            if (contained_in.at(ib) >= 0) {
              std::cerr << "polygon contained in multiple polygons"
                           " - meaning is undefined" << std::endl;
              return false;
            }
            contained_in.at(ib) = ia;
          }
          // A and B overlap partly
          else {
            std::cerr << "polygons overlap partly - meaning is undefined"
                      << std::endl;
            return false;
          }
        }
      }
    } // for b
  } // for a

// add found polygons to member variable
  for (ia = 0; (size_t)ia < contained_in.size(); ++ia) {
    // outer polygon
    if (contained_in.at(ia) < 0) {
      CgPolyHoles poly(simples.at(ia));
      // find and add holes
      for (ib = 0; (size_t)ib < contained_in.size(); ++ib) {
        if (contained_in.at(ib) == ia) {
          // holes must be counter-clockwise
          simples.at(ib).reverse_orientation();
          poly.add_hole(simples.at(ib));
        }
      }
      // add polygon to member variable
      mPolys.push_back(poly);
    }
  }

return true;
}

/**
 * @brief load polygons from layer
 * @param[in] layer layer to obtain the polygons from
 * @param[in] eqDist maximum distance of two points to be considered equal
 * @return if the layer could be converted to polygons and imported
 */
bool Polygons::loadLayer(const Layer &layer, double eqDist)
{
  clear();
  return addLayer(layer, eqDist);
}

/**
 * @brief create inner offset polygons
 * @param[in] offset offset, > 0.0
 * @param[out] offsetPolys offset polygons (!= *this)
 * @return if inner offset polygons could be constructed
 */
bool Polygons::createInnerOffset(double offset, Polygons &offsetPolys) const
{
  // clear output polygons
  offsetPolys.mPolys.clear();
  // leave if offset size is invalid
  if (offset <= 0.0) {
    std::cerr << "invalid polygon offset distance " << offset << std::endl;
    return false;
  }

// process all polygons
  CgPolyHolesVec::const_iterator poly;
  for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {

// create inner offset polygons
    CgPolyHolesPtrVec offPolys =
      CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2(
        offset, *poly);

// add offset polygons to output polygons
    CgPolyHolesPtrVec::const_iterator offPoly;
    for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
      offsetPolys.mPolys.push_back(**offPoly);

} // for poly

return true;
}

/**
 * @brief create outer offset polygons
 * @param[in] offset offset, > 0.0
 * @param[out] offsetPolys offset polygons (!= *this)
 * @return if outer offset polygons could be constructed
 */
bool Polygons::createOuterOffset(double offset, Polygons &offsetPolys) const
{
  // clear output polygons
  offsetPolys.mPolys.clear();
  // leave if offset size is invalid
  if (offset <= 0.0) {
    std::cerr << "invalid polygon offset distance " << offset << std::endl;
    return false;
  }

// process all polygons
  CgPolyHolesVec::const_iterator poly;
  for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {
    offsetPolys.mPolys.push_back(CgPolyHoles());
    createOuterOffsetPoly(*poly, offset, offsetPolys.mPolys.back());
  }

return true;
}

/**
 * @brief fill insides of polygons by creating inner offset polygons
 * @param[in] offset offset, > 0.0
 * @param[out] offsetPolys offset polygons (!= *this)
 * @return if insides of polygons could be filles with inner offset polygons
 */
bool Polygons::fillInnerOffset(double offset, Polygons &offsetPolys) const
{
  // clear output polygons
  offsetPolys.mPolys.clear();
  // leave if offset size is invalid
  if (offset <= 0.0) {
    std::cerr << "invalid polygon offset distance " << offset << std::endl;
    return false;
  }

// process all polygons
  CgPolyHolesVec::const_iterator poly;
  for (poly = mPolys.begin(); poly != mPolys.end(); ++poly) {

// create interior straight skeleton
    CgSsPtr skel = CGAL::create_interior_straight_skeleton_2(*poly);

// create inner offset polygons with increasing offset
    size_t i;
    for (i = 1; ; ++i) {

// create inner offset polygons
      CgPolyPtrVec offPolys =
        CGAL::create_offset_polygons_2<CgPoly>(offset * i, *skel);

// no offset polygons -> done
      if (offPolys.empty())
        break;

// add offset polygons to output polygons
      CgPolyPtrVec::const_iterator offPoly;
      for (offPoly = offPolys.begin(); offPoly != offPolys.end(); ++offPoly)
        offsetPolys.mPolys.push_back(CgPolyHoles(**offPoly));

} // for i

} // for poly

return true;
}

/**
 * @brief add all polygons with holes as multiple paths to a layer
 * @param[in,out] layer layer to add paths to
 */
void Polygons::addToLayer(Layer &layer) const
{
  CgPolyHolesVec::const_iterator poly;
  for (poly = mPolys.begin(); poly != mPolys.end(); ++poly)
    PolyHolesToLayer(*poly, layer);
}

/**
 * @brief write all polygons with holes as multiple paths to a layer
 * @param[in,out] layer layer to write paths to
 */
void Polygons::writeToLayer(Layer &layer) const
{
  layer.mPaths.clear();
  addToLayer(layer);
}

/**
 * @brief create outer offset polygon
 * @param[in] poly polygon to create outer offset of
 * @param[in] offset offset, > 0.0
 * @param[out] offsetPoly offset polygon (!= *this)
 * @return if outer offset polygon could be constructed
 */
bool Polygons::createOuterOffsetPoly(const CgPolyHoles &poly, double offset,
                                     CgPolyHoles &offsetPoly)
{
  // calculate outer offset of outer bondary
  const CgPoly &outer = poly.outer_boundary();
  CgPolyPtrVec outOffPolys =
    CGAL::create_exterior_skeleton_and_offset_polygons_2(
      offset, outer);
  /* outer Offset should now contain 2 polygons,
     the artificially added very outer boundary and the offset polygon */
  if (outOffPolys.size() != 2) {
    std::cerr << "internal error during outer offset computation" << std::endl;
    return false;
  }
  offsetPoly = CgPolyHoles(*outOffPolys.at(1)); // use offset polygon

// calculate inner offset of holes
  CgPolyHoles::Hole_const_iterator hole;
  for (hole = poly.holes_begin(); hole != poly.holes_end(); ++hole) {
    CgPoly holeRev = *hole; // reverse orientation (make hole a normal poly)
    holeRev.reverse_orientation();
    CgPolyPtrVec inOffPolys =
      CGAL::create_interior_skeleton_and_offset_polygons_2(
        offset, holeRev);
    CgPolyPtrVec::iterator inOff; // add inner offset polys as new holes
    for (inOff = inOffPolys.begin(); inOff != inOffPolys.end(); ++inOff) {
      (*inOff)->reverse_orientation(); // re-reverse (make poly a hole again)
      offsetPoly.add_hole(**inOff);
    }
  }

return true;
}

/**
 * @brief add a polygon as path to a layer
 * @param[in] poly polygon to add to layer
 * @param[in,out] layer layer to add path to
 */
void Polygons::PolyToLayer(const CgPoly &poly, Layer &layer)
{
  // ignore empty polygons
  if (poly.vertices_begin() == poly.vertices_end())
    return;
  // create new path
  layer.mPaths.push_back(Path());
  Path &path = layer.mPaths.back();
  // add all points
  CgPoly::Vertex_const_iterator v;
  for (v = poly.vertices_begin(); v != poly.vertices_end(); ++v)
    path.addPoint(CGAL::to_double(v->x()), CGAL::to_double(v->y()));
  // add first point again to close path
  path.addPoint(path.mPoints.front());
}

/**
 * @brief add a polygon with holes as multiple paths to a layer
 * @param[in] poly polygon with holes to add to layer
 * @param[in,out] layer layer to add paths to
 */
void Polygons::PolyHolesToLayer(const CgPolyHoles &poly, Layer &layer)
{
  PolyToLayer(poly.outer_boundary(), layer);
  CgPolyHoles::Hole_const_iterator hole;
  for (hole = poly.holes_begin(); hole != poly.holes_end(); ++hole)
    PolyToLayer(*hole, layer);
}

dxfngc

revert to inexact construction kernel for polygon offsetting because it is way faster