如何讓無限邊緣提升到有限邊緣？

Question

我發現，在升壓庫，Voronoi圖，一些邊緣數據是無限的。根據指示，它必須被裁剪。但我無法找到如何去做。 有誰可以給​​我一個示例代碼，請？

THX

Answer 1

這是一個相當陳舊的問題，但我發現它試圖解決相同問題的時候。分享我遇到的解決方案是公平的，所以下一個可憐的悶棍不必自己弄清楚。

我不知道這是否是做事情特別好的方式，我想，如果你開始使用弧形細胞會掙扎，但我的目的，效果還行。

最根本的問題是，你只有無限的邊緣一個頂點，所以你要自己計算的方向向量。使用方向垂直於由邊緣分隔的兩點之間的矢量。

#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())); 
    } 
    } 

也可能會丟失一些類變量或方法，但邏輯是這裏重要的。