c++ - Boost union 在 1.67 中不起作用，但在 1.61 中起作用。为什么？

Question

我想弄明白为什么我的下面的代码在 boost 1.61 中按预期工作，但在 boost 1.67 中却没有。

在 boost 1.61 中，输入多边形正确组合并显示轮廓多边形。

在 boost 1.67 中，没有更改代码，轮廓多边形是错误且不完整的。好像缺了点。

添加输出图像以帮助解释。还有一个 #define BOOST_1_6_1 我需要添加，因为 boost 1.61 似乎不会自动添加该头文件。

如果您想查看输入多边形的外观，请取消注释 drawAllPolygons()。

有人可以帮忙吗？

#include <iostream>


#include <boost\geometry.hpp>

//#define BOOST_1_6_1
#ifdef BOOST_1_6_1
#include <boost/geometry/geometries/point_xy.hpp>
#endif

typedef boost::geometry::model::d2::point_xy<int> intPt;
typedef boost::geometry::model::polygon<intPt> polygon;

const int GRID_WIDTH = 220;
const int GRID_HEIGHT = 60;

bool canvas[GRID_WIDTH][GRID_HEIGHT];

std::vector<polygon> output;
std::vector<polygon> input;

void initCanvas()
{
    for (unsigned int y = 0; y < GRID_HEIGHT; ++y)
    {
        for (unsigned int x = 0; x < GRID_WIDTH; ++x)
        {
            canvas[x][y] = false;
        }
    }
}

void drawGrid()
{
    for (unsigned int y = 0; y < GRID_HEIGHT; ++y)
    {
        for (unsigned int x = 0; x < GRID_WIDTH; ++x)
        {
            if (canvas[x][y])
            {
                std::cout << "x";
            } 
            else
            {
                std::cout << ".";
            }
        }

        std::cout << std::endl;
    }
}

polygon setupPolygon(const int startX, const int startY, const int width, const int height)
{
    polygon polygon1;

    int endX = startX + width;
    int endY = startY + height;

    for (int x = startX; x <= endX; ++x)
    {
        intPt pt(x, startY);
        polygon1.outer().push_back(pt);
    }

    for (int y = startY; y <= endY; ++y)
    {
        intPt pt(endX, y);
        polygon1.outer().push_back(pt);
    }

    for (int x = endX; x >= startX; --x)
    {
        intPt pt(x, endY);
        polygon1.outer().push_back(pt);
    }

    for (int y = endY; y >= startY; --y)
    {
        intPt pt(startX, y);
        polygon1.outer().push_back(pt);
    }

    return polygon1;
}

std::vector<polygon> combine(std::vector<polygon> input)
{
    bool loop = true;
    while (loop)
    {
        unsigned int before = input.size();
        bool exit = false;
        for (unsigned int i = 0; i < input.size() && !exit; ++i)
        {
            for (unsigned int j = i + 1; j < input.size() && !exit; ++j)
            {
                std::vector<polygon> output;
                boost::geometry::correct(input[i]);
                boost::geometry::correct(input[j]);
                boost::geometry::union_(input[i], input[j], output);

                if (i < j)
                { 
                    input.erase(input.begin() + j);
                    input.erase(input.begin() + i);
                }
                else
                {
                    input.erase(input.begin() + i);
                    input.erase(input.begin() + j);
                }

                input.insert(input.begin(), output.begin(), output.end());

                exit = true;
            }
        }

        if (before == input.size())
        {
            loop = false;
        }
    }


    return input;
}

void drawAllPolygons()
{
    for (unsigned int i = 0; i < input.size(); ++i)
    {
        auto outer = input[i].outer();
        for (unsigned int i = 0; i < outer.size(); ++i)
        {
            int x = outer[i].get<0>();
            int y = outer[i].get<1>();
            canvas[x][y] = true;
        }
    }
}

void drawCombinedPolygons()
{
    for (unsigned int j = 0; j < output.size(); ++j)
    {
        auto outer = output[j].outer();
        for (unsigned int i = 0; i < outer.size(); ++i)
        {
            int x = outer[i].get<0>();
            int y = outer[i].get<1>();
            canvas[x][y] = true;
        }
    }
}

int main()
{
    initCanvas();

    input.push_back(setupPolygon(40, 10, 50, 15));
    input.push_back(setupPolygon(40, 20, 50, 15));
    input.push_back(setupPolygon(50, 10, 50, 15));
    input.push_back(setupPolygon(60, 30, 50, 15));

    output = combine(input);

    //drawAllPolygons();
    drawCombinedPolygons();

    drawGrid();

    std::cin.get();

    return 0;
}

Answer 1

Boost 1.61 显然没有做所有可能的优化。

---

有很多误解。

1. 输入多边形(环)的方向错误。您可以使用 is_valid 和 correct 帮助自己。下面的代码将显示它。

2. 明确创建原始多边形以包含许多冗余点。即使您只是将其中一个与自己“union ”，您也可以预期结果会得到简化:

   Live On Coliru

   polygon p = setupPolygon(40, 10, 50, 15);
   std::cout << "original: " << bg::wkt(p) << "\n";
   multi_polygon simple;
   bg::union_(p, p, simple);
   std::cout << "self-union: " << bg::wkt(simple) << "\n";
   

   会打印

   original: POLYGON((40 10,40 11,40 12,40 13,40 14,40 15,40 16,40 17,40 18,40 19,40 20,40 21,40 22,40 23,40 24,40 25,40 25,41 25,42 25,43 25,44 25,45 25,46 25,47 25,48 25,49 25,50 25,51 25,52 25,53 25,54 25,55 25,56 25,57 25,58 25,59 25,60 25,61 25,62 25,63 25,64 25,65 25,66 25,67 25,68 25,69 25,70 25,71 25,72 25,73 25,74 25,75 25,76 25,77 25,78 25,79 25,80 25,81 25,82 25,83 25,84 25,85 25,86 25,87 25,88 25,89 25,90 25,90 25,90 24,90 23,90 22,90 21,90 20,90 19,90 18,90 17,90 16,90 15,90 14,90 13,90 12,90 11,90 10,90 10,89 10,88 10,87 10,86 10,85 10,84 10,83 10,82 10,81 10,80 10,79 10,78 10,77 10,76 10,75 10,74 10,73 10,72 10,71 10,70 10,69 10,68 10,67 10,66 10,65 10,64 10,63 10,62 10,61 10,60 10,59 10,58 10,57 10,56 10,55 10,54 10,53 10,52 10,51 10,50 10,49 10,48 10,47 10,46 10,45 10,44 10,43 10,42 10,41 10,40 10))
   self-union: MULTIPOLYGON(((90 25,90 10,40 10,40 25,90 25)))
   

   如您所见，结果将简化为仅矩形的明显角。但是，您的“绘图”代码依赖于存在的冗余点。

   这就是您最终得到“参差不齐”结果的原因 - 似乎遗漏了点，只是因为您的绘图代码没有绘制任何线条。它只是绘制(角)点。

3. canvas 维度是倒置的

   我认为您的canvas 索引一直在交换。我建议使用带有(可选)边界检查的更明确的数据结构来避免这种情况。

改为使用 SVG

如果你把代码改成输出输入和输出的SVG，你会发现整件事情非常合理。请注意，这还需要注意更正输入:

Live On Coliru

#include <iostream>
#include <fstream>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

namespace bg = boost::geometry;
typedef bg::model::d2::point_xy<int> intPt;
typedef bg::model::polygon<intPt> polygon;
typedef bg::model::multi_polygon<polygon> multi_polygon;

const int GRID_WIDTH = 220;
const int GRID_HEIGHT = 60;

std::array<std::array<bool, GRID_WIDTH>, GRID_HEIGHT> canvas;

void initCanvas() {
    for (auto& row : canvas)
        for (auto& cell : row)
            cell = false;
}

void drawGrid() {
    for (auto& row : canvas) {
        for (auto& cell : row)
            std::cout << (cell?"x":".");
        std::cout << std::endl;
    }
}

template <typename R> void valid(R& g) {
    std::string reason;
    while (!bg::is_valid(g, reason)) {
        std::cout << "Not valid: " << reason << "\n";
        bg::correct(g);
    }
}

polygon setupPolygon(const int startX, const int startY, const int width, const int height) {
    polygon::ring_type r;

    int const endX = startX + width;
    int const endY = startY + height;

    for (int x = startX; x <= endX;   ++x) r.emplace_back(x,      startY);
    for (int y = startY; y <= endY;   ++y) r.emplace_back(endX,   y);
    for (int x = endX;   x >= startX; --x) r.emplace_back(x,      endY);
    for (int y = endY;   y >= startY; --y) r.emplace_back(startX, y);

    valid(r);

    return {r};
}

template <typename Polygons>
multi_polygon combine(Polygons const& input) {

    if (input.empty()) return {};
    //if (input.size()<2) return {input.front()};

    multi_polygon out;
    for (polygon const& i : input) {
        multi_polygon tmp;
        bg::union_(out, i, tmp);
        out = tmp;
    }

    return out;
}

void draw(polygon const& p) {
    for (auto& pt : p.outer())
        canvas.at(pt.y()).at(pt.x()) = true;
}

void draw(multi_polygon const& mp) { for (auto& p : mp) draw(p); }
void draw(std::vector<polygon> const& mp) { for (auto& p : mp) draw(p); }

void writeSvg(multi_polygon const& g, std::string fname) {
    std::ofstream svg(fname);
    boost::geometry::svg_mapper<intPt> mapper(svg, 400, 400);
    mapper.add(g);
    mapper.map(g, "fill-opacity:0.5;fill:rgb(0,0,153);stroke:rgb(0,0,200);stroke-width:2");
}

void writeSvg(std::vector<polygon> const& g, std::string fname) {
    std::ofstream svg(fname);
    boost::geometry::svg_mapper<intPt> mapper(svg, 400, 400);
    for (auto& p: g) {
        mapper.add(p);
        mapper.map(p, "fill-opacity:0.5;fill:rgb(153,0,0);stroke:rgb(200,0,0);stroke-width:2");
    }
}

int main() {
    std::vector<polygon> input { {
        setupPolygon(40, 10, 50, 15),
        setupPolygon(40, 20, 50, 15),
        setupPolygon(50, 10, 50, 15),
        setupPolygon(60, 30, 50, 15),
    } };

    for (auto& p : input)
        valid(p);

    auto output = combine(input);

    initCanvas();
    draw(input);
    drawGrid();

    initCanvas();
    draw(output);
    drawGrid();

    writeSvg(input, "input.svg");
    writeSvg(output, "output.svg");
}

打印

Not valid: Geometry has wrong orientation
Not valid: Geometry has wrong orientation
Not valid: Geometry has wrong orientation
Not valid: Geometry has wrong orientation
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
........................................xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.......................................................................................................................
........................................x.........x.......................................x.........x.......................................................................................................................
........................................x.........x.......................................x.........x.......................................................................................................................
........................................x.........x.......................................x.........x.......................................................................................................................
[ snip ]
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................
............................................................................................................................................................................................................................

和input.svg:

和输出.svg: