Dies ist eine ziemlich abgestanden Frage, aber ich fand es, wenn genau das gleiche Problem zu lösen versuchen. Es ist nur fair, die Lösung, die ich getroffen habe, zu teilen, damit der nächste arme Saft es nicht selbst herausfinden muss.
Ich habe keine Ahnung, ob dies ein besonders guter Weg ist, Dinge zu tun, und ich vermute, es würde kämpfen, wenn Sie anfangen würden, gebogene Zellen zu verwenden, aber es funktionierte für meine Zwecke.
Das grundlegende Problem ist, dass Sie nur einen Eckpunkt für die unendlichen Kanten haben, so dass Sie den Richtungsvektor selbst berechnen müssen. Die zu verwendende Richtung ist senkrecht zum Vektor zwischen den beiden durch die Kante getrennten Punkten.
#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());
}
}
Jesus Chris, warum haben wir das nicht in der Bibliothek selbst implementiert? o.O. – PiotrK