如何用Boost.Voronoi正确生成浮点输入的Voronoi胞体？

一、正确适配浮点坐标的输入方案 #

Boost.Voronoi依赖整数运算保证拓扑正确性，直接用浮点输入会触发精度问题导致胞体错乱。正确做法是通过固定比例缩放将浮点坐标转换为64位整数（int64_t），既保留精度又符合库的输入要求：

• 自定义点类型示例（以米为单位，缩放1e6转为微米级整数）：

struct PedPoint {
    double x, y;
    PedPoint(double x_, double y_) : x(x_), y(y_) {}

    // 返回缩放后的整数坐标，供Boost.Voronoi读取
    int64_t x() const { return static_cast<int64_t>(x * 1e6); }
    int64_t y() const { return static_cast<int64_t>(y * 1e6); }
};

// 向Boost注册坐标转换器
namespace boost::polygon::detail {
    template <>
    struct geometry_converter<PedPoint> {
        typedef int64_t coordinate_type;
        static inline coordinate_type get(const PedPoint& p, orientation_2d orient) {
            return (orient == HORIZONTAL) ? p.x() : p.y();
        }
    };
}

• 此方案避免了放大100倍精度不足的问题，能精确还原原始浮点坐标，彻底解决胞体交叉、点归属错误的问题。

二、修复clang-tidy线段构造报错 #

clang-tidy的类型检查严格，需确保线段构造的起点/终点类型统一为自定义点类型，避免隐式转换：

std::vector<boost::voronoi_diagram<double>::segment_type> edges;
// 用自定义PedPoint构造线段，而非直接传double
edges.emplace_back(PedPoint(wall_x1, wall_y1), PedPoint(wall_x2, wall_y2));

三、Qt6替代OpenGL的可视化实现 #

用Qt6的QPainter实现跨平台的Voronoi胞体绘制，无需依赖过时的OpenGL示例：

void renderVoronoi(QPainter& painter, const boost::voronoi_diagram<double>& vd, 
                   const std::vector<PedPoint>& ped_points, double scale = 1e6) {
    // 绘制胞体
    painter.setPen(QPen(Qt::black, 0.01));
    for (const auto& cell : vd.cells()) {
        if (!cell.contains_point()) continue;
        QPainterPath path;
        bool is_first = true;
        for (const auto& edge : cell.edges()) {
            if (!edge.is_finite()) continue;
            auto v0 = edge.vertex0();
            QPointF p(v0->x()/scale, v0->y()/scale);
            is_first ? path.moveTo(p) : path.lineTo(p);
            is_first = false;
        }
        path.closeSubpath();
        painter.fillPath(path, QColor::fromHsv(rand()%360, 100, 240));
        painter.drawPath(path);
    }
    // 绘制行人头部点
    painter.setPen(Qt::red);
    painter.setBrush(Qt::red);
    for (const auto& p : ped_points) {
        painter.drawEllipse(QPointF(p.x, p.y), 0.02, 0.02);
    }
}

• 边界胞体的无限边需根据室内场景的实际边界（如墙壁坐标）截断，避免绘制出画布外的无效线条。

四、胞体面积计算 #

用鞋带公式计算胞体面积，注意将缩放后的顶点坐标还原为原始浮点值：

double calculateCellArea(const boost::voronoi_diagram<double>::cell_type& cell, double scale = 1e6) {
    double area = 0.0;
    std::vector<QPointF> vertices;
    for (const auto& edge : cell.edges()) {
        if (!edge.is_finite()) continue;
        auto v = edge.vertex0();
        vertices.emplace_back(v->x()/scale, v->y()/scale);
    }
    // 鞋带公式计算多边形面积
    size_t n = vertices.size();
    for (size_t i = 0; i < n; ++i) {
        size_t j = (i + 1) % n;
        area += vertices[i].x() * vertices[j].y() - vertices[j].x() * vertices[i].y();
    }
    return std::fabs(area) / 2.0;
}

核心注意事项 #

• 缩放比例需匹配数据精度：毫米级数据用1e3，微米级用1e6，避免浮点转整数时的截断误差。
• 禁止直接将浮点值传入Boost.Voronoi，整数运算的拓扑稳定性是库的设计核心，强行用浮点会导致胞体拓扑错误。

内容的提问来源于stack exchange，提问作者baziorek