Кратчайший путь между двумя точками в сетке (Matlab) - PullRequest
Новая
       1

Кратчайший путь между двумя точками в сетке (Matlab)

3 голосов
/ 15 ноября 2011

Я пытаюсь найти кратчайший путь между двумя точками сетки без препятствий и двигаться во всех направлениях (N NE E ES S SW W WN).

Кажется, это обычная задача... Разве это не реализовано уже в Matlab?Когда Matlab строит две точки, соединенные линией (plot (X, Y, '-')), кажется, внутренне выполняет этот расчет, поскольку я предполагаю, что сгенерированное изображение также является сеткой.

Пример: из [1, 1] - [3,6] одно решение - [1,1;2,2;2,3;2,4;3,5;3,6]

Я пытался: 

    dist_x = length(linspace(p1(1),p2(1), dist(p1(1),p2(1))+1));
    dist_y = length(linspace(p1(2),p2(2), dist(p1(2),p2(2))+1));
    num_points = max(dist_x, dist_y);
    x = round(linspace(p1(1),p2(1),num_points));
    y = round(linspace(p1(2),p2(2),num_points));

Но я думаю, что он возвращает больше очков, чем должен, и, возможно, есть реализованная процедура.

Спасибосерия

1 Ответ

3 голосов
/ 16 ноября 2011

Решение (данное Дж. Ф. Себастьяном) - это Алгоритм Брезенхэма .

...