как дать сделать бесконечное преимущество в форсированном направлении до конечного

Это довольно устаревший вопрос, но я нашел его, пытаясь решить точно такую ​​же проблему. Справедливо поделиться решением, с которым я столкнулся, так что следующему бедному соку не придется это выяснять самим.

Я понятия не имею, если это особенно хороший способ сделать что-то, и я подозреваю, что будет трудно, если вы начнете использовать изогнутые ячейки, но это работало нормально для моих целей.

Основная проблема в том, что у вас есть только одна вершина для бесконечных ребер, поэтому вы должны сами рассчитать вектор направления. Используемое направление перпендикулярно вектору между двумя точками, разделенными ребром.

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