在循环中重复使用boost :: geometry :: intersection

Question

我有一个基础多边形B和许多其他多边形p_0, p_1, p_2, ...，每个都有一个重量w_0, w_1, w_2, ...。

我想要：

• 计算B和p_0的交叉区域，并将该区域乘以w_0。
• 差异B和p_0形成一个新的多边形B_1，这是B与p_0切出来的。
• 计算B_1和p_1的交叉区域，并将该区域乘以w_1。
• 差异B_1和p_1形成一个新的多边形B_2，这是B_1与p_1切出来的。
• 等等...

我试图使用boost :: polygon库来做到这一点。他们有一个如何做交叉点here和差异here的例子。

交点函数定义如下：

bool intersection(Geometry1 const & geometry1, Geometry2 const & geometry2, GeometryOut & geometry_out)

为了在循环中使用intersection，并测量区域，我想我需要将GeometryOut类型转换为Geometry1类型。目前尚不清楚如何做到这一点。

到目前为止，我的代码的缩减版本是：

#include <boost/polygon/polygon.hpp>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/multi/geometries/multi_polygon.hpp>
#include <iostream>
#include <vector>
#include <cstdlib>
namespace gtl = boost::polygon;

typedef gtl::polygon_data<float> Polygon;

Polygon MakeBox(float xmin, float ymin, float xmax, float ymax){
  typedef gtl::polygon_traits<Polygon>::point_type Point;
  Point pts[] = {
    gtl::construct<Point>(xmin, ymin),
    gtl::construct<Point>(xmin, ymax),
    gtl::construct<Point>(xmax, ymax),
    gtl::construct<Point>(xmax, ymin)
  };
  Polygon poly;
  gtl::set_points(poly, pts, pts+4);

  return poly;
}

double GetValue(const Polygon &base, const std::vector<Polygon> &polys, const std::vector<double> &vals){
  double value     = 0;
  double base_area = gtl::area(base);
  boost::geometry::model::multi_polygon<Polygon> multipoly, isect, multipolynew;
  //I've also tried the following line in place of the line above: doesn't work.
  //std::deque<Polygon> multipoly, isect, multipolynew;
  multipoly.push_back(base);

  for(int i=0;i<polys.size();i++){
    boost::geometry::intersection(multipoly, polys[i], isect);
    value    += gtl::area(isect)/base_area*vals[i];
    boost::geometry::difference(multipoly,polys[i],multipolynew);
    multipoly = multipolynew;
  }

  return value;
}

int main() {
  Polygon base = MakeBox(0,0,10,10); //Base polygon
  std::vector<Polygon> polys;
  std::vector<double>  vals;
  //Set up some random input
  for(int i=0;i<3;i++){
    int xmin=rand()%10;
    int xmax=xmin+rand()%10;
    int ymin=rand()%10;
    int ymax=ymin+rand()%10;
    polys.push_back(MakeBox(xmin,ymin,xmax,ymax));
    vals.push_back(rand()%100);
  }
  std::cout<<GetValue(base,polys,vals)<<std::endl;
}

Answer 1

从各个角度来看这个我会得出结论，这是Boost Geometry adaptation of Boost Polygon types的限制。

即使用Boost Polygon（boost::polygon_data<>）更全功能的多边形概念实现替换“vanilla”环类型（boost::polygon_with_holes_data<>），也不允许在boost::geometry::multi_poygon<T>实例化中使用自适应的Polygon。

如果您有兴趣，我会在搜索过程中发现更多信息：

1. 使用Boost Geometry模型而不是Boost Polygon类型时，您可以执行所需的操作。将multi_polygon直接用作Geometry是没有问题的： Live On Coliru

   #include <fstream>
   #include <boost/geometry/geometry.hpp>
   #include <boost/geometry/io/io.hpp>
   #include <boost/geometry/geometries/geometries.hpp>
   #include <boost/geometry/geometries/point_xy.hpp>
   #include <boost/foreach.hpp>
   
   typedef boost::geometry::model::d2::point_xy<double> PointType;
   using Polygon = boost::geometry::model::polygon<PointType>;
   
   Polygon MakeBox(float xmin, float ymin, float xmax, float ymax){
       Polygon poly;
       poly.outer().assign({
           {xmin, ymin},
           {xmin, ymax},
           {xmax, ymax},
           {xmax, ymin}
       });
       return poly;
   }
   
   double GetValue(const Polygon &base, const std::vector<Polygon> &polys, const std::vector<double> &vals){
       double value     = 0;
       double base_area = boost::geometry::area(base);
   
       boost::geometry::model::multi_polygon<Polygon> multipoly, isect, multipolynew;
       multipoly.push_back(base);
   
       for(size_t i=0;i<polys.size();i++){
           boost::geometry::intersection(multipoly, polys[i], isect);
   
           value += boost::geometry::area(isect)/base_area*vals[i];
           boost::geometry::difference(multipoly,polys[i],multipolynew);
   
           multipoly = multipolynew;
       }
   
       return value;
   }
   
   int main()
   {
       Polygon base = MakeBox(0,0,10,10); //Base polygon
       std::vector<Polygon> polys;
       std::vector<double>  vals;
       //Set up some random input
       for(int i=0;i<3;i++){
           int xmin=rand()%10;
           int xmax=xmin+rand()%10;
           int ymin=rand()%10;
           int ymax=ymin+rand()%10;
           polys.push_back(MakeBox(xmin,ymin,xmax,ymax));
           vals.push_back(rand()%100);
       }
       std::cout<<GetValue(base,polys,vals)<<std::endl;
   }

2. 或者，您可以实现相交的O（n log n）访问版本，该版本与多边形的两个集合（例如矢量）相交，即使它们不是单个几何。 这个邮件列表精确地交换了这个http://boost-geometry.203548.n3.nabble.com/intersection-of-two-vectors-of-polygons-tp2875513p2880997.html的详细信息（尽管这里的用例是这样的，单个多边形可以与ids难以处理的独特信息位（multi_polygons）相关联）。 以下是对交叉点起作用的代码的简化修改。我想你需要为difference调用（？）做类似的方法。我将把它作为读者的练习。 Live On Coliru 另一个相关的主题可能是http://boost-geometry.203548.n3.nabble.com/Unioning-many-polygons-td3405482.html