如何使用opencv python解决theta迷宫？

Question

我必须找到从迷宫中心到最外圈的最短路径。我必须使用opencv和python来解决这个问题

Answer 1

我出去了！

可以考虑图像中的每个白色像素为无向加权图的节点。每个像素（节点）都连接到它的白色邻居。连接两个节点的边的重量在水平和垂直方向上为1，在对角线方向上为sqrt(2)（或简单地为1.414）。

由于您知道起点和终点，因此您可以运行Dijkstra algorithm来查找起点和终点之间的最短路径。

我用Rosetta Code实现Dijkstra算法的：

这是代码（不是真的打磨，但工作）。代码是用C++编写的，但应该很容易转换为Python，特别是如果你能找到一个很好的Dijkstra算法实现：

#include <opencv2/opencv.hpp> 


#include <iostream> 
#include <vector> 
#include <string> 
#include <list> 

#include <limits> // for numeric_limits 

#include <vector> 
#include <set> 
#include <utility> // for pair 
#include <algorithm> 
#include <iterator> 

using namespace cv; 
using namespace std; 

typedef int vertex_t; 
typedef double weight_t; 

const weight_t max_weight = std::numeric_limits<double>::infinity(); 

struct neighbor { 
    vertex_t target; 
    weight_t weight; 
    neighbor(vertex_t arg_target, weight_t arg_weight) 
     : target(arg_target), weight(arg_weight) { } 

    bool operator == (const neighbor& other) const { 
     return target == other.target; 
    } 
}; 

typedef std::vector<std::vector<neighbor> > adjacency_list_t; 


void DijkstraComputePaths(vertex_t source, 
    const adjacency_list_t &adjacency_list, 
    std::vector<weight_t> &min_distance, 
    std::vector<vertex_t> &previous) 
{ 
    int n = adjacency_list.size(); 
    min_distance.clear(); 
    min_distance.resize(n, max_weight); 
    min_distance[source] = 0; 
    previous.clear(); 
    previous.resize(n, -1); 
    std::set<std::pair<weight_t, vertex_t> > vertex_queue; 
    vertex_queue.insert(std::make_pair(min_distance[source], source)); 

    while (!vertex_queue.empty()) 
    { 
     weight_t dist = vertex_queue.begin()->first; 
     vertex_t u = vertex_queue.begin()->second; 
     vertex_queue.erase(vertex_queue.begin()); 

     // Visit each edge exiting u 
     const std::vector<neighbor> &neighbors = adjacency_list[u]; 
     for (std::vector<neighbor>::const_iterator neighbor_iter = neighbors.begin(); 
      neighbor_iter != neighbors.end(); 
      neighbor_iter++) 
     { 
      vertex_t v = neighbor_iter->target; 
      weight_t weight = neighbor_iter->weight; 
      weight_t distance_through_u = dist + weight; 
      if (distance_through_u < min_distance[v]) { 
       vertex_queue.erase(std::make_pair(min_distance[v], v)); 

       min_distance[v] = distance_through_u; 
       previous[v] = u; 
       vertex_queue.insert(std::make_pair(min_distance[v], v)); 

      } 

     } 
    } 
} 


std::list<vertex_t> DijkstraGetShortestPathTo(
    vertex_t vertex, const std::vector<vertex_t> &previous) 
{ 
    std::list<vertex_t> path; 
    for (; vertex != -1; vertex = previous[vertex]) 
     path.push_front(vertex); 
    return path; 
} 

struct lessPoints 
{ 
    bool operator() (const Point& lhs, const Point& rhs) const { 
     return (lhs.x != rhs.x) ? (lhs.x < rhs.x) : (lhs.y < rhs.y); 
    } 
}; 

int main() 
{ 
    Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE); 
    resize(img, img, Size(), 0.5, 0.5); 

    copyMakeBorder(img, img, 1, 1, 1, 1, BORDER_CONSTANT, Scalar(0)); 

    Point startPt(150, 150); 
    Point endPt(160, 10); 

    Mat1b mask = img > 200; 

    vector<Point> pts; 
    findNonZero(mask, pts); 


    map<Point, int, lessPoints> mp; 
    for (size_t i = 0; i < pts.size(); ++i) { 
     mp[pts[i]] = i; 
    } 

    adjacency_list_t adj(pts.size()); 
    for (size_t i = 0; i < pts.size(); ++i) { 

     int r = pts[i].y; 
     int c = pts[i].x; 

     // TODO: Check valid range 

     if (mask(r - 1, c - 1)) { // Top Left 
      adj[i].push_back(neighbor(mp[Point(c - 1, r - 1)], 1.414)); 
     } 
     if (mask(r - 1, c)) { // Top 
      adj[i].push_back(neighbor(mp[Point(c, r - 1)], 1.0)); 
     } 
     if (mask(r - 1, c + 1)) { // Top Right 
      adj[i].push_back(neighbor(mp[Point(c + 1, r - 1)], 1.414)); 
     } 
     if (mask(r, c - 1)) { // Left 
      adj[i].push_back(neighbor(mp[Point(c - 1, r)], 1.0)); 
     } 
     if (mask(r, c + 1)) { // Right 
      adj[i].push_back(neighbor(mp[Point(c + 1, r)], 1.0)); 
     } 
     if (mask(r + 1, c - 1)) { // Bottom Left 
      adj[i].push_back(neighbor(mp[Point(c - 1, r + 1)], 1.414)); 
     } 
     if (mask(r + 1, c)) { // Bottom 
      adj[i].push_back(neighbor(mp[Point(c, r + 1)], 1.0)); 
     } 
     if (mask(r + 1, c + 1)) { // Bottom Right 
      adj[i].push_back(neighbor(mp[Point(c + 1, r + 1)], 1.414)); 
     } 
    } 


    vertex_t start_vertex = mp[startPt]; 
    vertex_t end_vertex = mp[endPt]; 

    std::vector<weight_t> min_distance; 
    std::vector<vertex_t> previous; 
    DijkstraComputePaths(start_vertex, adj, min_distance, previous); 

    Mat3b dbg; 
    cvtColor(mask, dbg, COLOR_GRAY2BGR); 
    circle(dbg, startPt, 3, Scalar(0, 255, 0)); 
    circle(dbg, endPt, 3, Scalar(0, 0, 255)); 

    std::list<vertex_t> path = DijkstraGetShortestPathTo(end_vertex, previous); 

    for (vertex_t v : path) { 
     dbg(pts[int(v)]) = Vec3b(255, 0, 0); 
     int vgfd = 0; 
    } 

    imshow("Solution", dbg); 
    waitKey(); 

    return 0; 
}