Dijkstra 算法的实现方案

下面是一个基于 Dijkstra 算法的实现方案，能够在 DEM（数字高程模型）数据上进行寻路，并满足以下需求：

使用 Qt C++ 编写；
规避 DEM 中的障碍物；
支持指定起点和终点；
使用 GDAL 库读取 DEM 文件；
输出路径到 TXT 文件；
输出的坐标为地理坐标（例如经纬度），而不是像素坐标。
前置条件
GDAL 库：确保你的开发环境已经安装了 GDAL 库，并在 Qt 项目中正确配置了 GDAL 库路径。
Qt 环境：确保已经安装 Qt 并配置开发环境。
实现步骤

1. 初始化项目并引入 GDAL
   在 Qt 项目的 .pro 文件中引入 GDAL 库和必要的标志：

QT += core
CONFIG += c++11
LIBS += -lgdal
2. 代码实现
下面是实现该功能的代码。

#include <QCoreApplication>
#include <gdal_priv.h>
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

struct Node {
    int x, y;
    double cost;
    bool operator>(const Node& other) const { return cost > other.cost; }
};

class DEMPathFinder {
public:
    DEMPathFinder(const std::string &demPath);
    bool findPath(double startLon, double startLat, double endLon, double endLat, const std::string &outputPath);

private:
    double geoTransform[6];
    int width, height;
    std::vector<std::vector<double>> elevationData;
    std::vector<std::vector<bool>> obstacles;

    bool loadDEM(const std::string &demPath);
    bool isValid(int x, int y);
    double calculateCost(int x, int y, int nx, int ny);
    void pixelToGeo(int x, int y, double &lon, double &lat);
    void geoToPixel(double lon, double lat, int &x, int &y);
};

DEMPathFinder::DEMPathFinder(const std::string &demPath) {
    GDALAllRegister();
    loadDEM(demPath);
}

bool DEMPathFinder::loadDEM(const std::string &demPath) {
    GDALDataset *dataset = (GDALDataset*) GDALOpen(demPath.c_str(), GA_ReadOnly);
    if (dataset == nullptr) return false;

    dataset->GetGeoTransform(geoTransform);
    width = dataset->GetRasterXSize();
    height = dataset->GetRasterYSize();

    elevationData.resize(height, std::vector<double>(width));
    obstacles.resize(height, std::vector<bool>(width, false));

    GDALRasterBand *band = dataset->GetRasterBand(1);
    for (int y = 0; y < height; ++y) {
        band->RasterIO(GF_Read, 0, y, width, 1, elevationData[y].data(), width, 1, GDT_Float64, 0, 0);
        for (int x = 0; x < width; ++x) {
            if (elevationData[y][x] == -9999) { // 假设 -9999 表示障碍物
                obstacles[y][x] = true;
            }
        }
    }
    GDALClose(dataset);
    return true;
}

bool DEMPathFinder::isValid(int x, int y) {
    return x >= 0 && x < width && y >= 0 && y < height && !obstacles[y][x];
}

double DEMPathFinder::calculateCost(int x, int y, int nx, int ny) {
    return 1.0 + std::abs(elevationData[ny][nx] - elevationData[y][x]);
}

void DEMPathFinder::pixelToGeo(int x, int y, double &lon, double &lat) {
    lon = geoTransform[0] + x * geoTransform[1] + y * geoTransform[2];
    lat = geoTransform[3] + x * geoTransform[4] + y * geoTransform[5];
}

void DEMPathFinder::geoToPixel(double lon, double lat, int &x, int &y) {
    x = static_cast<int>((lon - geoTransform[0]) / geoTransform[1]);
    y = static_cast<int>((lat - geoTransform[3]) / geoTransform[5]);
}

bool DEMPathFinder::findPath(double startLon, double startLat, double endLon, double endLat, const std::string &outputPath) {
    int startX, startY, endX, endY;
    geoToPixel(startLon, startLat, startX, startY);
    geoToPixel(endLon, endLat, endX, endY);

    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
    std::vector<std::vector<double>> dist(height, std::vector<double>(width, std::numeric_limits<double>::infinity()));
    std::vector<std::vector<std::pair<int, int>>> prev(height, std::vector<std::pair<int, int>>(width, {-1, -1}));

    pq.push({startX, startY, 0});
    dist[startY][startX] = 0;

    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};

    while (!pq.empty()) {
        Node node = pq.top(); pq.pop();
        if (node.x == endX && node.y == endY) break;

        for (int i = 0; i < 4; ++i) {
            int nx = node.x + dx[i];
            int ny = node.y + dy[i];

            if (isValid(nx, ny)) {
                double newCost = node.cost + calculateCost(node.x, node.y, nx, ny);
                if (newCost < dist[ny][nx]) {
                    dist[ny][nx] = newCost;
                    pq.push({nx, ny, newCost});
                    prev[ny][nx] = {node.x, node.y};
                }
            }
        }
    }

    std::vector<std::pair<double, double>> path;
    for (int x = endX, y = endY; x != -1 && y != -1; ) {
        double lon, lat;
        pixelToGeo(x, y, lon, lat);
        path.push_back({lon, lat});
        auto [px, py] = prev[y][x];
        x = px;
        y = py;
    }

    std::ofstream outFile(outputPath);
    for (auto it = path.rbegin(); it != path.rend(); ++it) {
        outFile << it->first << ", " << it->second << std::endl;
    }

    return !path.empty();
}

int main(int argc, char *argv[]) {
    QCoreApplication app(argc, argv);

    DEMPathFinder pathFinder("path/to/your/dem/file.tif");
    if (pathFinder.findPath(102.0, 25.0, 103.0, 26.0, "output_path.txt")) {
        std::cout << "Path found and saved to output_path.txt" << std::endl;
    } else {
        std::cout << "Path not found" << std::endl;
    }

    return app.exec();
}

代码说明
加载 DEM 文件：使用 GDAL 加载 DEM 文件，并获取像素坐标到地理坐标的转换参数。
障碍物检测：假设 DEM 数据中的 -9999 表示障碍物，可根据需要修改。
Dijkstra 算法：使用优先队列进行路径搜索，寻找代价最低的路径。
地理坐标转换：实现了像素坐标和地理坐标的转换。
输出路径：将路径的地理坐标保存到 txt 文件中。
注意事项
将 “path/to/your/dem/file.tif” 替换为你的 DEM 文件路径；
GDAL 安装和库链接应配置正确，否则可能出现加载失败的情况。
这段代码可以在 DEM 数据上寻找到避开障碍物的最优路径，并输出路径的地理坐标。