[Boost-users] [polygon] get_trapezoids not reporting holes?

Subject: [Boost-users] [polygon] get_trapezoids not reporting holes?
From: David Thompson (david.thompson_at_[hidden])
Date: 2016-06-22 13:57:02

Hi all,

I am having trouble with boost::polygon: when get_trapezoids is called on a polygon_set_data containing a polygon_with_holes_data, it returns trapezoids covering the outer loop but that cover the hole (i.e., the hole is being ignored). A small example is below to demonstrate. I've tried with boost 1.60, 1.55, and 1.50. Am I doing something wrong?

        Thanks,
        David

#include "boost/polygon/polygon.hpp"

#include <vector>

namespace poly = boost::polygon;

typedef long long Coord;
typedef poly::point_data<Coord> Point;

Coord outerPts[] = {
  -37205784000000LL, -22528321200000LL,
  -20252740200000LL, -40391736000000LL,
   19228717200000LL, -39708900000000LL,
   37774737000000LL,  32882157000000LL,
  -37205784000000LL, -22528321200000LL,
};

Coord innerPts[] = {
   -8808676800000LL,  -4351000500000LL,
   29799924000000LL,  21288613500000LL,
    8185023000000LL, -10611816600000LL,
   -8808676800000LL,  -4351000500000LL,
};

template<typename T>
void liftPt(double x[2], const T& pt, double sf)
{
  x[0] = sf * pt.x();
  x[1] = sf * pt.y();
}

template<typename T>
void print_polyarray(const std::string& msg, T& parr, double scale, double iscale)
{
  std::cout << msg << " has " << parr.size() << " polygons\n";
  std::vector<poly::polygon_data<Coord> >::const_iterator pit;
  int pp = 0;
  for (pit = parr.begin(); pit != parr.end(); ++pit, ++pp)
    {
    poly::polygon_data<Coord>::iterator_type pcit;
    std::cout << "  Polygon " << pp << " has " << pit->size() << " points\n";
    double p0[2];
    for (pcit = poly::begin_points(*pit); pcit != poly::end_points(*pit); ++pcit)
      {
      liftPt(p0, *pcit, iscale);
      std::cout << "  " << p0[0] << " " << p0[1] << "\n";
      }
    std::cout << "--\n";
    }
}

int main()
{
  const double scale = 2.31e13;
  const double iscale = 1./2.31e13;

  poly::polygon_with_holes_data<Coord> pface;
  std::vector<poly::polygon_data<Coord> > holes;
  poly::polygon_data<Coord> loop;

  std::vector<Point> polypts1;
  for (unsigned ii = 0; ii < sizeof(outerPts)/sizeof(outerPts[0])/2; ++ii)
    {
    polypts1.push_back(Point(outerPts[2*ii], outerPts[2*ii + 1]));
    }
  pface.set(polypts1.begin(), polypts1.end());

  std::vector<Point> polypts2;
  for (unsigned ii = 0; ii < sizeof(innerPts)/sizeof(innerPts[0])/2; ++ii)
    {
    polypts2.push_back(Point(innerPts[2*ii], innerPts[2*ii + 1]));
    }
  loop.set(polypts2.rbegin(), polypts2.rend());

  holes.push_back(loop);
  pface.set_holes(holes.begin(), holes.end());
  Point holecenter( 9725423400000LL,  2108598800000LL);
  Point nonholepnt(37774730000000LL, 32882150000000LL);
  // ^^ Compare to 37774737000000LL, 32882157000000LL, which is a vertex in outerPts.
  std::cout << "Polygon has " << pface.size() << " vertices and " << pface.size_holes() << " holes\n";
  std::cout << "Winding is " << (poly::winding(pface) == poly::CLOCKWISE ? "cw" : "ccw") << "\n";
  std::cout << "Contains hole center? " << (poly::contains(pface, holecenter) ? "Y" : "N") << "\n";
  std::cout << "Contains point it should? " << (poly::contains(pface, nonholepnt) ? "Y" : "N") << "\n";

  // The above demonstrates that pface appears to be a valid polygon with a hole.
  // However, now when we ask for trapezoids, no hole is provided:

  // Add pface to polys so we can get trapezoids:
  poly::polygon_set_data<Coord> polys;
  std::vector<poly::polygon_data<Coord> > parr;
  polys.insert(pface);

  polys.get(parr);
  // This prints that parr (and thus polys) contains 0 polygons, which seems wrong:
  print_polyarray("Original polygon set", parr, scale, iscale);

  polys.get_trapezoids(parr);
  // This prints 2 polygons that form only the outer boundary, which seems wrong:
  print_polyarray("Tessellation ", parr, scale, iscale);

  return 0;
}