为什么我没有得到这些多边形的任何交集？

Question

我学习了如何将 boost::polygon 库与自定义多边形结合使用。我举了一个使用自定义多边形的例子，并试图获得这些多边形的交集。我没有任何交集，也不明白为什么。另外，你可以看到这个构造函数

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

没有它我无法编译我的程序。有人可以解释一下，为什么我需要它？我做错了什么？

/*
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;
}

我在交叉点的结果向量中得到 size = 0。

Answer 1

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

这超出了范围，因为数组只有 4 个元素。通过现代化避免整个错误类别：

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());

接下来你有：

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

但是你的样本数据不符合那个绕组。修复您的输入数据：

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),
};

最后，Boost Polygon 中运算符的结果是一个多边形集合视图。您可以让图书馆分配：

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

或

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

两者在效果上是等价的，但第二个可能更有效？

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));

版画

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

修复区域

现在只看到结果集上的缠绕还是错的

毫无疑问，这就是 area(res) 失败的原因。我们可以通过将绕组更改为逆时针（当然还有示例数据）来显示：

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

也许您毕竟想要逆时针旋转（考虑到测试数据），或者可能需要另一个特征来告诉库 vector<CPolygon> 作为多边形集的绕组。

修复构造函数问题

在删除构造函数时在编译器错误中向上调用链，我们看到

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

这似乎证实了上面的预感：您缺少多边形集的特征。但是，添加一些

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);
    }
};

结果相同，因为 ps.get 最终在“任意编队”上做了一个复杂的编队以获得“破碎的”多边形集（呃，我不知道所有这些东西是什么意思）和在事件处理器中，它最终只是调用您现有的 polygon_mutable_traits::set_points。我已经简化了你的实现：

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

然而，显然 decltype(*I) 将是 CPoint 的假设只是一个错误。修复它：

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;
    }
};

现在“一切正常”

完成演示

还将测试还原为通用模板并在所有 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>();
}

版画

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

原理图匹配：

为什么我没有得到这些多边形的任何交集？

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

c++

math

boost

boost-polygon

修复区域

修复构造函数问题

完成演示