Каков кратчайший путь в двоичном изображении, которое охватывает все истинно значимые пиксели?

Question

Источником проблемы является то, что нам даны угловые точки многочлена. Точки, которые имеют целочисленные координаты, которые находятся внутри полинома, являются нашими узлами.

Предположим, что эти узлы вписаны в булеву матрицу, так что если пиксель равен true, то это внутри полинома. Это означает, что каждый пиксель соответствует целочисленной координате.

Мы хотели бы получить кратчайший путь, который охватывает все true пикселей (узлов), начиная с данной точки. Эта точка может быть любым из true пикселей. Узел может быть повторно посещен. Есть только 4 направления, что означает, что следующий узел должен быть на расстоянии одного пикселя по вертикали или горизонтали. Входными данными, вероятно, является большая матрица, и можно считать, что полином является выпуклым без дырок.

Желаемым выходным сигналом является вектор точек, в которых входные данные являются булевой матрицей. Мне нужен алгоритм, который решает проблему за минимальное количество оборотов.

До сих пор я думал о сканировании сверху вниз, как описано:

up_or_down = (cur_p.y - top_p.y) < (bot_p.y - cur_p.y)

if (up_or_down)    // up
    while (cur_p.y > top_p.y) {
        if (is_movable(cur_p.up))
            move(cur_p.up)
        else if (is_movable(cur_p.left.up))
            move(cur_p.left)
        else // right is movable
            move(cur_p.right)
    }
else    // down
    ...

while (there_is_movable()) {
    left_or_right = cur_p.x - leftmost_movable_p(cur_p).x < rightmost_movable_p(cur_p).x - cur_p.x

    if (left_or_right) {    // left
        while (leftmost_movable_p(cur_p).x < cur_p.x)
            move(cur_p.left)
        while (rightmost_movable_p(cur_p).x > cur_p.x)
            move(cur_p.right)
        if (up_or_down)    // up, so go down
            if (bot_p.y < cur_p.y)    // check if we reached bottom
                while ( ! is_movable(cur_p.down) )
                    move(cur_p.left)
        else    // down, so go up
            ...
    }

    else {    // right
        ...
    }
}

Я хотел бы знать, если есть лучшее решение, или вы думаете, что в моем алгоритме должны быть улучшения.

Answer 1

Выполнение простого поиска в глубину со спиральным поисковым соседством с возвратом на тупики может быть эффективным для замкнутых многоугольников без дырок. Я приложил простое решение. Если в вашем полигоне есть дыры, особенно если их много, вам нужно взглянуть на более мощные решения, предназначенные для общей задачи коммивояжера.

Я включил несколько тестовых данных (5x5 2D векторов) и переключаемая настройка #define BIAS, которая заставит поиск двигаться как можно дальше к одному углу, а затем повернуть к следующему углу. В некоторых случаях это быстрее, но в целом оставить поиск беспристрастным, вероятно, быстрее, и я оставил его неопределенным по умолчанию в коде ниже.

#include <iostream>
#include <vector>
using namespace std;

#define TEST3

#ifdef TEST1
bool matrixInit[] = {
    0, 0, 1, 0, 0,
    0, 1, 1, 1, 0,
    1, 1, 1, 1, 1,
    0, 1, 1, 1, 0,
    0, 0, 1, 0, 0
};
std::pair<int, int> startPoint(0, 2);
int trueCount = 13;

#elif defined(TEST2)
bool matrixInit[] = {
    1, 1, 1, 1, 1,
    1, 1, 1, 1, 1,
    0, 1, 1, 1, 1,
    0, 1, 1, 1, 1,
    0, 1, 1, 1, 1
};
std::pair<int, int> startPoint(0, 2);
int trueCount = 22;

#elif defined(TEST3)
bool matrixInit[] = {
    1, 0, 0, 0, 1,
    1, 1, 0, 1, 1,
    1, 1, 0, 1, 1,
    1, 1, 1, 1, 1,
    1, 1, 1, 1, 1
};
std::pair<int, int> startPoint(0, 4);
int trueCount = 20;
#endif

//#define BIAS

std::vector<std::vector<bool>> matrixVec;
std::vector<std::vector<std::pair<int, int>>> lastNode;
std::vector<std::pair<int, int>> path;
int visitedCount = 0;

int main() {
    matrixVec.resize(5);
    lastNode.resize(5);
    for (int i = 0; i < 5; ++i) {
        matrixVec[i].resize(5);
        lastNode[i].resize(5);
    }

    for (int y = 0; y < 5; ++y) {
        for (int x = 0; x < 5; ++x) {
            matrixVec[y][x] = matrixInit[y * 5 + x];
            lastNode[y][x] = std::pair<int, int>(-1, -1);
        }
    }

    //Important! Up, right, down, left spiral
    static int neighX[]{0, 1, 0, -1};
    static int neighY[]{-1, 0, 1, 0};
    static int bias = 0;

    path.push_back(startPoint);
    matrixVec[startPoint.first][startPoint.second] = 0;
    ++visitedCount;
    std::pair<int, int> currentPoint(startPoint);
    bool lastFoundVisited = true;

    int biasLimit = 4;
#ifdef BIAS
    biasLimit = 2;
#endif
    while (visitedCount < trueCount) {
        bool foundUnvisited = false;
        for (int i = 0; i < biasLimit; ++i) {
            int n = (i + bias) % 4;

            int nextY = currentPoint.first + neighY[n];
            int nextX = currentPoint.second + neighX[n];

            if (nextY >= matrixVec.size() || nextX >= matrixVec[0].size() || nextY < 0 || nextX < 0) {
                continue;
            }

            if (matrixVec[nextY][nextX]) {
                lastFoundVisited = true;
                foundUnvisited = true;
                ++visitedCount;
                matrixVec[nextY][nextX] = false;
                lastNode[nextY][nextX] = currentPoint;
                currentPoint = std::pair<int, int>(nextY, nextX);
                path.push_back(currentPoint);
                break;
            }
        }
        if (foundUnvisited) {
            continue;
        }

#ifdef BIAS
        if (lastFoundVisited) {
            lastFoundVisited = false;
            bias = (bias + 1) % 4;
            continue;
        }
#endif

        //Surrounded by matrix boundaries or previously visited nodes. Need to backtrack
        currentPoint = lastNode[currentPoint.first][currentPoint.second];
        path.push_back(currentPoint);
    }

    cout << "SIZE: " << path.size() << endl;
    for (int i = 0; i < path.size(); ++i) {
        cout << path[i].first << ", " << path[i].second << endl;
    }

    return 0;
}