有限端へのブーストで無限端を作る方法は？

Question

私は、ボロノイ図のブーストライブラリでは、一部のエッジデータが無限大であることがわかりました。命令によれば、それはクリップされなければならない。しかし、私はそれを行う方法を見つけることができません。 誰かが私にサンプルコードをくれますか？

Thxを

Answer 1

は、これはかなり古い質問ですが、正確に同じ問題を解決しようとするとき、私はそれを見つけました。私が打ち負かすソリューションを分かち合うことは公正なことであり、次の貧弱な樹液はそれ自体を理解する必要はありません。

これは特に効果的な方法であるかどうかはわかりませんが、カーブしたセルを使い始めると苦労すると思いますが、それはうまくいきました。

基本的な問題は、無限端の頂点が1つしかないことです。そのため、方向ベクトルを自分で計算する必要があります。使用する方向は、エッジで区切られた2点間のベクトルに垂直です。

#include <vector> 
#include <boost/polygon/voronoi.hpp> 
using boost::polygon::voronoi_builder; 
using boost::polygon::voronoi_diagram; 

typedef boost::polygon::point_data<int> point; 
typedef voronoi_diagram<double>::cell_type cell_type; 
typedef voronoi_diagram<double>::edge_type edge_type; 
typedef voronoi_diagram<double>::vertex_type vertex_type; 

int main(int argc, char *argv[]) 
{ 
    std::vector<point> points; 

    // Populate with random points 
    for (int i = 0; i < 50; i++) 
    { 
     points.push_back(point(60 + rand() % 500, 60 + rand() % 500)); 
    } 

    voronoi_diagram<double> vd; 
    construct_voronoi(points.begin(), points.end(), &vd); 

    // vd now contains the voronoi diagram. Let's visualise it 
    // pseudocode 'draw_line(x1, y1, x2, y2)' 

    for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); 
     it != vd.cells().end(); ++it) 
    { 
     const cell_type& cell = *it; 
     const edge_type* edge = cell.incident_edge(); 

     do 
     { 
     if (edge->is_primary()) 
     { 
      // Easy finite edge case 
      if (edge->is_finite()) 
      { 
       // Without this check each edge would be drawn twice 
       // as they are really half-edges 
       if (edge->cell()->source_index() < 
        edge->twin()->cell()->source_index()) 
       { 
        draw_line(edge->vertex0()->x(), edge->vertex0()->y(), 
          edge->vertex1()->x(), edge->vertex1()->y()); 
       } 
      } 
      else 
      { 
       // This covers the infinite edge case in question. 
       const vertex_type* v0 = edge->vertex0(); 
       // Again, only consider half the half-edges, ignore edge->vertex1() 
       // to avoid overdrawing the lines 
       if (v0) 
       { 
        // Direction of infinite edge if perpendicular to direction 
        // between the points owning the two half edges. 
        // Take the rotated right vector and multiply by a large 
        // enough number to reach your bounding box 
        point p1 = points[edge->cell()->source_index()]; 
        point p2 = points[edge->twin()->cell()->source_index()]; 
        int end_x = (p1.y() - p2.y()) * 640; 
        int end_y = (p1.x() - p2.x()) * -640; 

        draw_line(v0->x(), v0->y(), 
          end_x, end_y); 
       } 
      } 
     } 
     edge = edge->next(); 
     } while (edge != cell.incident_edge()); 
    } 
} 

Answer 2

私はここで、このコードセグメントを見つけました：http://www.boost.org/doc/libs/1_55_0/libs/polygon/example/voronoi_visualizer.cpp

void clip_infinite_edge(
     const edge_type& edge, std::vector<point_type>* clipped_edge) { 
    const cell_type& cell1 = *edge.cell(); 
    const cell_type& cell2 = *edge.twin()->cell(); 
    point_type origin, direction; 
    // Infinite edges could not be created by two segment sites. 
    if (cell1.contains_point() && cell2.contains_point()) { 
     point_type p1 = retrieve_point(cell1); 
     point_type p2 = retrieve_point(cell2); 
     origin.x((p1.x() + p2.x()) * 0.5); 
     origin.y((p1.y() + p2.y()) * 0.5); 
     direction.x(p1.y() - p2.y()); 
     direction.y(p2.x() - p1.x()); 
    } else { 
     origin = cell1.contains_segment() ? 
      retrieve_point(cell2) : 
      retrieve_point(cell1); 
     segment_type segment = cell1.contains_segment() ? 
      retrieve_segment(cell1) : 
      retrieve_segment(cell2); 
     coordinate_type dx = high(segment).x() - low(segment).x(); 
     coordinate_type dy = high(segment).y() - low(segment).y(); 
     if ((low(segment) == origin)^cell1.contains_point()) { 
     direction.x(dy); 
     direction.y(-dx); 
     } else { 
     direction.x(-dy); 
     direction.y(dx); 
     } 
    } 
    coordinate_type side = xh(brect_) - xl(brect_); 
    coordinate_type koef = 
     side/(std::max)(fabs(direction.x()), fabs(direction.y())); 
    if (edge.vertex0() == NULL) { 
     clipped_edge->push_back(point_type(
      origin.x() - direction.x() * koef, 
      origin.y() - direction.y() * koef)); 
    } else { 
     clipped_edge->push_back(
      point_type(edge.vertex0()->x(), edge.vertex0()->y())); 
    } 
    if (edge.vertex1() == NULL) { 
     clipped_edge->push_back(point_type(
      origin.x() + direction.x() * koef, 
      origin.y() + direction.y() * koef)); 
    } else { 
     clipped_edge->push_back(
      point_type(edge.vertex1()->x(), edge.vertex1()->y())); 
    } 
    } 

それはいくつかのクラス変数やメソッドを欠落していることかもしれませんが、ロジックはここで重要なものです。