come dare un vantaggio infinito in boost a un limite finito?

Question

Trovo che nella libreria boost, per il diagramma di voronoi, alcuni dati di bordo siano infiniti. Secondo le istruzioni, deve essere tagliato. Ma non riesco a trovare come farlo. Qualcuno potrebbe darmi un codice di esempio, per favore?

Thx

Answer 1

Questa è una domanda piuttosto stantio, ma ho trovato quando si cerca di risolvere lo stesso identico problema. È giusto condividere la soluzione su cui mi sono imbattuto, quindi la prossima povera linfa non deve capirlo da sé.

Non ho idea se questo sia un modo particolarmente valido di fare le cose, e sospetto che sarebbe difficile se si iniziasse a usare le celle curve, ma ha funzionato correttamente per i miei scopi.

Il problema di base è che hai solo un vertice per i bordi infiniti, quindi devi calcolare tu stesso il vettore di direzione. La direzione da utilizzare è perpendicolare al vettore tra i due punti separati dal bordo.

#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

ho trovato questo segmento di codice qui: 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())); 
    } 
    } 

Potrebbe mancare alcune variabili di classe o metodi, ma la logica è ciò che è importante qui.