Why doesn't i get any intersections of these polygons?

Question

I learn how to use boost::polygon library with custom polygons. I took an example with usage of custom polygons and tried to get intersections of these. I doesn't get any intersection and can't understand why. Also, you can see this constructor

CPoint(boost::polygon::point_data<int> pd) 

I can't compile my program without it. Can someone explain, why i need it? What do i do wrong ?

/*
Copyright 2008 Intel Corporation

Use, modification and distribution are subject to the Boost Software License,
Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt).
*/
#include <boost/polygon/polygon.hpp>
#include <cassert>
#include <list>
namespace gtl = boost::polygon;
using namespace boost::polygon::operators;


template <typename Polygon>
void test_polygon()  
{
  

  typedef typename gtl::polygon_traits<Polygon>::point_type Point;
  Point pts[] = {gtl::construct<Point>(6, 0),
                 gtl::construct<Point>(0, 6),
                 gtl::construct<Point>(-6, 0),
                 gtl::construct<Point>(0, -6),
                 };
  Polygon poly, poly2;
  gtl::set_points(poly, pts, pts+5);

  Point pts2[] = {gtl::construct<Point>(4, 0),
                 gtl::construct<Point>(4, 4),
                 gtl::construct<Point>(0, 4),
                 gtl::construct<Point>(0, 0),
                };

  gtl::set_points(poly2, pts2, pts2+5);


  std::vector<Polygon> res;
  //boost::polygon::polygon_set_data<int> res;
  //res += poly;
  //assign(res, poly);
  res.push_back(poly);
  res &= poly2;
  std::cout << "size = " << res.size() << std::endl;
  assert(!res.empty());
  //for(auto it = res[0].begin(); it != res[0].end(); ++it)
  //    std::cout << "Point(" << it->x << ", " << it->y << ")" << std::endl;
  assert(gtl::area(poly) == 100.0f);
  
}

struct CPoint {
  CPoint()=default;
  CPoint(boost::polygon::point_data<int> pd) /*---> WHY? What for ? I implemented constructor with traits*/
  {
    x = pd.x();
    y = pd.y();
  }
  int x;
  int y;
};


namespace boost { namespace polygon {
  template <>
  struct geometry_concept<CPoint> { typedef point_concept type; };
  template <>
  struct point_traits<CPoint> {
    typedef int coordinate_type;

    static inline coordinate_type get(const CPoint& point,
    orientation_2d orient) {
      if(orient == HORIZONTAL)
        return point.x;
      return point.y;
    }
  };

  template <>
  struct point_mutable_traits<CPoint> {
    typedef int coordinate_type;

    static inline void set(CPoint& point, orientation_2d orient, int value) {
      if(orient == HORIZONTAL)
        point.x = value;
      else
        point.y = value;
    }
    static inline CPoint construct(int x_value, int y_value) {
      CPoint retval;
      retval.x = x_value;
      retval.y = y_value;
      return retval;
      }
    };
  } 
}


typedef std::list<CPoint> CPolygon;


namespace boost { 
  namespace polygon {

  template <>
  struct geometry_concept<CPolygon>{ typedef polygon_concept type; };

  template <>
  struct polygon_traits<CPolygon> {
    typedef int coordinate_type;
    typedef CPolygon::const_iterator iterator_type;
    typedef CPoint point_type;


    static inline iterator_type begin_points(const CPolygon& t) {
      return t.begin();
    }

    static inline iterator_type end_points(const CPolygon& t) {
      return t.end();
    }


    static inline std::size_t size(const CPolygon& t) {
      return t.size();
    }


    static inline winding_direction winding(const CPolygon& t) {
      return clockwise_winding;
    }
  };

  template <>
  struct polygon_mutable_traits<CPolygon> {
      template <typename iT>
      static inline CPolygon& set_points(CPolygon& t,
                                       iT input_begin, iT input_end) {
        t.clear();
        t.insert(t.end(), input_begin, input_end);
        return t;
      }

    };
  } 
}



int main() {
  test_polygon<CPolygon>();
  return 0;
}

I get size = 0 in the result vector of intersections.

Answer 1

gtl::set_points(poly, pts, pts + 5);

That's out of bounds, because the array has only 4 elements. Avoid the entire bug category by modernizing:

std::array const pts1{
    gtl::construct<Point>(6, 0),
    gtl::construct<Point>(0, 6),
    gtl::construct<Point>(-6, 0),
    gtl::construct<Point>(0, -6),
};

std::array const pts2{
    gtl::construct<Point>(4, 0),
    gtl::construct<Point>(4, 4),
    gtl::construct<Point>(0, 4),
    gtl::construct<Point>(0, 0),
};

And then

Polygon poly1;
gtl::set_points(poly1, pts1.begin(), pts1.end());

Polygon poly2;
gtl::set_points(poly2, pts2.begin(), pts2.end());

Next up you have:

static inline winding_direction winding(const CPolygon& t)
{
    return clockwise_winding;
}

But your sample data does not conform to that winding. Fixing your input data:

std::array const pts1{
    gtl::construct<Point>(0, -6),
    gtl::construct<Point>(-6, 0),
    gtl::construct<Point>(0, 6),
    gtl::construct<Point>(6, 0),
};

std::array const pts2{
    gtl::construct<Point>(0, 0),
    gtl::construct<Point>(0, 4),
    gtl::construct<Point>(4, 4),
    gtl::construct<Point>(4, 0),
};

Finally, the result of operators in Boost Polygon is a polygon set view. You can have the library assign that:

std::vector<Polygon> res;
gtl::assign(res, poly1 & poly2);

Or

std::vector<Polygon> res{poly1};
res &= poly2;

Which are both effectively equivalent, though the second might be more efficient?

fmt::print("poly1 {}, area {}\n", poly1, gtl::area(poly1));
fmt::print("poly2 {}, area {}\n", poly2, gtl::area(poly2));

fmt::print("res {}, area {}\n", res, gtl::area(res));

Prints

Live On Compiler Explorer

poly1 [(0, -6), (-6, 0), (0, 6), (6, 0)], area 72
poly2 [(0, 0), (0, 4), (4, 4), (4, 0)], area 16
res [[(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)]], area 0

Fixing The Area

The only thing I see now is the winding on the result set is still wrong.

This is, no doubt, the reason that area(res) fails. We can show by changing the winding to counter-clockwise (and the sample data too of course):

Live On Compiler Explorer

poly1 {(6, 0), (0, 6), (-6, 0), (0, -6)}, area 72
poly2 {(4, 0), (4, 4), (0, 4), (0, 0)}, area 16
res {{(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)}}, area 14

Perhaps you wanted counter-clockwise after all (considering the test data), or perhaps another trait is needed to tell the library the winding for vector<CPolygon> as a polygon set.

Fixing The Constructor Issue

Going up the call-chain in the compiler error when the constructor is removed, we see

  polygon_set_mutable_traits<polygon_set_type_1>::set(lvalue, ps.begin(), ps.end());

This seems to confirm the hunch above: You are missing the traits for the polygon set. However, adding some

template <> struct polygon_set_traits<std::vector<CPolygon> > {
    using C               = std::vector<CPolygon>;
    using iterator_type   = C::const_iterator;
    using coordinate_type = polygon_traits<CPolygon>::coordinate_type;

    static iterator_type begin(C const& c)  { return c.begin(); }
    static iterator_type end(C const& c)  { return c.end(); }
    static bool clean(C const& c) { return c.empty(); }
};

template <> struct polygon_set_mutable_traits<std::vector<CPolygon> > {
    using C               = std::vector<CPolygon>;
    using iterator_type   = C::iterator;
    using coordinate_type = polygon_set_traits<C>::coordinate_type;

    static iterator_type begin(C& c)  { return c.begin(); }
    static iterator_type end(C& c)  { return c.end(); }

    template <typename II>
    static inline void set(C& c, II input_begin, II input_end)
    {
        c.clear();
        size_t num_ele = std::distance(input_begin, input_end);
        c.reserve(num_ele);
        polygon_set_data<coordinate_type> ps;
        ps.reserve(num_ele);
        ps.insert(input_begin, input_end);
        ps.get(c);
    }
};

results in the same since ps.get ends up doing a complicated formation on an "arbitrary formation" to get the "fractured" polygon set (ugh, I don't know what all these things mean) and inside an event processor it ends-up just calling your existing polygon_mutable_traits::set_points. I had already simplified your implementation:

template <typename I>
static inline CPolygon& set_points(CPolygon& t, I f, I l)
{
    t.assign(f, l);
    return t;
}

However, clearly the assumption that decltype(*I) would be CPoint was just an error. Fixing it:

template <> struct polygon_mutable_traits<CPolygon> {
    template <typename I>
    static inline CPolygon& set_points(CPolygon& p, I f, I l)
    {
        p.clear();
        for (; f != l; ++f)
            p.push_back({get(*f, HORIZONTAL), get(*f, VERTICAL)});
        return p;
    }
};

Now "everything just works"

Complete Demo

Also reverting the test to generic template and ordered before all the types/traits:

Live On Compiler Explorer

#include <boost/polygon/polygon.hpp>
#include <cassert>
#include <fmt/ostream.h>
#include <fmt/ranges.h>
#include <list>
namespace gtl = boost::polygon;
using namespace gtl::operators;

template <typename Polygon> void test_polygon()
{
    using Point = typename gtl::polygon_traits<Polygon>::point_type;

    std::array const pts1{
        gtl::construct<Point>(6, 0),
        gtl::construct<Point>(0, 6),
        gtl::construct<Point>(-6, 0),
        gtl::construct<Point>(0, -6),
    };

    std::array const pts2{
        gtl::construct<Point>(4, 0),
        gtl::construct<Point>(4, 4),
        gtl::construct<Point>(0, 4),
        gtl::construct<Point>(0, 0),
    };

    Polygon poly1;
    gtl::set_points(poly1, pts1.begin(), pts1.end());

    Polygon poly2;
    gtl::set_points(poly2, pts2.begin(), pts2.end());

#if 1
    std::vector<Polygon> res;
    gtl::assign(res, poly1 & poly2);
#else
    std::vector<Polygon> res{poly1};
    res &= poly2;
#endif
    fmt::print("poly1 {}, area {}\n", poly1, gtl::area(poly1));
    fmt::print("poly2 {}, area {}\n", poly2, gtl::area(poly2));

    fmt::print("res {}, area {}\n", res, gtl::area(res));
}

struct CPoint {
    int x;
    int y;

    friend std::ostream& operator<<(std::ostream& os, CPoint const& cp) {
        return os << "(" << cp.x << ", " << cp.y << ")";
    }
};

namespace boost::polygon {
    template <> struct geometry_concept<CPoint> {
        using type = point_concept;
    };

    template <> struct point_traits<CPoint> {
        using coordinate_type = int;

        static inline coordinate_type get(const CPoint&  point,
                                          orientation_2d orient)
        {
            return orient == HORIZONTAL ? point.x : point.y;
        }
    };

    template <> struct point_mutable_traits<CPoint> {
        using coordinate_type = int;

        static inline void set(CPoint& point, orientation_2d orient, int value)
        {
            if (orient == HORIZONTAL) {
                point.x = value;
            } else {
                point.y = value;
            }
        }
        static inline CPoint construct(int x_value, int y_value)
        {
            return CPoint{x_value, y_value};
        }
    };
} // namespace boost::polygon

using CPolygon = std::list<CPoint>;

namespace boost::polygon {

    template <> struct geometry_concept<CPolygon> {
        using type = polygon_concept;
    };

    template <> struct polygon_traits<CPolygon> {
        using iterator_type   = CPolygon::const_iterator;
        using point_type      = CPoint;
        using coordinate_type = typename point_traits<point_type>::coordinate_type;

        static inline iterator_type begin_points(const CPolygon& t)
        {
            return t.begin();
        }

        static inline iterator_type end_points(const CPolygon& t)
        {
            return t.end();
        }

        static inline std::size_t size(const CPolygon& t) { return t.size(); }

        static inline winding_direction winding(const CPolygon& t)
        {
            return counterclockwise_winding;
        }
    };

    template <> struct polygon_mutable_traits<CPolygon> {
        template <typename I>
        static inline CPolygon& set_points(CPolygon& p, I f, I l)
        {
            p.clear();
            for (; f != l; ++f)
                p.push_back({get(*f, HORIZONTAL), get(*f, VERTICAL)});
            return p;
        }
    };

} // namespace boost::polygon

int main()
{
    test_polygon<CPolygon>();
}

Prints

poly1 {(6, 0), (0, 6), (-6, 0), (0, -6)}, area 72
poly2 {(4, 0), (4, 4), (0, 4), (0, 0)}, area 16
res {{(4, 2), (2, 4), (0, 4), (0, 0), (4, 0), (4, 2)}}, area 14

Which matches the schematic: