2

我无法使用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

此方法适用于不相交的多边形，但在这里它只产生一个矩形，而不是两个。这似乎表明我正在尝试做的事情应该是可能的。我做错了什么，或者这可能吗？

4

1 回答 1

3

您的代码正在“压力测试”多边形代码。严格来说，您的点列表没有定义多边形。理论上，平面区域（特别是多边形）仅由形成周长的所谓 Jordan（简单）曲线很好地定义。用最简单的术语来说，乔丹（简单）曲线不能与自身相交。

当使用具有以下 8 个点列表的 Jordan（简单）曲线重新定义相同的形状时，

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-01T21:20:33.203 回答