728x90

blue cell: obstacles, black cell = start( or end) 

$$\text{distance measure}:~\text{Manhattan distance}=|x_2 - x_1 | + |y_2 - y_1|$$

Grassfire 알고리즘을 써서 최단경로를 찾는 문제는 DFS로도 구현할 수 있으나 비효율적이고(왜 그런지는 쉽게 알 수 있다) BFS로 구현하는 것이 더 적합하다. 

void grassfire(CPoint q, int **map, int w, int h, int **dist) {
    for (int y = 0; y < h; y++) 
        for (int x = 0; x < w; x++) 
            dist[y][x] = INF;  //unvisited cells;

    std::queue<CPoint> Q;
    dist[q.y][q.x] = 0;     //start( or end) position: distance = 0;
    Q.push(q);
    while (!Q.empty()) {
        CPoint p = Q.front(); Q.pop();
        int distance = dist[p.y][p.x];
        if (p.x > 0     && map[p.y][p.x - 1] == 0 && dist[p.y][p.x - 1] == INF) {
            dist[p.y][p.x - 1] = distance + 1;
            Q.push(CPoint(p.x - 1, p.y)); 
        }
        if (p.x < w - 1 && map[p.y][p.x + 1] == 0 && dist[p.y][p.x + 1] == INF) {
            dist[p.y][p.x + 1] = distance + 1;
            Q.push(CPoint(p.x + 1, p.y));
        }
        if (p.y > 0     && map[p.y - 1][p.x] == 0 && dist[p.y - 1][p.x] == INF) {
            dist[p.y - 1][p.x] = distance + 1;
            Q.push(CPoint(p.x, p.y - 1));
        }
        if (p.y < h - 1 && map[p.y + 1][p.x] == 0 && dist[p.y + 1][p.x] == INF) {
            dist[p.y + 1][p.x] = distance + 1;
            Q.push(CPoint(p.x, p.y + 1));
        }
    }
}

'Image Recognition > Fundamental' 카테고리의 다른 글

Brute-Force Euclidean Distance Transform  (0) 2021.03.14
Poisson Noise  (0) 2021.03.06
Grassfire Algorithm  (0) 2021.03.05
Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Posted by helloktk

댓글을 달아 주세요