多边形在C++

Question

假设我有在2D空间中的多个多边形如下面的图像示出了：

每个多边形与一个表示X-Y坐标的列表。例如，多边形A可以写成PolygonA：{（3,4），（7,8），...，（3,4）}。所有的多边形生成后，我们想对它们执行一些操作。例如，我们想知道矩形框内的所有多边形。或者对于某个多边形，我们想知道它的相邻多边形。这里是我的问题：我如何组织数据结构，以便多边形上的操作变得更加简单和高效。最直接的方法是将所有多边形放入矢量容器中。但是对它们的操作变得效率低下。关于正确的数据结构或库的任何想法？

Answer 1

现在，这只是一个提示！ 我会做一个不同的方式。它（正如你已经说过的）方式太不能操作整个多边形。经常使用的帮助是将多边形分成更小（更容易计算）的形状。

假设你有一个多边形。

再次，与每个单一坐标操作..没办法。 假设您有一个算法根据“强度因子”返回多个形状。它可能看起来像这样。

std::vector<Shape> fill_with_shapes(const Polygon &a, float intensity); //example 

并且强度越大，越详细。

和（如果你想要的话）甚至更多。

矩形和三角形的计算比整个多边形更简单。现在，我没有这样一个'fill_with_shapes'函数的代码，再次，这个答案更多的是建议之前你做任何操作 ..我希望这个想法有帮助！

Answer 2

我认为从boost :: geometry库中使用r-tree似乎是一个很好的解决方案。我发布的代码如下：

#include<stdio.h> 

#include <boost/geometry.hpp> 
#include <boost/geometry/extensions/index/rtree/rtree.hpp> 
#include <vector> 


#include <boost/geometry.hpp> 
#include <boost/geometry/extensions/index/rtree/rtree.hpp> 

#include <random> 

#include <iostream> 
#include <exception> 
#include <boost/foreach.hpp> 

int main(void) 
{ 
    namespace bg = boost::geometry; 
    namespace bgi = boost::geometry::index; 

    typedef bg::model::point<float,2,bg::cs::cartesian> point; 
    typedef bg::model::box<point> box; 

    typedef bgi::rtree<box,unsigned > rtreeType; 

    rtreeType rtree(6,3); 

    for(unsigned i=0; i<10; i++) 
    { 
     box b(point(i+0.1f,i+0.1f),point(i+0.5f,i+0.5f)); 
     rtree.insert(b,i); 
    } 

    box query_box(point(0,0),point(5,5)); 

    rtree.print(); 

    std::cout<<"number of elements: "; 
    std::cout<<rtree.elements()<<std::endl; 


    // application 1: search for boxes that are within query_box 
    std::deque<unsigned> &boxValue=rtree.find(query_box); 





    return 0; 
}