2

次のような、指定された整数 (1 から INT_MAX までの任意の値) の行列があります。

1 2 3
1 3 3
1 3 3
100 2 1

マトリックス内の一意の int ごとに同じ色のポリゴンを作成して、ここに示すような座標/グループをポリゴンに持たせたいと考えています。

ここに画像の説明を入力

次のような画像を生成できます。

ここに画像の説明を入力

どの *(実行された vectirisation のため、次のようなサイズにスケーリングされます):

ここに画像の説明を入力(下手な絵でごめんなさい)

ブーストジオメトリでそのようなことを行う方法はありますか?

アップデート：

だから@sehe悲しい：純粋にBoost.Geometryを使用してI'd simply let Boost Geometry do most of the work.このピクセル単位のクラスのaeria growerを作成し、コンパイルして実行しますが、クラスター化されたデータで実行する必要があります..そして、1000 x 1800のucharファイルがあります（それぞれの一意のuchar ==データはそのクラスターに属します)。このコードの問題: 18 行目で、各ポイントの作成に 1 秒以上かかるほど非常に遅くなります =(

コード：

//Boost
#include <boost/assign.hpp>
#include <boost/foreach.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/algorithm/string.hpp>

#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/multi/geometries/multi_polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>

//and this is why we use Boost Geometry from Boost trunk 
//#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>

BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)


void make_point(int x, int y,  boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > & ring)
{
    using namespace boost::assign;

    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x-1, y-1));
    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x, y-1));
    boost::geometry::append(  ring,      boost::geometry::model::d2::point_xy<double>(x, y));
    boost::geometry::append(  ring,      boost::geometry::model::d2::point_xy<double>(x-1, y));
    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x-1, y-1));
    boost::geometry::correct(ring);
}

void create_point(int x, int y, boost::geometry::model::multi_polygon< boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > > & mp)
{
    boost::geometry::model::multi_polygon< boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > > temp;
    boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > ring;
    make_point(x, y, ring);
    boost::geometry::union_(mp, ring, temp);
    boost::geometry::correct(temp);
    mp=temp;
}

int main()
{
    using namespace boost::assign;


    boost::geometry::model::multi_polygon< boost::geometry::model::polygon < boost::geometry::model::d2::point_xy<double> > > pol, simpl;

    //read image
    std::ifstream in("1.mask", std::ios_base::in | std::ios_base::binary);
    int sx, sy;
    in.read(reinterpret_cast<char*>(&sy), sizeof(int));
    in.read(reinterpret_cast<char*>(&sx), sizeof(int));
    std::vector< std::vector<unsigned char> > image(sy);

    for(int i =1; i <= sy; i++)
    {
        std::vector<unsigned char> row(sx);
        in.read(reinterpret_cast<char*>(&row[0]), sx);
        image[i-1] = row;
    }

    //
    std::map<unsigned char,  boost::geometry::model::multi_polygon < boost::geometry::model::polygon < boost::geometry::model::d2::point_xy<double> > >  > layered_image;

    for(int y=1; y <= sy; y++)
    {
        for(int x=1; x <= sx; x++)
        {
            if (image[y-1][x-1] != 1)
            {
                create_point(x, y, layered_image[image[y-1][x-1]]);
                std::cout << x << " : " << y << std::endl;
            }
        }
    }
}

あなたが私のコードを見てわかるように..それで私は@seheコードのレンダラーを作成することにしました：

#include <iostream>
#include <fstream>

#include <vector>
#include <string>
#include <set>

//Boost
#include <boost/assign.hpp>
#include <boost/array.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/multi/geometries/multi_polygon.hpp>
#include <boost/geometry/geometries/adapted/boost_tuple.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/mersenne_twister.hpp>


//and this is why we use Boost Geometry from Boost trunk 
#include <boost/geometry/extensions/io/svg/svg_mapper.hpp>

BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)

    namespace mxdetail
{
    typedef size_t cell_id; // row * COLS + col

    template <typename T> struct area
    {
        T value;
        typedef std::vector<cell_id> cells_t;
        cells_t cells;
    };

    template <typename T, size_t Rows, size_t Cols>
    std::vector<area<T> > getareas(const boost::array<boost::array<T, Cols>, Rows>& matrix)
    {
        typedef boost::array<boost::array<T, Cols>, Rows> mtx;
        std::vector<area<T> > areas;

        struct visitor_t
        {
            const mtx& matrix;
            std::set<cell_id> visited;

            visitor_t(const mtx& mtx) : matrix(mtx) { }

            area<T> start(const int row, const int col)
            {
                area<T> result;
                visit(row, col, result);
                return result;
            }

            void visit(const int row, const int col, area<T>& current)
            {
                const cell_id id = row*Cols+col;
                if (visited.end() != visited.find(id))
                    return;

                bool matches = current.cells.empty() || (matrix[row][col] == current.value);

                if (matches)
                {
                    visited.insert(id);
                    current.value = matrix[row][col];
                    current.cells.push_back(id);

                    // process neighbours
                    for (int nrow=std::max(0, row-1); nrow < std::min((int) Rows, row+2); nrow++)
                        for (int ncol=std::max(0, col-1); ncol < std::min((int) Cols, col+2); ncol++)
                            /* if (ncol!=col || nrow!=row) */
                            visit(nrow, ncol, current);
                }
            }
        } visitor(matrix);

        for (int r=0; r < (int) Rows; r++)
            for (int c=0; c < (int) Cols; c++)
            {
                mxdetail::area<int> area = visitor.start(r,c);
                if (!area.cells.empty()) // happens when startpoint already visited
                    areas.push_back(area);
            }

            return areas;
    }
}




typedef boost::array<int, 4> row;

template <typename T, size_t N>
boost::array<T, N> make_array(const T (&a)[N])
{
    boost::array<T, N> result;
    std::copy(a, a+N, result.begin());
    return result;
}


void make_point(int x, int y,  boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > & ring)
{
    using namespace boost::assign;

    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x-1, y-1));
    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x, y-1));
    boost::geometry::append(  ring,      boost::geometry::model::d2::point_xy<double>(x, y));
    boost::geometry::append(  ring,      boost::geometry::model::d2::point_xy<double>(x-1, y));
    boost::geometry::append(  ring,     boost::geometry::model::d2::point_xy<double>(x-1, y-1));
    boost::geometry::correct(ring);
}

void create_point(int x, int y, boost::geometry::model::multi_polygon< boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > > & mp)
{
    boost::geometry::model::multi_polygon< boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > > temp;
    boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > ring;
    make_point(x, y, ring);
    boost::geometry::union_(mp, ring, temp);
    boost::geometry::correct(temp);
    mp=temp;
}
boost::random::mt19937 rng;  
boost::random::uniform_int_distribution<> color(10,255);

std::string fill_rule()
{ 
    int red, green, blue;
    red = color(rng);
    green = color(rng);
    blue = color(rng);

    std::ostringstream rule;
    rule << "fill-rule:nonzero;fill-opacity:0.5;fill:rgb("
        << red  << ","  << green << "," << blue
        << ");stroke:rgb("
        << (red - 5) << "," << (green - 5) << "," << (blue -5) 
        <<  ");stroke-width:2";
    return rule.str();
}

int main()
{
    int sx = 4;
    int sy = 5;

    int row0[] = { 1  , 2, 3, 3, };
    int row1[] = { 1  , 3, 3, 3,};
    int row2[] = { 1  , 3, 3, 3, };
    int row3[] = { 2  , 2, 1, 2, };
    int row4[] = { 100, 2, 2, 2, };

    boost::array<row, 5> matrix;
    matrix[0] = make_array(row0);
    matrix[1] = make_array(row1);
    matrix[2] = make_array(row2);
    matrix[3] = make_array(row3);
    matrix[4] = make_array(row4);

    typedef std::vector<mxdetail::area<int> > areas_t;
    typedef areas_t::value_type::cells_t cells_t; 

    areas_t areas = mxdetail::getareas(matrix);

    using namespace boost::assign;

    typedef boost::geometry::model::polygon
        <
        boost::geometry::model::d2::point_xy<double>
        > polygon;

    typedef boost::geometry::model::multi_polygon<polygon> mp;

    typedef boost::geometry::point_type<mp>::type point_type;

    std::string filename = "draw.svg";
    std::ofstream svg(filename.c_str());


    boost::geometry::svg_mapper<point_type> mapper(svg, 400, 400);
    for (areas_t::const_iterator it=areas.begin(); it!=areas.end(); ++it)
    {
        mp pol;
        std::cout << "area of " << it->value << ": ";
        for (cells_t::const_iterator pit=it->cells.begin(); pit!=it->cells.end(); ++pit)
        {
            int row = *pit / 3, col = *pit % 3;
            std::cout << "(" << row << "," << col << "), ";
            create_point( (row+1), (col+1), pol);
        }

        std::cout << std::endl;
        mapper.add(pol);
        mapper.map(pol, fill_rule());
    }
    std::cout << "areas detected: " << areas.size() << std::endl;
    std::cin.get();
}

このコードはコンパイル可能ですが、うまくいきません (結局、配列の操作方法がわからなかったようです...):

ここに画像の説明を入力

4

2 に答える 2

3

要するに、質問が正しければ、Boost Geometry にほとんどの作業を任せることができます。

NxM のサンプル マトリックスの場合、各マトリックス セルに視覚的に対応する NxM の「flyweight」長方形ポリゴンを作成します。

ここで、反復深化アルゴリズムを使用して、すべてのグループを見つけます。

* for each _unvisited_ cell in matrix
  * start a new group
  * [visit:] 
     - mark _visited_
     - for each neighbour with equal value: 
          - add to curent group and
          - recurse [visit:]

このアルゴリズムの結果は、同じ値を持つ個別のグループになる可能性があることに注意してください (分離ポリゴンを表します)。たとえば、2OP のサンプルの値は2 つのグループになります。

次に、グループごとに、 Boost Geometry のUnion_アルゴリズムを呼び出して、そのグループを表す統合ポリゴンを見つけます。

実装例

更新C++ 11 での最適化されていない実装は次のとおりです。

Edit C++03版はこちら（Boost使用）

テストで使用されるサンプル データは、質問のマトリックスに対応しています。

#include <iostream>
#include <array>
#include <vector>
#include <set>

namespace mxdetail
{
    typedef size_t cell_id; // row * COLS + col

    template <typename T> struct area
    {
        T value;
        std::vector<cell_id> cells;
    };

    template <typename T, size_t Rows, size_t Cols>
        std::vector<area<T> > getareas(const std::array<std::array<T, Cols>, Rows>& matrix)
    {
        typedef std::array<std::array<T, Cols>, Rows> mtx;
        std::vector<area<T> > areas;

        struct visitor_t
        {
            const mtx& matrix;
            std::set<cell_id> visited;

            visitor_t(const mtx& mtx) : matrix(mtx) { }

            area<T> start(const int row, const int col)
            {
                area<T> result;
                visit(row, col, result);
                return result;
            }

            void visit(const int row, const int col, area<T>& current)
            {
                const cell_id id = row*Cols+col;
                if (visited.end() != visited.find(id))
                    return;

                bool matches = current.cells.empty() || (matrix[row][col] == current.value);

                if (matches)
                {
                    visited.insert(id);
                    current.value = matrix[row][col];
                    current.cells.push_back(id);

                    // process neighbours
                    for (int nrow=std::max(0, row-1); nrow < std::min((int) Rows, row+2); nrow++)
                    for (int ncol=std::max(0, col-1); ncol < std::min((int) Cols, col+2); ncol++)
                        /* if (ncol!=col || nrow!=row) */
                            visit(nrow, ncol, current);
                }
            }
        } visitor(matrix);

        for (int r=0; r < Rows; r++)
            for (int c=0; c < Cols; c++)
            {
                auto area = visitor.start(r,c);
                if (!area.cells.empty()) // happens when startpoint already visited
                    areas.push_back(area);
            }

        return areas;
    }
}

int main()
{
    typedef std::array<int, 3> row;
    std::array<row, 4> matrix = { 
        row { 1  , 2, 3, },
        row { 1  , 3, 3, },
        row { 1  , 3, 3, },
        row { 100, 2, 1, },
    };

    auto areas = mxdetail::getareas(matrix);

    std::cout << "areas detected: " << areas.size() << std::endl;
    for (const auto& area : areas)
    {
        std::cout << "area of " << area.value << ": ";
        for (auto pt : area.cells)
        {
            int row = pt / 3, col = pt % 3;
            std::cout << "(" << row << "," << col << "), ";
        }
        std::cout << std::endl;
    }
}

コンパイルされgcc-4.6 -std=c++0xた出力は次のとおりです。

areas detected: 6
area of 1: (0,0), (1,0), (2,0), 
area of 2: (0,1), 
area of 3: (0,2), (1,1), (1,2), (2,1), (2,2), 
area of 100: (3,0), 
area of 2: (3,1), 
area of 1: (3,2),
于 2011-11-07T23:17:50.573 に答える
0

ポイントの数が多い場合 (たとえば、1000x1000 以上)、上記のソリューションは大量のメモリを消費します。そして、これがまさにトピックスターターに起こったことです。

以下に、よりスケーラブルなアプローチを示します。

ここでは 2 つの問題に分けます。1 つは領域を見つけること、もう 1 つは領域をポリゴンに変換することです。

最初の問題は、隣接するグラフに同じ「色」が付けられている場合に限り、エッジを持つグリッド グラフの接続されたコンポーネントを見つけることと実際には同じです。のグリッド グラフを使用できます。

#include <boost/graph/grid_graph.hpp>
// Define dimension lengths, a MxN in this case
boost::array<int, 2> lengths = { { M, N } };

// Create a MxN two-dimensional, unwrapped grid graph 
grid_graph<2> graph(lengths);

次に、与えられた行列 M をエッジ フィルタに変換する必要があります。隣接する行列の「色」が同じ場合、グリッド エッジが存在します。

template <class Matrix>
struct GridEdgeFilter
{  
    typedef grid_graph<2> grid;
    GridEdgeFilter(const Matrix & m, const grid&g):_m(&m),_g(&g){}

    /// \return true iff edge is present in the graph
    bool operator()(grid::edge_descriptor e) const
    {
        grid::vertex_descriptor src = source(e,*_g), tgt = target(e,*_g);
        //src[0] is x-coord of src, etc. The value (*m)[x,y] is the color of the point (x,y).
        //Edge is preserved iff matrix values are equal
        return (*_m)[src[0],src[1]] == (*_m)[tgt[0],tgt[1]];
    }

    const Matrix * _m;
    const grid* _g;
};

boost::filtered_graph最後に、グリッドのを定義し、EdgeFilter接続されたコンポーネントの Boost.Graph アルゴリズムを呼び出します。

各連結成分は、単色の点のセット、つまり多角形に変換したい領域を表します。

ここで、別の問題があります。Boost.Geometry では、ポリゴンを 1 つずつマージすることしかできません。したがって、ポリゴン数が多いと非常に遅くなります。

より良い方法は、Boost.Polygon、つまりそのプロパティ マージ機能を使用することです。空のproperty_mergeオブジェクトから開始し、指定された色の長方形を挿入して続行します (色をプロパティとして設定できます)。次に、メソッドを呼び出して、出力としてmergea を取得polygon_setします。

于 2013-11-02T02:27:41.317 に答える