The functions that draw objects of type Polygon_with_holes_2 and Polygon_set_2 are erroneous

[efifogel]

Issue Details

The functions that draw objects of type Polygon_with_holes_2 and Polygon_set_2 fail to draw when the outer boundary is not simple or when the outer boundary and the holes are not completely disjoint. (At least one boundary touches another.)

One solution is to obtain the 2D arrangement. The Polygon_set_2 class template has a member function, namely arrangement(), that returns the underlying arrangement. For polygons with holes, perhaps the best solution is to insert it into a Polygon_set_2 object and render the latter.
Once the arrangement is obtained, traverse the faces.
For each face, check whether it's included (a field in the face). If not, continue.

• If the face is the unbounded face, introduce an artificial rectangle that matches the window that serves as the outer boundary. (This is currently applied.)
• Imitate the procedure currently implemented for the face. This is correct, because holes in a face (a.k.a. inner boundaries) do not touch the outer boundaries or each other.

Source Code

#include <vector>
#include <boost/lexical_cast.hpp>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_set_2.h>
#include <CGAL/draw_polygon_set_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using Point = Kernel::Point_2;
using Polygon = CGAL::Polygon_2<Kernel>;
using Polygon_with_holes = CGAL::Polygon_with_holes_2<Kernel>;
using Polygon_set = CGAL::Polygon_set_2<Kernel>;

// Generate a "pyramid" made of n(n+1)/2 (approximately) equilateral triangles.
// The base of each triangle is 2 and the height is 1.732 (~sqrt(3)).
template <typename OutputIterator>
OutputIterator generate(std::size_t n, OutputIterator oi) {
  for (int j = 0; j != n; ++j) {
    for (int i = 0; i != n-j; ++i) {
      Polygon polygon;
      Kernel::FT yb(1.732 * j);
      Kernel::FT yt(1.732 * (j + 1));
      polygon.push_back(Point(Kernel::FT(j + 2 * i), yb));
      polygon.push_back(Point(Kernel::FT(j + 2 * i + 2), yb));
      polygon.push_back(Point(Kernel::FT(j + 2 * i + 1), yt));
      *oi++ = polygon;
    }
  }
  return oi;
}

int main(int argc, char* argv[]) {
  std::size_t n = (argc >= 2) ? boost::lexical_cast<std::size_t>(argv[1]) : 4;
  std::vector<Polygon> polygons;
  auto size = n*(n+1)/2;
  polygons.reserve(size);
  generate(n, std::back_inserter(polygons));
  Polygon_set R;
  for (auto it = polygons.begin(); it != polygons.end(); ++it)
    R.insert(Polygon_with_holes(*it));
  draw(R);
  return 0;
}

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): all
• Compiler: all
• Release or debug mode: both
• Specific flags used (if any): none
• CGAL version: latest (they have been erroneous from start.)
• Boost version: irrelevant
• Other libraries versions if used (Eigen, TBB, etc.): none

[gdamiand]

solved by #7751