基于Boost Graph Library构建无冗余GeoJSON线路图的技术问题

问题1：std::map编译错误C2678：缺少const point的binary '<'运算符 #

原因 #

std::map是有序关联容器，要求键类型必须支持const版本的小于比较运算符，因为容器内部会对键进行排序，且访问键时均为const引用。你的point结构体未定义该运算符，导致编译失败。

解决方案 #

给point结构体添加const修饰的operator<，定义明确的排序规则（比如先比较经度，再比较纬度）：

struct point {
    double lat;
    double lon;

    // 满足std::map要求的const版本小于运算符
    bool operator<(const point& other) const {
        if (lon != other.lon) {
            return lon < other.lon;
        }
        return lat < other.lat;
    }
};

如果使用Boost.Geometry的model::point，可直接复用Boost提供的比较逻辑，自定义结构体则必须显式实现该运算符。

问题2：基于LineString数据添加边的实现步骤 #

假设你已定义如下图类型：

// 边属性：包含ID和欧氏距离权重
struct Legs {
    int id;
    double distance;
};

// 无向图类型：顶点属性为point，边属性为Legs
using Graph = boost::adjacency_list<
    boost::vecS,               // 边存储方式
    boost::vecS,               // 顶点存储方式
    boost::undirectedS,        // 无向图类型
    point,                     // 顶点属性
    Legs                       // 边属性
>;

实现逻辑 #

遍历每个LineString，对其中的连续点对做以下处理：

1. 检查点是否已存在于顶点映射中，不存在则添加到图并更新映射
2. 计算两点间欧氏距离
3. 创建边属性并添加无向边

代码示例 #

// 计算两点欧氏距离（若为经纬度，建议转平面坐标后计算，此处为平面示例）
double calculate_euclidean_distance(const point& p1, const point& p2) {
    double dx = p1.lon - p2.lon;
    double dy = p1.lat - p2.lat;
    return std::sqrt(dx*dx + dy*dy);
}

Graph build_graph(const std::vector<linestring>& lines) {
    Graph g;
    std::map<point, Graph::vertex_descriptor> vertex_map;
    int edge_id = 0; // 边ID自增计数器（可替换为GeoJSON中的原始ID）

    for (const auto& line : lines) {
        if (line.size() < 2) continue; // 跳过无效短线路

        point prev_point = line[0];
        // 初始化第一个顶点
        if (!vertex_map.count(prev_point)) {
            auto v = boost::add_vertex(prev_point, g);
            vertex_map[prev_point] = v;
        }

        // 遍历线路中的连续点对，添加边
        for (size_t i = 1; i < line.size(); ++i) {
            point curr_point = line[i];
            // 检查当前顶点是否存在
            if (!vertex_map.count(curr_point)) {
                auto v = boost::add_vertex(curr_point, g);
                vertex_map[curr_point] = v;
            }

            // 获取顶点描述符
            auto v_prev = vertex_map[prev_point];
            auto v_curr = vertex_map[curr_point];

            // 计算距离并创建边属性
            double dist = calculate_euclidean_distance(prev_point, curr_point);
            Legs leg{edge_id++, dist};

            // 添加无向边
            boost::add_edge(v_prev, v_curr, leg, g);

            prev_point = curr_point;
        }
    }

    return g;
}

注意事项 #

• 若需处理经纬度的球面距离，替换calculate_euclidean_distance为Haversine公式实现
• 边ID可根据GeoJSON中的原始属性赋值，而非自增
• 若追求更高性能，可将std::map替换为std::unordered_map，但需为point实现哈希函数和operator==

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