jak dać nieskończoną przewagę w dopalaczu do skończonej krawędzi?

Question

Uważam, że w bibliotece boost, dla diagramu voronoi, niektóre dane krawędzi są nieskończone. Zgodnie z instrukcją, musi być obcięta. Ale nie mogę znaleźć, jak to zrobić. Czy ktoś może podać mi przykładowy kod?

Thx

Answer 1

Jest to raczej nieświeże pytanie, ale znalazłem go, gdy próbuje rozwiązać dokładnie ten sam problem. Sprawiedliwe jest dzielenie się rozwiązaniem, na które trafiłem, aby następny biedny sap nie musiał sam tego rozgryźć.

Nie mam pojęcia, czy jest to szczególnie dobry sposób robienia rzeczy, i podejrzewam, że byłoby to trudne, gdybyś zaczął używać zakrzywionych komórek, ale działało to dobrze dla moich celów.

Podstawowym problemem jest to, że masz tylko jeden wierzchołek dla nieskończonych krawędzi, więc musisz sam obliczyć wektor kierunku. Kierunek użycia jest prostopadły do ​​wektora między dwoma punktami oddzielonymi krawędzią.

#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

znalazłem ten segment kodu tutaj: 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())); 
    } 
    } 

To może brakować niektórych zmiennych lub metod klasy, ale logika jest to, co jest tu ważne.