[Boost Geometry] points -> polygon cluster

[개요]

DFS(Depth First Search)를 활용해 분포되어있는 boost point들을 boost polygon으로 클러스터화 하는 function

 

[결과]

points -> cluster polygon

응용 사례) 노란색 : 빈 공간에 대한 cluster find 결과

[코드 원본]

//INCLUDE LIBRARY
#include <boost/geometry.hpp>
#include <iostream>
#include <vector>
#include <fstream>

//MAKE NAMESPACE
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

//DEFINITION POINT, CLUSTER
typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
typedef std::vector<point_t> cluster_t;

//DIRECTION ARRAY
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

void DFS(std::vector<point_t> points, std::vector<bool> &used, int index, cluster_t &cluster)
{   
    const auto& point = points.at(index);
    
    for (int j = 0; j < points.size(); ++j)
    {
        if (index == j) continue;
        if (used[j]) continue;

        const auto& p = points.at(j);

        double x2 = bg::get<0>(p);
        double y2 = bg::get<1>(p);

        if (boost::geometry::distance(point, p) == 1)
        {   
            std::cout << j << " ";
            cluster.emplace_back(p);
            used[j] = true;

            DFS(points, used, j, cluster);
        }
    }
}


int main()
{
    std::vector<point_t> points;
    std::ofstream svg("boost_test.svg");
    boost::geometry::svg_mapper<point_t> mapper(svg, 600, 600);

    boost::geometry::model::box<point_t> box(point_t(-15,-15),point_t(15,15));

    mapper.add(box);
    mapper.map(box, "fill-opacity:1.0;fill:rgb(255,255,255);stroke:rgb(255,255,255);stroke-width:2", 2);

    int xy[10][10];

    for (double x = 0.0; x <= 10.0; x += 1.0)
    {
        for (double y = 0.0; y <= 10.0; y += 1.0)
        {
            if( (int)x % 5 != 0 && (int)y % 5 != 0 )
                points.push_back(point_t{ x, y });
        }
    }
    

    std::vector<cluster_t> clusters;
    std::vector<bool> used(points.size(),false);
    
    for (auto p : points)
    {
        mapper.add(p);
        mapper.map(p, "fill-opacity:1.0;fill:rgb(153,4,100);stroke:rgb(153,104,100);stroke-width:1", 1);
    }

    for (int i=0;i<points.size();++i)
    {
        const auto& point = points.at(i);
        
        if (used[i]) continue;

        double x1 = bg::get<0>(point);
        double y1 = bg::get<1>(point);
        

        cluster_t cluster;

        cluster.emplace_back(point);
        std::cout << i << " ";

        DFS(points, used, i, cluster);

        used[i] = true;

        clusters.emplace_back(cluster);

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

    auto draw = [&](boost::geometry::svg_mapper<point_t>& mapper, boost::geometry::model::polygon<point_t, false> p, double r, double g, double b)
    {
        std::string option = "fill - opacity:1.0;fill:rgb(" + std::to_string(r) +","+ std::to_string(g) + "," + std::to_string(b) + "; stroke:rgb(255, 255, 255); stroke - width:1";

        mapper.add(p);
        mapper.map(p, option, 1);
    };

    for (size_t i = 0; i < clusters.size(); ++i) {
        std::cout << "Cluster " << i << std::endl;

        auto r = (255.0 * ((double)i / clusters.size())) ;
        auto g = (255.0 * ((double)i / clusters.size())) ;
        auto b = (255.0 * ((double)i / clusters.size())) ;

        std::string option = "fill - opacity:1.0;fill:rgb(" + std::to_string(r) + "," + std::to_string(g) + "," + std::to_string(b) + "; stroke:rgb(255, 255, 255); stroke - width:1";
        
        std::cout << option << std::endl;

        boost::geometry::model::polygon<point_t, false> poly;
        boost::geometry::model::polygon<point_t, false> results;

        for (int x = 0; x < clusters[i].size(); ++x)
        {
            poly.outer().emplace_back(clusters[i][x]);
        }

        boost::geometry::convex_hull(poly, results);
        
        mapper.add(results);
        mapper.map(results, "fill-opacity:1.0;fill:rgb(153,4,100);stroke:rgb(153,104,100);stroke-width:1", 1);
    }
}

 

[코드 해석]

• DFS Function
  • point(x, y)의 집합인 points를 순회하며, 조건으로 제시한 거리보다 가까이 있는 point들을 찾는 함수
  • 특정 point로부터 시작하며 클러스터에 해당하는 경우 다음 연산에서 제외
• mapper
  • 디버그를 위해 svg로 출력하기 위한 도구
  • boost svg mapper를 사용
• convex_hull
  • point들을 outer ring에 처리한 이후, OBB를 계산하기 위해 사용
  • inner ring을 제외하고 outline만 살리는 로직으로 다각형 polygon을 구현할 수 있음