C++实现Voronoi风格瓦片地图的垂线计算及方案咨询

你步骤4需要的不是任意垂线，是两个相邻站点连线的垂直平分线——Voronoi边的定义就是到两个相邻站点距离相等的点的集合，正好对应这条线，计算逻辑很直接：

• 设两个相邻站点坐标为A(x1, y1)、B(x2, y2)，先算两点连线的中点：mx = (x1 + x2) / 2.0，my = (y1 + y2) / 2.0，垂直平分线必然过这个中点。
• 计算原线段AB的方向向量dx = x2 - x1、dy = y2 - y1，垂直平分线的方向向量为(-dy, dx)（反向(dy, -dx)也成立，垂线是双向延伸的）。
• 如果要写直线方程，注意处理除零边界：原线段水平时（dy=0），垂直平分线是竖线，方程为x = mx；原线段垂直时（dx=0），垂直平分线是水平线，方程为y = my；其余情况斜率为原线段斜率的负倒数，即k = -dx/dy，代入点斜式即可。
• 步骤5求Voronoi顶点不需要绘制整条垂线，直接算两条相邻垂直平分线的交点即可：单个Voronoi顶点对应三个相邻站点的外接圆圆心，是三个站点两两连线的三条垂直平分线的公共交点，计算两条线的交点就能得到坐标，第三条线可以用来做精度校验。

下面是直线求交的参考实现，已经加了浮点精度容错：

#include <cmath>
#include <utility>
using namespace std;

// 计算两条直线交点：直线1过点p1、方向向量d1；直线2过点p2、方向向量d2
// 返回值第一个字段标记是否相交（平行/重合返回false），第二个字段为交点坐标
pair<bool, pair<double, double>> get_line_intersection(
    pair<double, double> p1, pair<double, double> d1,
    pair<double, double> p2, pair<double, double> d2
) {
    const double eps = 1e-8;
    double det = d1.first * d2.second - d1.second * d2.first;
    if (fabs(det) < eps) {
        return {false, {0.0, 0.0}};
    }
    double t = ((p2.first - p1.first) * d2.second - (p2.second - p1.second) * d2.first) / det;
    return {true, {p1.first + t * d1.first, p1.second + t * d1.second}};
}

你现在手写邻接连线、垂线、交点的思路很容易踩浮点精度、邻接漏判、边界裁剪的坑，尤其是地图边缘的Voronoi单元是开放图形，需要手动和地图边界求交裁剪，从零实现调试成本很高，直接用成熟实现即可：

• 首选Boost.Geometry库内置的Voronoi实现：工业级稳定性，支持整数、浮点双精度坐标，十万级站点生成速度在毫秒级，输出结果直接包含所有Voronoi单元、边、顶点的拓扑关联，不需要改动你前两步生成瓦片站点的逻辑，直接把站点数组传入即可拿到结果，省掉所有几何计算步骤。
• 如果不想引入Boost的重依赖，可以用无第三方依赖的轻量实现jc_voronoi：纯C编写的单库实现，接口极简，编译无额外配置，专门适配游戏、程序化地图生成类场景，输出的Voronoi多边形可以直接用来渲染，对均匀分布站点的适配效果很好。
• 额外提醒：你当前每个瓦片内随机偏移生成站点的方式，生成的Voronoi多边形大小均匀、边缘自然，非常适合做瓦片地图风格的渲染，用成熟库的话直接跳过你原来的3-5步即可，不需要自己处理几何逻辑。

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