Я хочу превратить двумерный массив в многоугольник. Производительность очень важна для меня, но я хочу избегать расширения Си. Бинарное контурное изображение может быть сделано с эрозией. Потом я нашелэтот, Это было слишком медленно и неt справляются с шипами, порожденными эрозией. Спайк:

000100
000100
000100
111011

Моя первая попытка:

mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)

vertices = np.argwhere(mat)
minx = vertices.min(axis=0)[0]
maxx = vertices.max(axis=0)[0]

vertices_sorted = {}
for x in xrange(minx - 1, maxx + 2):
    vertices_sorted[x] = []

for vertex in vertices:
    vertices_sorted[vertex[0]].append(vertex[1])

vertex_loop = [(minx, vertices_sorted[minx][0])]
while True:
    x, y = vertex_loop[-1]
    for column, row in ((x, y + 1), (x, y - 1), 
    (x + 1, y), (x + 1, y + 1), (x + 1, y - 1),
    (x - 1, y), (x - 1, y + 1), (x - 1, y - 1)):
        if row in vertices_sorted[column]:
            vertices_sorted[column].remove(row)
            vertex_loop.append((column, row))
            break
    else:
        vertex_loop.pop()

    if vertex_loop[-1] == vertex_loop[0]:
        break
return vertex_loop[:-1]

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

mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)

xs, ys = np.nonzero(mat)
ys = np.ma.array(ys)

vertex_loop = [(xs[0], ys[0])]
ys[0] = np.ma.masked
while True:
    x, y = vertex_loop[-1]
    start = np.searchsorted(xs, x-1, side="left")
    end = np.searchsorted(xs, x+1, side="right")

    for i in xrange(start, end):
        if ys[i] == y or ys[i] == y + 1 or ys[i] == y - 1:
            vertex_loop.append((xs[i], ys[i]))
            ys[i] = np.ma.masked
            break
    else:
        if np.all(ys.mask):
            break
        else:
            vertex_loop.pop()
return vertex_loop

Как я могу улучшить скорость дальше?

РЕДАКТИРОВАТЬ: Кажется, что массивные маски очень медленно. Эта реализация почти так же быстро, как и первая:

#import time
#t1 = time.time()
mat = mat.copy() != 0
mat = mat - scipy.ndimage.binary_erosion(mat)

xs, ys = np.nonzero(mat)
#t2 = time.time()
minx = xs[0]
maxx = xs[-1]

# Ketju pakosti käy läpi kaikki rivit minx:n ja maxx:n välissä, sillä se ON KETJU
xlist = range(minx - 1, maxx + 2)
# starts ja ends ovat dictit jotka kertovat missä slicessä x == key
tmp = np.searchsorted(xs, xlist, side="left")
starts = dict(zip(xlist, tmp))
tmp = np.searchsorted(xs, xlist, side="right")
ends = dict(zip(xlist, tmp))

unused = np.ones(len(xs), dtype=np.bool)
#t3 = time.time()
vertex_loop = [(xs[0], ys[0])]
unused[0] = 0
count = 0
while True:
    count += 1
    x, y = vertex_loop[-1]
    for i in xrange(starts[x - 1], ends[x + 1]):
        row = ys[i]
        if unused[i] and (row == y or row == y + 1 or row == y - 1):
            vertex_loop.append((xs[i], row))
            unused[i] = 0
            break
    else:
        if abs(x - xs[0])