Найти, если координаты образуют полный путь - PullRequest
1 голос
/ 06 апреля 2019

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

Я думал о создании начальной точки и поиске того, существует ли путь, который не повторяет точки (то есть (1,1) -> (2, 1) -> (1,1) запрещен) и мог бы вернуться к начальной точке; однако, если начальная точка находится в ответвлении круга, это не сработает.

Например, список координат

[[0, 0], [0, 1], [1, 2], [2, 3], [3, 3], [3, 4], [4, 4], [3, 2], [3, 1], [3, 0], [2, -1], [1, -1], [0, -1]] 

будет формировать полный путь, в то время как, если я уберу [1, -1], он не будет формировать полный путь.

1 Ответ

0 голосов
/ 07 апреля 2019

Решение, которое я выбрал, состоит в том, чтобы превратить список соседей в матрицу, превратить эту матрицу в матрицу логики, а затем, предположив, что вы точно знаете точку внутри цикла, использовать функцию imfill для этой точки и проверить,[1,1] координата была преобразована.

    mat = zeros(length, length);
    mat(coordinates) = 1;
    mat = logical(mat);
    mat = imfill(mat, [length/2 length/2]);
    if mat(1) == 1
       not closed loop
    else
       closed loop
    end

Некоторые предположения, касающиеся этого кода, заключаются в том, что средняя точка находится внутри цикла и еще не заполнена, а значение координаты (1,1) еще не будет заполнено, что является предположениями, которые я могу сделать с даннымиЯ работаю с

...