Предполагая, что в матрице/изображении присутствует только одна кривая и что каждая точка на кривой имеет от 1 до 2 соседей, следующая функция предоставит необходимые вам результаты.
Он работает, беря точку, ближайшую к верхнему левому углу, и формируя цепочку точек, итеративно находя ближайшую точку, которая еще не была посещена, до тех пор, пока не останется других точек. Для замкнутой кривой квадрат евклидова расстояния между первой/конечной точками цепи будет меньше 2.
import numpy as np
def find_chain(mat):
locs=np.column_stack(np.nonzero(mat))
chain=[np.array([0,0])]
while locs.shape[0]>0:
dists=((locs-np.vstack([chain[-1]]*locs.shape[0]))**2).sum(axis=1)
next=dists.argmin()
if dists.min()<=2 or len(chain)==1:
chain.append(locs[next,:])
locs=locs[np.arange(locs.shape[0])!=next,:]
else:
chain=[chain[0]]+chain[1::][::-1]
return np.vstack(chain[1::]),((chain[1]-chain[-1])**2).sum()<=2
Для открытой кривой:
>>> mat1=np.array([[0, 0, 0, 0, 0, 0, 0],
... [0, 1, 0, 0, 1, 0, 0],
... [0, 0, 1, 0, 0, 1, 0],
... [0, 0, 0, 1, 1, 0, 0],
... [0, 0, 0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat1)
>>> points
array([[1, 1],
[2, 2],
[3, 3],
[3, 4],
[2, 5],
[1, 4]])
>>> isclosed
False
И для замкнутой кривой:
>>> mat2=np.array([[0, 0, 0, 0, 0],
... [0, 0, 1, 0, 0],
... [0, 1, 0, 1, 0],
... [0, 1, 0, 1, 0],
... [0, 0, 1, 0, 0],
... [0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat2)
>>> points
array([[1, 2],
[2, 1],
[3, 1],
[4, 2],
[3, 3],
[2, 3]])
>>> isclosed
True
И кривая, где начальная точка (ближайшая точка к началу координат) делит кривую на две части.
>>> mat3=np.array([[0, 0, 0, 0, 0],
... [0, 1, 1, 1, 0],
... [0, 1, 0, 0, 0],
... [0, 1, 0, 0, 0],
... [0, 0, 0, 0, 0],
... [0, 0, 0, 0, 0]])
>>> points,isclosed=find_chain(mat3)
>>> points
array([[1, 3],
[1, 2],
[1, 1],
[2, 1],
[3, 1]])
>>> isclosed
False
23.06.2011
