#matlab #image-processing #graph
#matlab #обработка изображений #График
Вопрос:
Итак, у меня есть список точек, которые обычно образуют своего рода круглую форму, за исключением того, что от круга часто отходят небольшие ответвления, которые по сути являются просто линиями, скажем, от границы круга, идущего в определенном направлении. Я хочу создать функцию, которая при задании этого списка координат / точек определяет, существует ли полный путь в этом наборе точек.
Я думал о создании начальной точки и определении того, существует ли путь, который не повторяет точки (т. Е. (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. Вам не нужно возвращаться к начальной точке, чтобы обнаружить цикл. Вам нужно только вернуться к ранее посещенной точке, которая не является непосредственной предшественницей текущей точки.
2. @beaker Это верно, однако может быть небольшое скопление точек, которое вызовет это ложное обнаружение. В приведенном мной примере это сработало бы, однако я работаю с большими объемами данных, что не гарантирует, что не будет случаев, подобных тому, что я упомянул.
3. Может быть, этот путь является скелетом? Учитывая ваш ответ, похоже, что стандартная обрезка конечной точки сделает именно то, что вам нужно.
Ответ №1:
Решение, с которым я пошел, состоит в том, чтобы превратить список соседей в матрицу, превратить эту матрицу в матрицу логических элементов, а затем, предполагая, что вы точно знаете точку в цикле, используйте функцию 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) еще не будет заполнено, и это предположения, которые я могу сделать с данными, с которыми я работаю.