使用Boost.Polygon切片曼哈頓多邊形

我無法使用Boost.Polygon中的get_rectangles(output_container_type& output, const T& polygon_set)方法將曼哈頓（直線）多邊形切片爲矩形。它似乎不適用於自相交多邊形，例如下面的多邊形。使用Boost.Polygon切片曼哈頓多邊形

這裏是我的嘗試：

#include <iostream> 
#include <boost/polygon/polygon.hpp> 
#include <vector> 

namespace gtl = boost::polygon; 
using namespace boost::polygon::operators; 

int main() { 
    typedef gtl::polygon_90_with_holes_data<int> Polygon; 
    typedef gtl::polygon_traits<Polygon>::point_type Point; 

    Point pts[] = {gtl::construct<Point>(0, 0), // See the image 
    gtl::construct<Point>(0, 10), 
    gtl::construct<Point>(30, 10), 
    gtl::construct<Point>(30, 20), 
    gtl::construct<Point>(10, 20), 
    gtl::construct<Point>(10, 0)}; 

    Polygon poly; 
    gtl::set_points(poly, pts, pts+6); 

    std::vector< gtl::rectangle_data<int> > rects; 
    get_rectangles(rects, poly); 

    std::cout << rects.size() << " rectangle: \n"; 

    for(std::vector<gtl::rectangle_data<int> >::iterator it = rects.begin(); it !=      
     rects.end(); ++it) { 
      // Print out the corner coordinates 
      std::cout << "x1: "<< gtl::xl(*it) << ", x2: " << gtl::xh(*it) 
      << ", y1: "<< gtl::yl(*it) << ", y2: " << gtl::yh(*it) << std::endl; 
    } 
    return 0; 
}

而這裏的輸出：

1 rectangle: 
    x1: 10, x2: 30, y1: 10, y2: 20

此方法處理爲一個不相交的多邊形，但在這裏它只能產生一個矩形，不是兩個。 This似乎表明我正在嘗試做的事情應該是可能的。我做錯了什麼，或者這是可能的？

來源

2014-06-05 user21760

您的代碼是「壓力測試」多邊形代碼。嚴格地說，你的點列表沒有定義多邊形。理論上，平面區域（特別是多邊形形狀）僅由形成周邊的所謂喬丹（簡單）曲線很好地定義。用最簡單的術語來說，喬丹（簡單）曲線不能交叉。

當相同的形狀使用具有8個點的下面的列表約旦（簡單）曲線重新定義，

Point pts[] = {gtl::construct<Point>(0, 0), 
gtl::construct<Point>(0, 10), 
gtl::construct<Point>(10, 10),  
gtl::construct<Point>(10, 20), 
gtl::construct<Point>(30, 20), 
gtl::construct<Point>(30, 10), 
gtl::construct<Point>(10, 10), 
gtl::construct<Point>(10, 0)};

代碼產生正確的結果：

2矩形： X1：0 ，x2：10，y1：0，y2：10 x1：10，x2：30，y1：10，y2：20

來源

2014-07-01 21:20:33 Melody

使用Boost.Polygon切片曼哈頓多邊形

回答

相關問題